<s>[INST] 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.
 [/INST] 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.
</s>