Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

4 Answers 4

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

share|improve this answer
    
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.

share|improve this answer

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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