Let $n$ be a positive whole number. Given $2^7 \equiv 2 \mod n$ and $3^7 \equiv 3 \mod n$, prove for all $a$ in $\mathbb{Z}$: $a^7 \equiv a \mod n$, without using a computer.

$n$ must be greater than 3 and less than $2^6=64$, so using a computer it is easy to verify that $n$ must be 6,7,14,21 or 42.


From the given congruences, $n$ is a common factor of $$\eqalign{ 2^7-2=2(2^3+1)(2^3-1)&=2\times3^2\times7\cr \hbox{and}\quad 3^7-3=3(3^3+1)(3^3-1)&=2^3\times3\times7\times13\ ,\qquad\cr}$$ so $n\mid 2\times3\times7$. Since for any $a$ we have $$\eqalign{ a^2\equiv a\pmod2\quad\Rightarrow\quad a^7\equiv(a^2)^3a\equiv a^4\pmod2\quad\Rightarrow\quad &a^7\equiv a\pmod2\cr a^3\equiv a\pmod3\quad\Rightarrow\quad a^7\equiv(a^3)^2a\equiv a^3\pmod3 \quad\Rightarrow\quad &a^7\equiv a\pmod3\cr &a^7\equiv a\pmod 7\ ,\cr}$$ it follows that $a^7\equiv a$ modulo any number which is a product of $2,3$ and $7$ at most once each. All the $n$ we are considering are of this form.


Using Fermat's Little Theorem,

$$a^7\equiv a\pmod7$$

$$a^7-a=a(a^6-1)=a(a-1)\{a^5+a^4+\cdots+a+1\}$$ where by Little Theorem, $\displaystyle2|a(a-1)$

$$a^7-a=a(a^6-1)=a(a^2-1)(a^4+a^2+1)=(a^3-a)(a^4+a^2+1)$$ where by Little Theorem, $\displaystyle3|(a^3-a)$

So, $\displaystyle a^7-a$ will be divisible by lcm$(2,3,7)$


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.