# 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.

-
This is deifnitely a duplicate. –  Bill Dubuque Apr 19 '12 at 21:20
My apologies if it is, I could not find it. –  Dominick Gerard Apr 19 '12 at 21:29

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$?

-
From here, could we say $a \equiv a_0 \quad \text{mod } pq$? Would that be enough to complete the proof? –  Dominick Gerard Apr 19 '12 at 21:40
@Dominick: What's $a_0$ to you? –  anon Apr 19 '12 at 21:41
can we say that it is 1? we know it must be in the set of all integers right? –  Dominick Gerard Apr 19 '12 at 21:43
@Dominick: Given $a\equiv1~(p)$ and $a\equiv1~(q)$, at the very least CRT says there is a unique solution modulo $pq$. Obviously $1$ is a solution, so $a\equiv1~(pq)$ by uniqueness. –  anon Apr 19 '12 at 21:47
thanks, also can you elaborate on why we can go from $a=p^{q-1} + q^{p-1}$ to $a \equiv 0^{q-1} + q^{p-1} \equiv p^{q-1} + 0^{p-1}$? –  Dominick Gerard Apr 19 '12 at 22:02

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.

-

first using Fermat's theorem,

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

Also,$\ \ \ p^{q-1}\equiv0(mod\ p)$

Second using Fermat's theorem,

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

Also,$q^{p-1}\equiv0(mod\ q)$

Using first part we get,

$q^{p-1}+p^{q-1}\equiv1(mod\ p)$

using second part we get,

$p^{q-1}+q^{p-1}\equiv1(mod\ q)$

Since p and q are distinct prime, therefore gcd (p,q)=1

$q^{p-1}+p^{q-1}\equiv1(mod\ pq)$

-

Since $gcd(p,q)=1$, by Fermat little theorem, $p^{q-1}\equiv1 (\mod{q})$.

Now, $q^{p-1}\equiv 0(\mod{q})(\because q\mid q^{p-1}).$

Thus we have, $p^{q-1}+q^{p-1}\equiv 1(\mod{q}).\tag{1}$ Again by Fermat little theorem,

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

And $p^{q-1}\equiv 0(\mod{q})(\because p\mid p^{q-1})$

From this we have, $p^{q-1}+q^{p-1}\equiv 1(\mod{p})\tag{2}$ From $(1)$ and $(2)$, we have,

$p^{q-1}+q^{p-1}\equiv 1(\mod{pq}) .(\because (p,q)=1)$

-