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.
Please comment and offer any advice that would help me.

---

2. See here.

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

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

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

Thus $\displaystyle \phi(n) $ is even for all $\displaystyle n>2 $.

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 $\displaystyle n<m $ where $\displaystyle n $ is composite and $\displaystyle m $ is prime.

$\displaystyle n $ composite $\displaystyle \implies \phi(n)<n-1<m-1=\phi(m) $.