# Prove $a^{pq} \equiv a \pmod {pq}$

For p and q being distinct primes. I am given that $a^{p} \equiv a \pmod q$ and $a^q \equiv a \pmod p$. We are supposed to use the Fermat's Theorem and Chinese remainder Theorem to Prove.

I have assumed that $p$ not equal to $q$ is what is meant by distinct. I know $a^p \equiv a \pmod p$. So $a^q \equiv a^p \equiv a \pmod p$. Similarly, Since $a^q \equiv a \pmod q$ then $a^p \equiv a^q \equiv a \pmod q$.

I am having a hard time going from $\mod p$ and $\mod q$ to $\mod pq$. Can someone point me in the right direction?

• Daniel that doesn't really help. I fully understand that a^(pq)≡(a^p)^q≡(a^q)^p in either mod p or mod q. – Elisabeth Sep 25 '13 at 23:49
• Sorry, misread your problem. It's almost 2am here, if that serves as an excuse. But going from the two congruences to the joint congruence is exactly what the Chinese remainder theorem is about. – Daniel Fischer Sep 25 '13 at 23:52
• Using CRT: I get a^pq ≡ p+q (mod pq). I am getting a1=a, a2=a, N1=p, N2=q, x1=a^-1, and x2=a^-1. I think I am having a problem when solving: pa^pq≡1(mod q) and qa^pq≡1(mod p) – Elisabeth Sep 26 '13 at 0:19
• It's too late for me to try to figure out what went wrong but when you know that $a^{pq} \equiv a \pmod{p}$ and $a^{pq}\equiv a \pmod{q}$, then you know that $a^{pq} \equiv a \pmod{\operatorname{lcm} (p,q)}$, even without CRT. – Daniel Fischer Sep 26 '13 at 0:24

$a^p \equiv a \pmod{p}$ by Fermat's little theorem but by hypothesis $a^q \equiv a\pmod{p}$, therefore

$$a^{pq} \equiv (a^p)^q \equiv a^p \equiv a \pmod{p}$$.

Do the same with the other one, and then use the CRT.

EDIT:

By doing the same to the other one you'll get:

$$a^{pq} \equiv (a^q)^p \equiv a^q \equiv a \pmod{q}$$

Now the CRT is useful here only when you want to conclude that $a^{pq} \equiv a \pmod{pq}$.

This is what the Chinese Remainder theorem says for the case of two congruence systems:

If we're looking for $x$ such that $x \equiv a \pmod{p}$ and $x \equiv b \pmod{q}$ for two distinct primes (or two coprime moduli) then the CRT asserts that such an $x$ exists and it is unique $\mod {pq}$.

Now in our case, you can use the CRT by thinking that both $a^{pq}$ and $a$ satisfy $x \equiv a \pmod{p}$ and $x \equiv a \pmod{q}$. So, by applying the uniqueness part of the CRT, we must have $a^{pq} \equiv a \pmod{pq}$.

I don't like this approach though. All you need to know is that the least common multiple of two relatively prime numbers is their product, then by using the definition of the least common multiple, you can say that if $p \mid a^{pq}-a$ and $q \mid a^{pq}-a$ then $pq \mid a^{pq}-a$ because $\operatorname{LCM}(p,q)=pq$. This one is a better approach I think.

• @ElisabethSimich: Does 'I get' mean that the problem has been solved or you still have a question about something that you get from the congruences? – user66733 Sep 26 '13 at 0:08
• Using CRT: I get a^pq ≡ p+q (mod pq). I am getting a1=a, a2=a, N1=p, N2=q, x1=a^-1, and x2=a^-1. I think I am having a problem when solving: pa^pq≡1(mod q) and qa^pq≡1(mod p) – Elisabeth Sep 26 '13 at 0:17
• @ElisabethSimich: See the edit. Do you know what $\operatorname{LCM}$ is and how it is defined in number theory and why we can use it to make life easier without applying the CRT? – user66733 Sep 26 '13 at 0:30
• @CalvinLin It is given that a^q ≡ a (mod p) – Elisabeth Sep 26 '13 at 0:31
• @ElisabethSimich: But you can also say that $a^q \equiv a \pmod{q}$ because of Fermat's little theorem. – user66733 Sep 26 '13 at 0:35