text: # Euler's Φ Function Proofs
  
  • Apr 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.
  • Apr 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$.
  • Apr 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).