For every positive odd integer $n$, do we have $n \mid 2^{n!}-1$?

Question

It is shown here on Math.SE that $ 2^n-1 \pmod n \not\equiv 0 $, for $n \geq 2$. Now I have checked some computations: for odd positive integers, I have got $n \mid 2^{n!}-1$ holds for some values of $n$. I have tried to use Fermat's little theorem but I can't show that. How can I prove that it is true for odd positive integers?

Answer 1

There is a slightly more general version of Fermat's little theorem:

Euler's Theorem

Let $\phi(n)$ be the number of integers $m$ such that $1\leq m<n$, and $\gcd(m,n)=1$, then $$a^{\phi(n)}\equiv_n 1$$ for any $a\in\Bbb Z_n$ with $\gcd(a,n)=1$

Notice first that $\phi(n)\leq n$, which means that $\phi(n)\mid n!$ so we can write $n!=k\phi(n)$. Since $\gcd(2,n)=1$ it therefore follows that $$(2^{\phi(n)})^k\equiv_n 1^k\equiv_n1\iff n\mid 2^{n!}-1$$

---

The proof of the theorem is quite beautiful. Look at all the units modulo $n$, that is $$\Bbb Z_n^\times=\{x_1,x_2,\dots,x_{\phi(n)}\}$$

There are precisely $\phi(n)$ such elements, since $x$ is a unit $\iff\gcd(x,n)=1$. Now, if we take any element $a\in\Bbb Z_n^\times$ and multiply it with every element in $\Bbb Z_n^\times$ we will still have the same elements. That is, $$\{ax_1,ax_2,\dots,ax_{\phi(n)}\}=\{x_1,x_2,\dots,x_{\phi(n)}\}$$ In particular $$(ax_1)(ax_2)\dots (ax_{\phi(n)})\equiv_n x_1x_2\dots x_{\phi(n)}$$ This gives us $$a^{\phi(n)}\equiv_n1$$ Notice in the special case when $n=p$ is prime, $\phi(p)=p-1$, which gives Fermat's little theorem.