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

I'm asked to show that $$a^{61} \equiv a\pmod{1001}$$ for every $$a \in \mathbb{N}$$. I've tried to tackle this using Fermat's Little Theorem and Euler's Theorem, but I can't even get started. My main problem seems to be the "for every $$a \in \mathbb{N}$$" part, because if it restricted $$\gcd(a, 1001) = 1$$ I would be able to factor out 1001 and try to show that it's factors divide $$a^{61} - a$$. I'm kinda lost here. Any help is appreciated.

• Note that Fermat's little theorem, while usually stated in terms of $a^{p-1}\equiv 1$ and with the condition $\gcd(a,p)=1$, may just as well be stated as $a^p\equiv a$ without the coprime condition. I think that will make it easier to see why that condition is not needed here either. Jan 25, 2017 at 0:57

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.

Which version of Fermat's Little Theorem are you using? If you use

Theorem. Let $p$ be prime. Then $a^p\equiv a\pmod p$ for every integer $a$

you should find the problem works out quite simply. (Use a factorisation of $1001$, as you suggested.)

You can regard the above result as an alternative statement of Fermat's Little Theorem, or as a corollary of Fermat's Little Theorem.

HINT.-$$\begin{cases}a^{61}=(a^7)^8\cdot a^5\equiv a^8\cdot a^5\equiv a^7\equiv a\mod7\\a^{61}=(a^{11})^5\cdot a^6\equiv a^ {11}\equiv a\mod 11\\a^{61}=(a^{13})^4\cdot a^9\equiv a^{13}\equiv a\mod13\end{cases}$$

Thus $$a^{61}-a=7m_1=11m_2=13m_3\Rightarrow?$$

The smallest positive integer greater than $k$ such that $a^k \equiv 1 \bmod n$ for all $a$ coprime to $n$ is given by the charmicael lambda function. It is easy to caclulate it, as explained in this wikipedia page.

In the case in which $n$ is square free, $\lambda(n)+1$ is the smallest number such that $a^{\lambda(n)}\equiv a \bmod n$ for all $a$. We have that $\lambda(10001)+1=61$