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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ This is deifnitely a duplicate. $\endgroup$ – Bill Dubuque Apr 19 '12 at 21:20
  • 1
    $\begingroup$ My apologies if it is, I could not find it. $\endgroup$ – Dominick Gerard Apr 19 '12 at 21:29
6
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ From here, could we say $a \equiv a_0 \quad \text{mod } pq$? Would that be enough to complete the proof? $\endgroup$ – Dominick Gerard Apr 19 '12 at 21:40
  • $\begingroup$ @Dominick: What's $a_0$ to you? $\endgroup$ – anon Apr 19 '12 at 21:41
  • $\begingroup$ can we say that it is 1? we know it must be in the set of all integers right? $\endgroup$ – Dominick Gerard Apr 19 '12 at 21:43
  • $\begingroup$ @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. $\endgroup$ – anon Apr 19 '12 at 21:47
  • $\begingroup$ 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}$? $\endgroup$ – Dominick Gerard Apr 19 '12 at 22:02
6
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
5
$\begingroup$

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

|cite|improve this answer
$\endgroup$
1
$\begingroup$

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

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.