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