2
$\begingroup$

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.

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

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.