Number Theory 11/29

[Steven G]

Show that if p and q are distinct primes, then p^(q-1) + q^(p-1) = 1 (mod pq)

 

[BobP]

Fermat's little theorem says that
$p^{q-1} \equiv 1 \mod(q)$
so using that as a starting point,
$p^{q-1}=k.q + 1$ for some k,
$p^{q}=k.p.q + p$
$p^{q} \equiv p \mod(pq).$
Similarly for q, and adding
$p^{q}+q^{p} \equiv (p+q) \mod(pq) \;\; \;$ (1).
Now consider
$(p^{q-1}+q^{p-1})(p +q)=p^{q}+q^{p}+q.p^{q-1}+p.q^{p-1} \\ \equiv (p^{q}+q^{p})\mod(pq) \equiv (p+q) \mod(pq)$
using (1).
So,
$(p^{q-1}+ q^{p-1})(p+q)-(p+q) \equiv 0 \mod(pq),$
$(p+q)(p^{q-1}+q^{p-1}-1) \equiv 0 \mod(pq).$
Since p+q will not be divisible by pq, it follows that the other factor will be, meaning that
$p^{q-1} + q^{p-1} - 1 = k.p.q,$ for some k,
$p^{q-1}+q^{p-1} \equiv 1 \mod(pq).$

 

[blamocur]

Since p+q will not be divisible by pq, it follows that the other factor will be, meaning that

Could not resist nitpicking : you need a stronger statement here, i.e. $p+q$ and $pq$ are mutually prime.

 

[BobP]

Could not resist nitpicking : you need a stronger statement here, i.e. $p+q$ and $pq[/im [/QUOTE]$

In context, it's quite a small nit.