Prove by induction that, for all positive integers $n$ , if $\gcd(a,M_n)=1$ , then $a^{(p_1−1)(p_2−1)⋯(p_n−1)} \equiv 1 \pmod{M_n}$.

Question

Suppose $M_n=p_1×p_2×⋯×p_n$ where $p_1,…,p_n$ are distinct primes. Prove by induction that, for all positive integers $n$ , if $\gcd(a,M_n)=1$ , then $a^{(p_1−1)(p_2−1)⋯(p_n−1)} \equiv 1 \pmod{M_n}$..

I don't know how to connect the question with "induction". In other words, I've stuck by IC AND IH

Answer 1

First of all, I should mention that this is a particular case of the Euler's theorem, $\gcd(a,M_n)=1 \Rightarrow a^{\varphi(M_n)} \equiv 1 \pmod{M_n}$ and $\varphi(M_n) = (p_1−1)(p_2−1)⋯(p_n−1)$.

But, we are asked to use induction, so no shortcuts.

Case 1 (IC). $n=1$ which means $M_1=p_1$ or $M_1$ is a prime and $\gcd(a,M_1)=1$. This is Fermat's little theorem or $a^{p_1-1} \equiv 1 \pmod{p_1}$ which is the same as $a^{p_1-1} \equiv 1 \pmod{M_1}$. This case is covered.

Case 2 (IH). Let's assume the statement is true for a fixed $k$, i.e. for any $M_k$ such that $\gcd(a,M_k)=1$ and $M_k=p_1p_2⋯p_k$ product of $k$ distinct prime numbers $\Rightarrow a^{(p_1−1)(p_2−1)⋯(p_k−1)} \equiv 1 \pmod{M_k}$.

Now we should prove the statement is also true for $M_{k+1}$ such that $\gcd(a,M_{k+1})=1$ and $M_{k}=p_1p_2⋯p_{k+1}$ product of $k+1$ distinct prime numbers.

Let's split $M_{k+1}=M_{k}\cdot p_{k+1}$. Because $\gcd(a,M_{k+1})=1 \Rightarrow \gcd(a,M_{k})=1$ too and from the hypothesis $$a^{(p_1−1)(p_2−1)⋯(p_k−1)} \equiv 1 \pmod{M_k}$$ and $$a^{(p_1−1)(p_2−1)⋯(p_k−1)(p_{k+1}-1)} \equiv 1^{p_{k+1}-1} \equiv 1 \pmod{M_k}$$ Because $\gcd(a,M_{k+1})=1$, then $\gcd(a,p_{k+1})=1$ and $\gcd(a^{(p_1−1)(p_2−1)⋯(p_k−1)} ,p_{k+1})=1$. And using Fermat's little threorem $$\left(a^{(p_1−1)(p_2−1)⋯(p_k−1)}\right)^{p_{k+1}-1} \equiv 1 \pmod{p_{k+1}}$$ Altogether: $$a^{(p_1−1)(p_2−1)⋯(p_k−1)(p_{k+1}-1)} \equiv 1\pmod{M_k}$$ $$a^{(p_1−1)(p_2−1)⋯(p_k−1)(p_{k+1}-1)} \equiv 1 \pmod{p_{k+1}}$$ Given $\gcd(M_k,p_{k+1})=1$ and

• $M_k|\left(a^{(p_1−1)(p_2−1)⋯(p_k−1)(p_{k+1}-1)}−1 \right)$ and
• $p_{k+1}|\left(a^{(p_1−1)(p_2−1)⋯(p_k−1)(p_{k+1}-1)}−1 \right)$

or $M_k\cdot Q_1=p_{k+1}\cdot Q_2=a^{(p_1−1)(p_2−1)⋯(p_k−1)(p_{k+1}-1)}−1$, for some integers $Q_1, Q2$, leading to $p_{k+1}|Q_1$, we have: $$a^{(p_1−1)(p_2−1)⋯(p_k−1)(p_{k+1}-1)} \equiv 1 \pmod{M_kp_{k+1}}$$ which is $$a^{(p_1−1)(p_2−1)⋯(p_k−1)(p_{k+1}-1)} \equiv 1 \pmod{M_{k+1}}$$ And we proved the statement for $k+1$ assuming it's true for $k$.