# Fermat's Little Theorem Induction $a^{(p_1 -1)(p_2 -1)\dots(p_n -1)} \equiv 1 \pmod{M}$

Let $M = p_1 p_2 \cdots p_n$ be a positive integer with prime factorization. Let $\gcd(a,M) =1$.

Prove that $a^{(p_1 -1)(p_2 -1)\cdots(p_n -1)} \equiv 1 \pmod{M}$, by induction.

The base case is just Fermat's Little Theorem but I am unsure how to proceed.

• Is induction necessary ? The result is a direct multiplication of application of fermats theorem to each of the p i's – Shailesh Nov 16 '15 at 3:04
• I noticed that but the question says to use induction for some reason. – Tomas Smith Nov 16 '15 at 3:06

We assume that all primes mentioned are distinct. Let $M_n=p_1p_2\cdots p_n$, and let $M_{n+1}=p_1p_2\cdots p_np_{n+1}$. We want to prove the induction step. Given that for a certain $k$ we have $$a^{(p_1-1)(p_2-1)\cdots(p_k-1)}\equiv 1\pmod{M_k},\tag{1}$$ we want to conclude that $$a^{(p_1-1)(p_2-1)\cdots(p_k-1)(p_{k+1}-1)}\equiv 1\pmod{M_{k+1}}.\tag{2}$$ First note, by raising the left side of (1) to the $(p_{k+1}-1)$-th power, that $$a^{(p_1-1)(p_2-1)\cdots(p_k-1)(p_{k+1}-1)}\equiv 1\pmod{M_{k}}.\tag{3}$$ Note also that $a^{p_{k+1}-1}\equiv 1\pmod{p_{k+1}}$. Raising both sides to the power $(p_1-1)(p_2-1)\cdots(p_k-1)$ we conclude that $$a^{(p_1-1)(p_2-1)\cdots(p_k-1)(p_{k+1}-1)}\equiv 1\pmod{p_{k+1}}.\tag{4}$$ Finally, from (3) and (4), the desired conclusion follows, since $M_{k+1}=M_kp_{k+1}$ and $M_k$ and $p_{k+1}$ are relatively prime.
• Well, like the trivial (uniqueness) part of CRT, I would not call it CRT, the interesting part of which is existence. Let $x=a^{(p_1-1)\cdots(p_{k+1}-1)}$. By (3) we have $M_k$ divides $x-1$. By (4) we have $p_{k+1}$ divides $x-1$. Since they are relatively prime, their product $M_{k+1}$ divides $x-1$, which is what we want to show. – André Nicolas Nov 16 '15 at 4:49