8
$\begingroup$

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.

  • 0
    Your post contained formula `$\phi(n):=\sum_{m=1}_{(m,n)=1}^n 1$` which did not render: $\phi(n):=\sum_{m=1}_{(m,n)=1}^n 1$. I replaced it with `$\phi(n):=\sum_{\substack{m=1\\(m,n)=1}}^n 1$` which renders as $\phi(n):=\sum\limits_{\substack{m=1\\(m,n)=1}}^n 1$. If this is not what you were going for, please, edit the post further.2015-02-14

1 Answers 1

5

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

  • 1
    ah, thanks a lot for your patience, now I got it2011-10-28