# 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. – Arthur Jan 25 '17 at 0:57

Hint $$\$$ Apply the following simple generalization of the little Fermat-Euler 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\: p\!-\!1\:|\:e\!-\!1$$

Proof $$\ (\Leftarrow)\ \$$ Since a squarefree natural divides another iff all its prime factors do, we need only show $$\rm\:p\:|\:a^{\large e}\!-\!a\:$$ for each prime $$\rm\:p\:|\:n,\:$$ or, that $$\rm\:a \not\equiv 0\:\Rightarrow\: a^{\large e-1} \equiv 1\pmod p,\:$$ which, since $$\rm\:p\!-\!1\:|\:e\!-\!1,\:$$ follows from $$\rm\:a \not\equiv 0\:$$ $$\Rightarrow$$ $$\rm\: a^{\large p-1} \equiv 1 \pmod p,\:$$ by little Fermat.
$$(\Rightarrow)\ \$$ See this answer (not required 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$$

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$