# Euler's Φ Function Proofs

• April 9th 2010, 07:41 PM
jjbrian
Euler's Φ Function Proofs
hi
Quote:

Prove or Disprove
1) With two exceptions, if 1 ≤ n < m then Φ(n) <Φ(m)

Rules I used:
1)if p is prime, then Φ(p)= p-1
2) if p is prime, then for all e > 0, Φ(p^e) = p^e-1 * (p-1)

Attempt for problem 1).
Statement is true with the exceptions of cases b and c.
I considered 4 cases.
a)When n and m are both primes.
Φ(n) < Φ(m) is true by induction
b) When n and m both are not primes.
Φ(n) <Φ(m) is false by a counter example
Φ(n=25) < Φ(m=26) is false
c) n is prime and m is not prime.
False by counter example n=13 and m=14
d) n is not prime and m is prime.
True but I do not know a formal way to prove this.

------------------------------------------------------------
Prove or disprove:
2) There is no n with Φ(n)= 14.

Guess: Statement is true.

Case 1: If n is a prime then Φ(n)= n-1
n can only be 15, but 15 is not a prime.
therefore false.

Case 2: If n is not a prime.
There exist a factorization of primes. so rule 2 can be applied.
2) if p is prime, then for all e > 0, Φ(p^e) = p^e-1 * (p-1)

14 has two factorization 1*14 and 2*7
When p = 2
14= 2^(e-1) * (2-1)
when p = 7
14 = 7^e-1 * ( 7-1)
For both of these equations there are no such integer e which can satisfy these equation.

----------

3)For every m ≥ 3, no matter how large n might be, Φ(m) has to be an even number.
True. I dont know how to prove this.

I need help with all three problem. my proof are informal.
• April 9th 2010, 08:56 PM
chiph588@
2. See here.

3. If $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$, then $\phi(n) = \prod_{i=1}^k p_i^{\alpha_i-1}(p_i-1)$

If $p_j\neq2$ then $p_j-1$ is even and we're done.

So our last case to consider is when $n=2^k$ which means $\phi(n) = 2^{k-1}$. So $\phi(n)$ is even when $k>1$.

Thus $\phi(n)$ is even for all $n>2$.
• April 9th 2010, 09:01 PM
chiph588@
Quote:

Originally Posted by jjbrian
d) n is not prime and m is prime.
True but I do not know a formal way to prove this.

We're given $n where $n$ is composite and $m$ is prime.

$n$ composite $\implies \phi(n).