## 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}

$$