Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.


share|cite|improve this question
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
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. –  Martin Sleziak Feb 14 at 7:22

1 Answer 1

up vote 5 down vote accepted

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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.