Sum of Co-prime Numbers of an Integer

Problem

Given a number $N$, find the sum of all numbers less than or equal to $N$ that are co-prime with $N$.

In case you forgot, a number $x$ is co-prime with $N$ if $gcd(x,N) = 1$.

For example, if $N = 10$, then the following numbers are co-prime with it: $[1, 3, 7, 9]$. Therefore, sum of co-prime numbers will be $1 + 3 + 5 + 7 + 9 = 20$.

Solution

Let us define a function $f(n)$, which gives us sum of all numbers less than or equal to $n$ that are co-prime to $n$. Then we can calculate the value of $f(n)$ with the following formula:

$$\bbox[yellow,5px]{
f(n) = \frac{\phi(n)}{2}n
}$$

where $\phi(n)$ is Euler Phi Function.

For example, for $n = 10$, then we get the sum of co-prime as:

$$\begin{align}
f(10) & = \frac{\phi(10)}{2} \times 10 \\
& = \frac{4}{2} \times 10 \\
& = 20
\end{align}
$$

Proof

Prerequisite

In order to understand this section, you have to be familiar with the following topic: Euler Totient or Phi Function

The proof is very simple. We divide the proof in two sections: when $n = 2$ and when $n > 2$.

When $n = 2$

When $n = 2$, we can see that the formula works by directly inserting the values:

$$\begin{align}
f(2) & = \frac{\phi(2)}{2} \times 2 \\
& = 1 \times 1 \\
& = 1
\end{align}
$$

Hence $f(2) = 1$, which is correct since the only integer less than $2$ co-prime with $2$ is $1$. So the formula works for when $n = 2$.

When $n > 2$

In order to prove the formula for the rest of the integers, we need to establish the following two facts:

  1. When $n > 2$, $\;\phi(n)$ is always even

    This is easy to establish. We just need to look at the formula for $\phi(n)$. We know that $\phi(n) = n \times \frac{p_1-1}{p_1} \times \frac{p_2-1}{p_2}… \times \frac{p_k-1}{p_k}$.

    Now, every $p_i$ divides $n$ as they are factor of $n$. So we can re-write the formula as:

    $\phi(n) = \frac{n}{p_1\times p_2 \dots \times p_k} \times (p_1 -1 ) \times (p_2 – 1) \times \dots \times (p_k – 1)$

    Since $n > 2$, there must be an odd prime factor, $p_j$, in $n$ and $p_j – 1$ is even. Hence, $\phi(n)$ is a multiple of $p_j – 1$ or an even number. Hence $\phi(n)$ is even for $n>2$.

  2. If $gcd(x,n) = 1$, then $gcd(n-x,n) = 1$

    This is a property of $gcd$ function. This can be proved using contradiction.

    Suppose $gcd(x,n) = 1$, but $gcd(n-x,n) = d$, where $d > 1$. Then $d$ divides $n-x$ and $n$. If $d$ divides $n$ and $n-x$, then it must also divide $x$. But that’s impossible since if $d$ can divide both $n$ and $x$, then $gcd(x,n) = d$. But we started with the fact that $gcd(x,n) = 1$. Contradiction! Hence, $gcd(n-x,n) \not = d$. Instead, it must be $gcd(n-x,n) = 1$.

With the two facts above established, we can now continue with our proof.

  • Let $S = {r_1, r_2, r_3, \dots, r_{\phi(n)}}$, where $r_i$ is a number which is co-prime to $n$.
  • Since $r_i$ is co-prime to $n$ and belongs to $S$, $n-r_i$ is also co-prime to $n$ and belongs to $S$.
  • Hence, we can form a pair: ${r_i, n-r_i}$ such that sum of the pair ${r_i, n-r_i}$ equals to $n$.
  • Since $\phi(n)$ is even, we can form $\phi(n)/2$ such pairs.
  • Each pair gives us a sum of $n$.
  • So, if we take sum of all pairs, we get $r_1 + r_2 + r_3 + \dots + r_{\phi(n)} = \frac{\phi(n)}{2}n$. Proved 🙂

Conclusion

The proof is very cute. Hopefully, you found it easy to understand. Unfortunately, I did not find any related problems. If you happen to know any related problems, please let me know in the comments.