Results 1 to 3 of 3

Math Help - Euler's Φ Function Proofs

  1. #1
    Newbie
    Joined
    Feb 2010
    Posts
    17

    Euler's Φ Function Proofs

    hi
    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    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 .
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by jjbrian View Post
    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<m where  n is composite and  m is prime.

     n composite  \implies \phi(n)<n-1<m-1=\phi(m) .
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: December 10th 2010, 07:14 AM
  2. Euler Phi function II
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: December 27th 2009, 05:33 AM
  3. [SOLVED] Number Theory:Euler phi function proofs
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: February 20th 2009, 01:39 AM
  4. Euler & Hamiltonian Circuit proofs
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 9th 2008, 08:16 PM
  5. Replies: 3
    Last Post: October 6th 2007, 03:01 PM

Search Tags


/mathhelpforum @mathhelpforum