7
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Arthur Jan 25 '17 at 0:57
4
$\begingroup$

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$

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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?$$

$\endgroup$
0
$\begingroup$

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$

$\endgroup$

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.