4
$\begingroup$

I am seeking a proof for the following...

Suppose $p$ and $q$ are distinct primes. Show that $$ p^{q-1} + q^{p-1} \equiv 1 \quad (\text{mod } pq)$$ $$$$ $$$$ I gather from Fermat's Little Theorem the following: $$q^{p-1} \equiv 1 \quad (\text{mod } p)$$

and

$$p^{q-1} \equiv 1 \quad (\text{mod } q)$$

How can I use this knowledge to give a proof? I'm confident I can combine this with the Chinese Remainder Theorem, but I am stuck from here.

  • 0
    This is deifnitely a duplicate.2012-04-19
  • 1
    My apologies if it is, I could not find it.2012-04-19

4 Answers 4