2

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.

JMoravitz
  • 79,518
Tomas Smith
  • 145

1 Answers1

1

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.

André Nicolas
  • 507,029
  • Can you explain further why the conclusion follows from (3) and (4)? It looks like the Chinese Remainder Theorem. – Tomas Smith Nov 16 '15 at 03:59
  • 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 04:49