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

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

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.