Show that $a^{61} \equiv a\pmod{1001}$ for every $a \in \mathbb{N}$

Solution 1:

Hint $\ $ Apply the following simple generalization of the little Fermat & Euler phi theorem. Since $\rm\:n = 1001 = \color{#C00}7\cdot\color{#0A0}{11}\cdot\color{brown}{13},\:$ is squarefree, it suffices to check $\rm\:\color{#C00}6,\color{#0A0}{10},\color{brown}{12}\:|\:61\!-\!1 = e\!-\!1.$

Theorem $\ $ For natural numbers $\rm\:a,e,n\:$ with $\rm\:e,n>1$

$\qquad\rm n\:|\:a^{\large e}-a\:$ for all $\rm\:a\:\iff n\:$ is squarefree, and prime $\rm\:p\:|\:n\:\Rightarrow\: \color{#0a0}{p\!-\!1\mid e\!-\!1}$

Proof $\ (\Leftarrow)\ $ By unique prime factorization (or Euclid's Lemma), a squarefree natural divides another iff all its prime factors do, so we need only show $\rm\:p\:|\:a^{\large e}\!-\!a\:$ for each prime $\rm\:p\:|\:n.\:$ It's clear if $\rm\,p \mid a.\,$ Else $\rm\!\bmod p\!:\ a \not\equiv 0\,$ $\rm\overset{\rm Fermat}\Longrightarrow\, \color{c00}{a^{\large\color{#0a0}{p-1}} \equiv 1}$ so $\rm\,\color{#c00}{a^{\large\color{#0a0}{e-1}}\equiv 1}\,$ by $\rm \,\color{#0a0}{p\!-\!1\mid e\!-\!1}\,$ and modular order reduction. Thus $\rm\,a^{\large e}-a\equiv a(\color{#c00}{a^{\large\color{#0a0}{e-1}}-1})\equiv a(\color{#c00}0)\equiv 0$. $\ \ (\Rightarrow)\ \ $ See here (not used here).

Corollary $\rm\,\ n\mid a^e b - a b^f\ $ if $\,\rm n\:$ is squarefree, and prime $\rm\:p\:|\:n\:\Rightarrow\: p\!-\!1\:|\:e\!-\!1,\,f\!-\!1$

Proof $\ $ By the Theorem $\rm\bmod n\!:\,\ a^e\equiv a,\, b^f\equiv b\,$ so $\rm\,a^e b - ab^f\equiv ab-ab\equiv 0$

Corollary' $\ n\mid f(a^{e_1},b^{e_2}) - f(a^{e_3},b^{e_4})\,$ if $\,n\,$ is squarefree, and prime $\,p\:|\:n\:\Rightarrow\: p\!-\!1\:|\:e_i\!-\!1\,$ and $\,f(x,y)\in\Bbb Z[x,y],\,$ i.e. $\,f\,$ is a polynomial in $\,x,y\,$ with integer coefficients.

Proof $\ $ By the Theorem $\bmod n\!:\,\ a^{e_i}\equiv a,\, b^{e_i}\equiv b\,$ so $f(a^{e_i},b^{e_i}) \equiv f(a,b)\,$ by the Polynomial Congruence Rule.