# Euler Function Inequality

• Feb 27th 2010, 08:21 PM
Tand
Euler Function Inequality
Hi all, I've been stumped by this proof:

Prove that if n is any odd positive integer and k is a natural number such that n > 2^k, then phi(n) >= k + 1

So far I've only been able to use the fact that n is odd to say that phi(2n) = phi(n) since phi(2n) = phi(2) * phi(n). I'm not sure if this is even relevant, but it seems like it could be useful. Any help is appreciated.

Thank you
• Feb 27th 2010, 09:56 PM
Bacterius
Hello !

Quote:

phi(2n) = phi(n)
This is wrong, it only holds if $n$ is an odd prime number, which cannot be controlled in your question.

Note that $\varphi{ \left ( 2^k \right ) } = k$. This might be useful.
• Feb 27th 2010, 11:47 PM
NonCommAlg
Quote:

Originally Posted by Bacterius
Hello !

This is wrong, it only holds if $n$ is an odd prime number, which cannot be controlled in your question.

it's not wrong! if $\gcd(m,n)=1,$ then $\varphi(mn)=\varphi(m)\varphi(n).$ what do you get if you put $m=2$ and assume that $n$ is odd?

Quote:

Note that $\varphi{ \left ( 2^k \right ) } = k$. This might be useful.
sorry but this is wrong! for any positive integer $k: \ \varphi(2^k)=2^{k-1}.$

Tand, if $0 \leq j \leq k,$ then $2^j \leq 2^k < n$ and $\gcd(2^j,n)=1.$ how many elements does the set $\{2^j: \ 0 \leq j \leq k \}$ have?
• Feb 28th 2010, 01:48 AM
Bacterius
Haha, I got killed :D
I'll be more careful next time, thanks NCA xD

Quote:

sorry but this is wrong!
What the hell, this Java applet kept telling me that phi(256) = 8 and phi(512) = 9 ! I'll do it myself next time.
• Feb 28th 2010, 07:12 AM
Tand
Thank you
Quote:

Originally Posted by [B
Tand, if $0 \leq j \leq k,$ then $2^j \leq 2^k < n$ and $\gcd(2^j,n)=1.$ how many elements does the set $\{2^j: \ 0 \leq j \leq k \}$ have?

It will have K+1 elements that are relatively prime to n. Then n's euler function is at least K + 1. That's perfect. Thank you very much!