# Proof: $\phi(n)=\sum\limits_{k=1}^{n-1} \left\lfloor\frac{1}{\operatorname{gcd}(n,k)} \right\rfloor$

I've got a question how to start the proof of the following task:

$$\phi(n)=\sum_{k=1}^{n-1} \left\lfloor\frac{1}{\operatorname{gcd}(n,k)} \right\rfloor$$

Any hints where and how to start? I know the definition

$$\phi(n):=\sum_{m=1}_{(m,n)=1}^n 1$$ but I don't know how to move on. Any help would be fine.

Greetings.

-
What is lcd(n,k)? –  Ragib Zaman Oct 28 '11 at 12:16
I think he means gcd(n,k) –  Daniel Freedman Oct 28 '11 at 12:18
arg, sorry, i mixed it up: gcd is the right expression –  ulead86 Oct 28 '11 at 12:20

It's often a good idea to expand out sums to see if it helps you understand what's going on:

$\phi(n) = \left\lfloor\frac{1}{(n,1)}\right\rfloor + \left\lfloor\frac{1}{(n,2)}\right\rfloor + ... + \left\lfloor\frac{1}{(n,n-1)}\right\rfloor$,

where I'm writing $(n,k)$ as shorthand for $\mbox{gcd}(n,k)$.

A few things to think about:

1. What's the smallest possible value of $(n,k)$? What is the largest? What are the possible values of $\left\lfloor \frac{1}{(n,k)}\right\rfloor$? When will these values occur?

2. What does $\phi(n)$ tell you about $n$?

-
Correct. So, what about the possible values of $\left[ \frac{1}{(n,k)} \right]$? If you don't already, think of the floor function as "rounding down". –  Daniel Freedman Oct 28 '11 at 12:30
Not quite. We have two cases: either $(n,k) = 1$, or $(n,k) > 1$. You're correct that, in the first case, $\left[ \frac{1}{(n,k)} \right] = 1$. However, in the second, what you've written can't be true, as $\left[\frac{1}{(n,k)} \right]$ must be an integer. We're dividing 1 by a number ($d$, say) bigger than 1, and then rounding down to the nearest integer. What does this give us? You should see that it doesn't matter what $d$ actually is: it only matters that $d$ is bigger than 1. –  Daniel Freedman Oct 28 '11 at 12:40
In any case, the smaller of $n$ and $k$ is $k$, not $n$. –  Daniel Freedman Oct 28 '11 at 12:46
Correct. It's essentially a 'counting' function: $\left[ \frac{1}{(n,k)} \right]$ counts 1 if $k$ is coprime to $n$, and 0 if not. –  Daniel Freedman Oct 28 '11 at 12:50
ah, thanks a lot for your patience, now I got it –  ulead86 Oct 28 '11 at 12:51