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.
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.