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

Greetings.

share|improve this question
    
What is lcd(n,k)? –  Ragib Zaman Oct 28 '11 at 12:16
2  
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
add comment

1 Answer

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|improve this answer
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". –  Daniel Freedman Oct 28 '11 at 12:30
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. –  Daniel Freedman Oct 28 '11 at 12:40
1  
In any case, the smaller of $n$ and $k$ is $k$, not $n$. –  Daniel Freedman Oct 28 '11 at 12:46
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. –  Daniel Freedman Oct 28 '11 at 12:50
1  
ah, thanks a lot for your patience, now I got it –  ulead86 Oct 28 '11 at 12:51
show 3 more comments

Your Answer

 
discard

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.