CRT + Fermat's Little Theorem 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.
 A: Write $a=p^{q-1}+q^{p-1}$. Immediately we have
$$\begin{cases} a\equiv 0^{\,q-1}+q^{p-1} \equiv 1 \mod p  \\ 
a\equiv p^{q-1}+0^{\,p-1} \equiv 1 \mod q.\end{cases}$$
What does CRT tell us $a$ must be $\bmod pq$?
A: Hint $\rm\ mod\ (p,q)\!:\ q^{p-1}\equiv (1,0),\ \ p^{q-1}\equiv (0,1)\:$ so their sum $\rm\:x \equiv (1,1)$
So $\rm\:p,q\ |\ x\!-\!1\ \Rightarrow\ pq = lcm(p,q)\ |\ x\!-\!1.\:$ (CRT isn't needed for this simple constant case)
More generally, if $\rm\:b,c\:$ are coprime then $\rm\: e' = b^{\phi(c)}$ satisfies $\rm\: e'\equiv 0\pmod{b},\ e'\equiv 1\pmod{c}\:.\ $ Hence, $\ $  using $\rm\:e'\:$ and its complement $\rm\:\ e = 1-e'\:,\ $ where $\rm\ \ e\: \equiv 1\pmod{b},\ e\:\equiv 0\pmod{c}\:,\:$ yields the following closed-form for solutions of congruences by the Chinese Remainder Theorem
$$\begin{eqnarray}\rm x\ \equiv\ a\pmod{b} \\ \rm x\ \equiv\ d\pmod{c}\end{eqnarray}\rm\ \ \iff\ \ x\ \equiv\ a\ e + d\ e'\pmod{b\:c}$$
The relationship between CRT and the orthogonal idempotents $\rm\:(1,0),\ (0,1)\:$ will become clearer when you study the Peirce decomposition induced by such idempotents.
A: first using Fermat's theorem,
$q^{p-1}\equiv 1 \pmod p$
Also,$\ \ \ p^{q-1}\equiv0 \pmod p$
Second using Fermat's theorem,
$p^{q-1}\equiv 1 \pmod q$
Also,$q^{p-1}\equiv0 \pmod q$
Using first part we get,
$q^{p-1}+p^{q-1}\equiv1 \pmod p$
using second part we get,
$p^{q-1}+q^{p-1}\equiv1 \pmod q$
Since $p$ and $q$ are distinct prime, therefore $\gcd (p,q)=1$
$q^{p-1}+p^{q-1}\equiv1 \pmod {pq}$ 
A: Since $\gcd(p,q)=1$, by Fermat little theorem, $p^{q-1}\equiv1  \pmod q$$.
Now, $q^{p-1}\equiv 0 \pmod q$ $(\because q\mid q^{p-1}).$
Thus we have, $p^{q-1}+q^{p-1}\equiv 1 \pmod q\tag{1}$
Again by Fermat little theorem,
$q^{p-1}\equiv 1 \pmod p$
And $p^{q-1}\equiv 0 \pmod q$ $(\because p\mid p^{q-1})$
From this we have,
$p^{q-1}+q^{p-1}\equiv 1 \pmod p\tag{2}$
From $(1)$ and $(2)$, we have,
$p^{q-1}+q^{p-1}\equiv 1 \pmod {pq}$  $(\because (p,q)=1)$
