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

Question

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 \begin{equation} a^{(p-1)(q-1)} \equiv 1 \pmod{n} \end{equation} 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.

Answer 1

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.

Answer 2

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

Answer 3

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