# If $n$ is an odd positive integer, then $2^{n!} − 1$ is divisible by $n$

Prove that if $n$ is an odd positive integer, then $2^{n!} − 1$ is divisible by $n$.

Progress so far: Let $n=2k+1$. The desired result becomes $2^{(2k+1)!} − 1$ By Euler's totient function theorem, we have that

$2^{\phi(2k+1)}=1\mod(2k+1).$ I cannot seem to rigorously prove that this is true also for $(2k+1)!.$

• Well...$\varphi(n)<n$, clearly. Hence $\varphi(n) \,|\,n!$. – lulu Oct 19 '17 at 23:09
• The above hint should be sufficient to write an answer. If you are convinced, then please attempt an answer below. – Teresa Lisbon Oct 19 '17 at 23:18
• Is this the case because now we have that $2^{k\phi(n)}=1\mod(n)$? – mathcounter Oct 19 '17 at 23:30

## 1 Answer

If $n=\prod\limits_{i=1}^rp_i^{e_i}$, then $\;\varphi(n)=\prod_{i=1}^rp_i^{e_i-1}(p_i - 1)\;$ is clearly a divisor of $n!$ since each of its factors is less than $n$ and they're all distinct, so $$2^{n!}=\bigl(2^{\varphi(n)} \bigr)^{\tfrac{n!}{\varphi(n)}}\equiv 1\mod n$$ by Euler's theorem.