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
    What is lcd(n,k)?2011-10-28
  • 2
    I think he means gcd(n,k)2011-10-28
  • 0
    arg, sorry, i mixed it up: gcd is the right expression2011-10-28
  • 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$?

  • 0
    I would say: the smallest possible value of (n,k) is always 1, if n and k are coprime. The largest value, I suggest, is k. $\phi(n)$ gives me the number of coprime integers of n.2011-10-28
  • 1
    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".2011-10-28
  • 0
    If $(n,k)=1$ then I get for $\left[ \frac{1}{(n,k)} \right]=\frac{1}{1}$ and in the other case, I get $\left[ \frac{1}{(n,k)} \right]=\frac{1}{n}$ because I pick the smaller number of n and k.2011-10-28
  • 1
    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.2011-10-28
  • 1
    In any case, the smaller of $n$ and $k$ is $k$, not $n$.2011-10-28
  • 0
    and the nearest integer is 0, so all $\left[ \frac{1}{(n,k)} \right]$ with $(n,k) \neq 1$ are "rounded down" to zero? In the sum only the fractions with $(n,k)=1$ remain, which is the number of coprime integers?2011-10-28
  • 2
    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.2011-10-28
  • 1
    ah, thanks a lot for your patience, now I got it2011-10-28