Show that $a^{(p-1)(q-1)} \equiv 1 \pmod{n}$

Let $p$ and $q$ be two different prime numbers, and $n = p \cdot q$. Let $a$ be a number relative prime to $n$. Use Fermat's little theorem and the Chinese remainder theorem to show that $$a^{(p-1)(q-1)} \equiv 1 \pmod{n}$$ By the Chinese remainder theorem I can write this as the system of linear congruences \begin{align*} \begin{cases} a^{(p-1)(q-1)} \equiv 1 \pmod{p} \\ a^{(p-1)(q-1)} \equiv 1 \pmod{q} \end{cases} \end{align*} Assuming that the inverse is simply 1 in both cases, that yields the solution \begin{align*} x \equiv a^{(p-1)(q-1)}(q+p) \pmod n \end{align*} Fermat's little theorem gives that \begin{align*} a^{p-1} \equiv 1 \pmod p \\ a^{q-1} \equiv 1 \pmod q \\ \end{align*} I don't really understand how to combine these to get the desired result.

• In my course we called it the Little Fermat improved theorem ! There is a hidden Gauss lemma in other proofs ;) – Maman Oct 6 '16 at 17:46

3 Answers

So close! Just raise the first equation to the power of $q-1$ and raise the second equation to the power of $p-1$. Now, you can apply the Chinese Remainder Theorem.

• Thanks! I felt like I was very close, but I just couldn't see the it. – SBS Oct 6 '16 at 17:37

Note that $\phi(n) = \phi(pq) = \phi(p)\phi(q) = (p-1)(q-1)$, where $\phi$ is the Euler Totient Function. Also we know that whenever $(a,n) = 1$

$$a^{\phi(n)} \equiv 1 \pmod n$$

• I know, but I don't think I was supposed to use the Euler Theorem since we haven't learned about that yet. – SBS Oct 6 '16 at 17:36

Given, $p$, $q$ are prime, $\phi(pq)=(p-1)(q-1)$ because every integer less or equal to a prime is relatively prime with that integer. Therefore, $\phi(p)=(p-1)$ and since it is $\phi$ is multiplicative, $\phi(pq)=(p-1)(q-1)$. Euler's theorem states that $a^{ϕ(n)}≡1 (mod n)$, when $(a,n)=1$. Therefore, $a^{(p-1)(q-1)}≡1 (mod n)$.

• This is a very funny site, it supports latex formulas! Look, how well your answer looks now. I edited it! – peterh Mar 17 '18 at 19:07