User:Vinkmar

From Wikipedia, the free encyclopedia

[edit] m363a4q7

p^{q-1} + q^{p-1} \equiv 1 \pmod{pq}

But p and q are distinct primes, so for the above to be valid, the following two equations must hold:

p^{q-1} + q^{p-1} \equiv 1 \pmod{p} and p^{q-1} + q^{p-1} \equiv 1 \pmod{q}

Considering only the first of the two equations (the latter case is, for lack of a better term, symmetrical), we have:

p^{q-1} \equiv 0 \pmod{p} and q^{p-1} \equiv 1 \pmod{p}.

The former is obviously true. The latter is proven using Fermat's Little Theorem, QED