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
[imath]p^{q-1} \equiv 1 \mod(q)[/imath]
so using that as a starting point,
[imath]p^{q-1}=k.q + 1[/imath] for some k,
[imath]p^{q}=k.p.q + p[/imath]
[imath]p^{q} \equiv p \mod(pq).[/imath]
Similarly for q, and adding
[imath]p^{q}+q^{p} \equiv (p+q) \mod(pq) \;\; \;[/imath] (1).
Now consider
[imath](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)[/imath]
using (1).
So,
[imath](p^{q-1}+ q^{p-1})(p+q)-(p+q) \equiv 0 \mod(pq),[/imath]
[imath](p+q)(p^{q-1}+q^{p-1}-1) \equiv 0 \mod(pq).[/imath]
Since p+q will not be divisible by pq, it follows that the other factor will be, meaning that
[imath]p^{q-1} + q^{p-1} - 1 = k.p.q,[/imath] for some k,
[imath]p^{q-1}+q^{p-1} \equiv 1 \mod(pq).[/imath]

 

[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. [imath]p+q[/imath] and [imath]pq[/imath] are mutually prime.

 

[BobP]

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

In context, it's quite a small nit.