Prove $n\mid \phi(2^n-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!

$(\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.

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