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.
 A: 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.
A: 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.
A: 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?$$
A: 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$
