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?
 A: $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.
