1. ## 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

2. Hello !

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.

3. 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?

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?

4. Haha, I got killed
I'll be more careful next time, thanks NCA xD

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.

5. ## Thank you

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!