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.
