Prove $n\mid \phi(2^n-1)$
Solution 1:
Consider $U(2^n-1)$. Clearly $2\in U(2^n-1)$. It can also be shown easily that the order of $2$ in the group $U(2^n-1)$ is $n$. By Lagrange's theorem $|2|=n$ divides $|U(2^n-1)|=\phi(2^n-1)$.
Remark: Thank you for letting me know about this fact. It's interesting!
Solution 2:
$(\mathbb{Z}/\mathbb{(a^n-1)Z})^*$ is a group of order $\phi(a^n-1)$ and gcd$(a,a^n-1)=1\Rightarrow a\in (\mathbb{Z}/\mathbb{(a^n-1)Z})^*$
We have $a^n\equiv 1\mod (a^n-1)$ and $a^k-1<a^n-1$ when ever $k<n$ so there does not exist $k<n$ such that the above condition holds. So the order of $a$ in $(\mathbb{Z}/\mathbb{(a^n-1)Z})^*$ is $n$. And as the order of each element divides the order of the group so we have $n|\phi(a^n-1)$
Putting $a=2$ we have the required result asked in the question.
Solution 3:
Hint: Clearly $2$ has order $n$, modulo $2^n-1$.
Further Hint: We know that $2^{ \phi(2^n -1)} \equiv 1 \pmod{2^n-1}$.
Solution 4:
Observation. If $2^n-1\mid 2^k-1$ then $n \mid k$.
Proof. Let $2^n-1\mid 2^k-1$. Let $k=qn+r$ where $0\le r<n$. Then we get $$2^k-1=2^{qn+r}-1=2^{qn+r}-2^r+2^r-1=2^r(2^{qn}-1)+2^r-1.$$ Since $2^{qn}-1=(2^n-1)(2^{(q-1)n}+2^{(q-2)n}+\dots+2^n+1)$, we see that $2^n-1$ divides $2^{qn}-1$. Therefore $2^n-1$ also divides $$2^r-1 = 2^k-1 - 2^r(2^{qn}-1).$$ But $2^n-1 \mid 2^r-1$ with $0\le r<n$ is only possible if $r=0$. So we get that $k=qn$ and $n\mid k$.
From Euler's theorem we have $$2^{\varphi(2^n-1)}\equiv 1 \pmod{2^n-1},$$ i.e., $2^n-1 \mid 2^{\varphi(2^n-1)}-1$. (Notice that $\gcd(2,2^n-1)=1$, so Euler's theorem can be applied here.)
Using the above observation for $k=\varphi(2^n-1)$ we get $$n\mid \varphi(2^n-1).$$
Note: The same argument would work to show that $n\mid \varphi(a^n-1)$ for any $a\ge2$. Some posts about this more general question:
- $n\mid \phi(a^{n}-1)$ for any $a>n$?
- $n$ divides $\phi(a^n -1)$ where $a, n$ are positive integer.
- Prove that $n$ divides $\phi(a^n -1)$ where $a, n$ are positive integer without using concepts of abstract algebra