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 + 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
[su_box title=”Prerequisite”]
In order to understand this section, you have to be familiar with the following topic: Euler Totient or Phi Function
[/su_box]
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:
- 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$, if $n$ is not a power of $2$ then 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 when $n$ is not a power of $2$.
When $n$ is a power of $2$, $phi(n) = \frac{n}{2} \times (2-1) = \frac{n}{2}$. Since $n > 2$ and a power of $2$, we will always get an even number.
Hence $\phi(n)$ is even for all values of $n>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.