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

Question

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_{\substack{m=1\\(m,n)=1}}^n 1$$ but I don't know how to move on. Any help would be fine.

Greetings.

Answer 1

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$?