Use Fermat’s Theorem to prove Euler’s Theorem in the case m = pq. with p and q being two distinct prime numbers

Question

If $p$ is a prime and $p$ does not divide $a$, then $$a^{p-1} \equiv 1 \pmod{p}.$$ Since $p$ is prime, the fact that $p$ does not divide a means that $a$ and $p$ are relatively prime. Also, $\varphi(p) = p-1$ Thus, Fermat’s Theorem follows from Euler’s Theorem

I'm just stuck on what to do at this point any tips?

Answer 1

Let $p,q \in \mathbb{P}$, and $a \in \mathbb{N}^*$

Suppose that $\gcd(a, pq) = 1$, Let proof that $a^{(p-1)(q-1)} \equiv 1 \pmod{pq}.$

Using Fermat theoreme we have :

$$\left\{ \begin{array}{cl} a^{p-1} \equiv 1 \pmod{p} & \\ a^{q-1} \equiv 1 \pmod{q} & \end{array} \right.$$

Then :

$$\left\{ \begin{array}{cl} a^{(p-1)(q-1)} \equiv 1 \pmod{p} & \\ a^{(q-1)(p-1)} \equiv 1 \pmod{q} & \end{array} \right.$$

We have $\gcd(p,q) = 1$ Then $pq$ divide $a^{(p-1)(q-1)} - 1$ and that complete the proof.