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$

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.

• – lhf Jun 6 '14 at 12:09
• Why can't n=3 again? – snulty Jun 6 '14 at 12:59

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.
$$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)$