Extension of Fermat's Little Theorem
Let
\[p, \; q\]
be distinct primes, then \[p^{q-1}+q^{p-1} \equiv 1 \; (mod \; pq)\]
.Proof
From Fermat's Little Theorem
\[p^{q-1} \equiv 1 \; (mod \; q), \; q^{p-1} \equiv 1 \; (mod \; p)\]
.Hence
\[p^{q-1} -1=mq, \; q^{p-1}-1=np\]
.Multiplying these together gives
\[(p^{q-1} -1)(q^{p-1}-1=mqnp\]
.\[(p^{q-1}q^{p-1}-p^{q-1}-q^{p-1}+1=mmqp\]
.\[-p^{q-1}-q^{p-1}+1 \equiv 0 \; (mod \; pq)\]
.\[p^{q-1}+q^{p-1} \equiv 1 \; (mod \; pq)\]
.
