If $m$ is an odd natural number, show that $m\mid 2^{\phi(m)}-1,$ where $\phi$ is the Euler totient function.

Question

If $m$ is an odd natural number, show that $$m\mid 2^{\phi(m)}-1,$$ where $\phi$ is the Euler totient function.

---

Can someone provide me some hints.

Answer 1

The result you want to prove is a straight consequence of Euler's totient theorem. On a quick look at the theorem, you will find that:

If $n$ and $a$ are coprime positive integers, then

$${\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n}}}$$

Since $m$ is odd (i.e. not divisible by $2$) and $2$ is prime, $m$ and $2$ are coprime, and hence you can apply Euler's totient theorem here, without any hesitation.