# A simpler proof that if $m \mid 2^n+1$, then $m \mid 2^m+1$

Prove that if $n=q^{v_q(n)}\cdot m$, where $q$ is the largest prime disivor of $n$ and $n \mid 2^n+1$, then $m \mid 2^m+1$.

The proof I known goes as follows:

Let $d=\text{ord}_m(-2)$ (that is, $d$ is the smallest number such that $(-2)^d\equiv 1\pmod m$). Then we have that if $(-2)^l\equiv 1\pmod m$, then $d \mid l$. And so, as $n \mid 2^n+1$, we have that $d \mid n$. It is well-known that $\text{ord}_m(-2) \mid \phi(m)$ ($\phi$ is Euler's totient function), and so $d \mid \phi(m)$, but $\phi(m)$ is relatively prime to $q^{v_q(n)}$. It follows that $\gcd (q^{v_q(n)}, d)=1$. And, as $d \mid n=q^{v_q(n)}\cdot m$, we have that $d \mid m$, and that means that $(-2)^m\equiv 1\pmod m$, which concludes the proof.

My question: is there any simpler proof? (in particular, one that doesn't employ Euler's totient function which I think is not really necessary here.)

Any ideas welcome.

• Is it given that m is odd otherwise $2^n\equiv-1\pmod n\ne(-2)^n\equiv1\pmod n$? – user5389726598465 May 2 at 1:43

That's about as simple as it gets. The presentation obfuscates the key idea, which is simply that we can cancel out primes $q$ that we know are coprime to the order, namely
Lemma  If the prime $\color{#c00}{q\rm\,\ exceeds\,}$ every prime factor of $\phi$ then $\,a^{\large \phi}\equiv 1\equiv a^{\large m\,q^{\Large k}}\!\Rightarrow\,a^{\large m}\equiv 1$
Proof $\ {\rm ord}(a):= d\mid \phi$ so $d$ is $\,\color{#c00}{\rm coprime\ to}\ q$ so coprime to $q^k.\,$ Thus $\,d\mid m q^k\Rightarrow\, d\mid m,\,$ so $\,a^m\equiv 1$
Remark  More generally $\,a^{\large \phi}\equiv 1\equiv a^{\large n}\,\Rightarrow\, a^{\large (\phi,n)}\equiv 1\$ since $\,d\mid \phi,n\,\Rightarrow\, d\mid (\phi,n).\,$ Hence the Lemma boils down to the gcd property $\,(\phi,m q^k) = (\phi,m)\,$ if $\,(\phi,q)=1,\,$ i.e. we can cancel from gcds any prime $q$ not occurring in some argument.