1. PF Contest - Win "Conquering the Physics GRE" book! Click Here to Enter
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Number Theory Q re: Euler phi-function

  1. Apr 15, 2012 #1
    1. The problem statement, all variables and given/known data

    Let p be prime. Show that p n, where n is a positive integer, iff [itex]\phi[/itex](np) = (p-1)[itex]\phi[/itex](n).

    2. Relevant equations

    Theorem 1: If p is prime, then [itex]\phi[/itex](p) = p-1. Conversely, if p is a positive integer with [itex]\phi[/itex](p) = p-1, then p is prime.

    Theorem 2: Let m and n be relatively prime positive numbers. Then [itex]\phi[/itex](mn) = [itex]\phi[/itex](m)[itex]\phi[/itex](n).

    3. The attempt at a solution

    Assume that p n.
    By Theorem 2, [itex]\phi[/itex](np) = [itex]\phi[/itex](n)[itex]\phi[/itex](p).
    By Theorem 1, [itex]\phi[/itex](np) = [itex]\phi[/itex](n)[itex]\cdot[/itex](p-1).
    So, if p n, then [itex]\phi[/itex](np) = (p-1)[itex]\cdot[/itex][itex]\phi[/itex](n).

    Now, assume that [itex]\phi[/itex](np) = (p-1)[itex]\phi[/itex](n).
    By Theorem 1, [itex]\phi[/itex](np) = [itex]\phi[/itex](p)[itex]\phi[/itex](n), since p is prime.

    ...and, that's it. I can't use Theorem 2 to show that n and p are relatively prime, so I'm not entirely sure what to do next. p is prime, so n p, but I don't see anything to base a conclusion of p n.

    Any help would be greatly appreciated!
  2. jcsd
  3. Apr 15, 2012 #2


    User Avatar
    Science Advisor
    Homework Helper

    If a prime p doesn't divide n then aren't p and n relatively prime? A common divisor of p and n must divide p. Think about it.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook