# Euler Function Inequality

• Feb 27th 2010, 07: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, 08:56 PM
Bacterius
Hello !

Quote:

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

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

Originally Posted by Bacterius
Hello !

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

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

Quote:

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

Tand, if $\displaystyle 0 \leq j \leq k,$ then $\displaystyle 2^j \leq 2^k < n$ and $\displaystyle \gcd(2^j,n)=1.$ how many elements does the set $\displaystyle \{2^j: \ 0 \leq j \leq k \}$ have?
• Feb 28th 2010, 12: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, 06:12 AM
Tand
Thank you
Quote:

Originally Posted by [B
Tand, if $\displaystyle 0 \leq j \leq k,$ then $\displaystyle 2^j \leq 2^k < n$ and $\displaystyle \gcd(2^j,n)=1.$ how many elements does the set $\displaystyle \{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!