1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    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!

Homework Help: 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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook