Expansion of Fermat's Little Theorem

[pacdude9]

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

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

a^{\phi(b)} + b^{\phi(a)} \equiv 1<br /> \; (\!\!\!\!\!\! \mod \, ab)

Where \phi(n) 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.

 

[rasmhop]

Can you show:
p^{q-1}+q^{p-1}\equiv 1 \pmod{p}
? If so can you do the same mod q and combine these results to get it mod pq?

 

[rasmhop]

BTW you are probably forgetting some requirements, because as stated your identities are false. Take for instance a=4, b=6, then you get:
\phi(a)=\phi(b)=2
a^{\phi(a)}+b^{\phi(b)}=4^2+6^2=52 \equiv 4 \pmod {ab=24}
Perhaps you meant for a and b to be relatively prime. And in the first you can take p=q=2 and get:
p^{q-1}+q^{p-1} = 2^1+2^1 = 4 \equiv 0 \pmod {pq=4}
Maybe p and q should be distinct?

 

[pacdude9]

Perhaps you meant for a and b to be relatively prime.
Maybe p and q should be distinct?

Thanks! Yes, in the first one, p and q are distinct primes, and in the second, a and b are coprime.

 

[IB1]

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)