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.

  • $\begingroup$ Is it given that m is odd otherwise $2^n\equiv-1\pmod n\ne(-2)^n\equiv1\pmod n$? $\endgroup$ – 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.


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.