A number theory problem

Number Theory Level 4

Let $(a,b)$ denote the greatest common divisor of integers $a$ and $b$ .

If $n\ge 2$ , evaluate

$\sum _{ j=1 }^{ n-1 } \left\lfloor \cfrac { 1 }{ (n,j) } \right\rfloor.$

\cfrac { n }{ \phi (n) }

\phi (n)

n

1

1 solution

Oliver Papillo
Apr 12, 2017

Where $x$ is a positive integer, $\lfloor\frac{1}{x}\rfloor = 1$ when $x = 1$ and $\lfloor\frac{1}{x}\rfloor = 0$ otherwise.

So the sum for $n$ is equal to the number of positive integers $j$ less than $n$ such that $gcd(n,j) = 1$ .

This is exactly what $\phi(n)$ is defined as, so the sum is always equal to $\phi(n)$ .