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$

Question

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.

Answer 1

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

Answer 2

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.