Peter wrote: Let $n$ be an integer with $n \ge 2$. Show that $\phi(2^{n}-1)$ is divisible by $n$. By Euler's theorem we have that $(2^n-1)|2^{\phi(2^n-1)}-1$ so $n|\phi(2^n-1)$, because $gcd(2^a-1;2^b-1)=2^{gcd(a;b)}-1$.

Peter wrote: Let $ n$ be an integer with $ n \ge 2$. Show that $ \phi(2^{n}-1)$ is divisible by $ n$. This is also a good example of a cute application of oder. Recall that [Definition] Let $ n>1$ and $ gcd(a,n)=1$. The order of $ a$ modulo $ M$ is the smallest positive integer $ i$ such that $ a^{i}\equiv 1 (mod \; M)$. It is not difficult to check that [Proposition] Let the integer $ a$ have order $ k$ modulo $ N$. Then $ a^{h}\equiv 1 \; (mod \;M)$ if and only if $ k \; \vert \; h$; in particular $ k \; \vert \; \phi(M)$. Here goes the solution. It is trivial that $ gcd(2^{n}-1,2)=1$. We have two observations: First thing is that $ Min \{ i \in \mathbf{Z}_{>0}\; \vert \; 2^{i}\equiv 1 (mod \; 2^{n}-1) \}=n$, which means that the order of $ 2$ modulo $ 2^{n}-1$ is $ n$. Second, by Euler's theorem, we obtain $ 2^{\phi( 2^{n}-1)}\equiv 1 (mod \; 2^{n}-1)$. Using the above proposition, we now conclude that $ n \vert \phi( 2^{n}-1)$.

More general: $n|\varphi(a^n-b^n)$ for all $a>b$. Similar: $n|\varphi(a^n+b^n)$ and $n|\varphi(\frac{a^n-b^n}{a-b})$. The latter kills http://www.problem-solving.be/pen/viewtopic.php?t=358 , too.

Euler theorem (Phi function)