Prove that for any even positive integer $n$, $n^2-1 \mid 2^{n!}-1$

Question

Prove that for any even positive integer $n$, $n^2-1 \mid 2^{n!}-1$

This is from a book. They have given the proof. But I didn't understand it well. I am looking for a simpler proof. Or it will be helpful if someone explain this a little bit more -
Proof: Let $m = n+1$ then we need to prove that $m(m-2) \mid 2^{(m-1)!}-1$. Because of $\phi(m) \mid (m-1)!$, we have $2^{\phi(m)} -1 \mid 2^{(m-1)!} -1$. And from Euler's theorem, $(m-2) \mid 2^{(m-1)!}-1$. Because $m$ is odd, $gcd(m,m-2)=1$ and the conclusion follows.

Answer 1

Step 1: $\phi(m) |(m-1)!$

This is easy, since $\phi(m) \leq m-1$ therefore, it is one of the terms appearing in $(m-1)!$.

Step 2: If $a|b$ then $2^a-1|2^b-1$.

This follows from the fact that $b=ak$ and $$x^k-1=(x-1)(1+x+x^2+..+x^{k-1})$$ Replace $x$ by $2^a$.

Step 3: $2^{\phi(m)} -1 \mid 2^{(m-1)!} -1$.

Follows now from step 1 and step 2.

Step 4: $m|2^{\phi(m)}-1$

This is just the Euler Theorem.

Step 5: $m| 2^{(m-1)!} -1$

Comes from step 3 and step 4.

Step 6: $m-2|2^{(m-1)!} -1$.

Since Step 5 holds for all integers, it holds if we replace $m$ by $m-2$. Therefore $$m-2| 2^{(m-3)!} -1$$

By Step 3, $2^{(m-3)!} -1|2^{(m-1)!} -1$.

Step 7: If $a|c, b|c$ and $gcd(a,b)=1$ then $ab|c$.

Setting $a=m, b=m-2$ and $c=2^{(m-1)!}-1$ you get the claim.

This is a standard result in number theory, which can be viewed via prime factrisation or Extended Euclid algorithm.

Answer 2

I have a shorter proof, because $n$ is even then $n^2-1$ is odd and $\gcd(n^2-1,2)=1$, thus according to Euler's theorem $$2^{\varphi(n^2-1)}\equiv 1 \pmod{n^2-1}$$ But totient function is multiplicative and $\gcd(n-1,n+1)=1$ or $$\varphi(n^2-1)=\varphi(n+1)\cdot \varphi(n-1)\leq n\cdot (n-2)<n!$$ or $n!=\varphi(n^2-1)\cdot Q, Q \in \mathbb{N}$ and $$2^{n!} \equiv 2^{\varphi(n^2-1)\cdot Q} \equiv 1^{Q} \equiv 1 \pmod{n^2-1}$$

Answer 3

$2\,$ is coprime to $\,n\!+\!1\,$ so $\,{\rm mod}\ n\!+\!1\!:\, $ $\,2$ has order $\le n,\,$ i.e. $\,\color{#c00}{2^{\large k}\! \equiv 1}\,$ for $\,k\le n,\,$ thus $\,k\mid n!\:$ hence $\,2^{\large n!}\!\equiv (\color{#c00}{2^{\large k}})^{\large n!/k}\!\equiv 1.\,$ Similarly $\,2^{\large n!}\!\equiv 1\pmod{\!n\!-\!1}.$ Thus $\,2^{\large n!}\!-1\,$ is divisible by $\,n\!+\!1\,$ and $\,n\!-\!1\,$ hence also by their lcm = product, since $\:\gcd(n\!+\!1,n\!-\!1) = \gcd(n\!+\!1,2) = 1,\,$ by $n$ even.