Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Expansion of Fermat's Little Theorem

  1. Apr 5, 2010 #1
    I've got a pair of (related) problems that are keeping me stumped. The two problems they are asking me to prove are:

    [tex] p^{(q-1)} + q^{(p - 1)} \equiv 1 \; (\!\!\!\!\!\! \mod \, pq) [/tex]

    [tex]a^{\phi(b)} + b^{\phi(a)} \equiv 1
    \; (\!\!\!\!\!\! \mod \, ab)[/tex]

    Where [tex] \phi(n) [/tex] is Euler's Totient Function.

    I know that these are similar, as the second problem is using Euler's Theorem, a generalization of Fermat's Little Theorem, I just can't seem to figure them out.
  2. jcsd
  3. Apr 5, 2010 #2
    Can you show:
    [tex]p^{q-1}+q^{p-1}\equiv 1 \pmod{p}[/tex]
    ? If so can you do the same mod q and combine these results to get it mod pq?
  4. Apr 5, 2010 #3
    BTW you are probably forgetting some requirements, because as stated your identities are false. Take for instance a=4, b=6, then you get:
    [tex]a^{\phi(a)}+b^{\phi(b)}=4^2+6^2=52 \equiv 4 \pmod {ab=24}[/tex]
    Perhaps you meant for a and b to be relatively prime. And in the first you can take p=q=2 and get:
    [tex]p^{q-1}+q^{p-1} = 2^1+2^1 = 4 \equiv 0 \pmod {pq=4}[/tex]
    Maybe p and q should be distinct?
  5. Apr 5, 2010 #4
    Thanks! Yes, in the first one, p and q are distinct primes, and in the second, a and b are coprime.
  6. Apr 6, 2010 #5


    User Avatar

    Indeed, Euler's Totient Function is a very nice generalization of Fermat's Little Theorem. There is an intuitive proof for both which is studied in "Olympiad Training" but if you're a student, you may try to use group properties. (hint- consider the set {1,2,...,p-1} and the multiplication modulo p. This is clearly a group. Then, What is the order of this group ? What is the order of each element? What does Lagrange's theorem implies ? Try first with Fermat's Little Theorem, and then you may try to expand in Euler's function)
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook