Switzerland competition problems

Solution:
We induct on $n$. The cases $n=1,2,3$ can easily be checked by hand:
- $n=1: 2^{2} \mid 32 \cdot 2$.
- $n=2: 2^{6} \mid 2^{5} \cdot \varphi(15)=2^{5} \cdot 2 \cdot 2^{3}$
- $n=3: 2^{12} \mid 2^{5} \cdot \varphi(255)=2^{5} \cdot 2 \cdot 2^{2} \cdot 2^{4}=2^{12}$

For $n \geq 4$ assume the statement is true for all $1 \leq k < n$ and note that
$$\varphi\left(2^{2^{n}}-1\right)=\varphi\left(\left(2^{2^{n-1}}-1\right)\left(2^{2^{n-1}}+1\right)\right)=\varphi\left(2^{2^{n-1}}-1\right) \cdot \varphi\left(2^{2^{n-1}}+1\right)$$
since $\gcd\left(2^{2^{n-1}}-1,2^{2^{n-1}}+1\right)=1$. But from our inductive assumption we know that
$$2^{(n-1) n} \mid 32 \cdot \varphi\left(2^{2^{n-1}}-1\right)$$
so all that is left to prove is that
$$2^{2 n} \mid \varphi\left(2^{2^{n-1}}+1\right)$$
Take now any prime $p$ that divides $2^{2^{n-1}}+1$ and let $d$ be the order of $2 \bmod p$. We know that
$$2^{2^{n-1}} \equiv -1 \bmod p, \text{ squaring gives } 2^{2^{n}} \equiv 1 \bmod p$$
By the properties of the order we therefore have
$$d \mid 2^{n} \text{ but } d \nmid 2^{n-1}$$
This implies $d=2^{n}$ and since we also have $d \mid p-1$ we get
$$2^{n} \mid p-1 \text{ and therefore } p \equiv 1 \bmod 2^{n}$$
If we are also able to prove that $2^{2^{n-1}}+1$ contains at least two different prime factors we would be done. This is because if $p, q$ are two different such primes we can write
$$2^{2^{n-1}}+1=p^{x} \cdot q^{y} \cdot N$$
with $N$ a positive integer and $p, q \nmid N$. Then
$$\varphi\left(2^{2^{n-1}}+1\right)=(p-1)(q-1) \cdot p^{x-1} q^{y-1} \varphi(N) \equiv 0 \bmod 2^{2 n}$$
Assume now that $2^{2^{n-1}}+1$ is instead a prime power, say $p^{x}$. It follows that
$$(p-1)\left(p^{x-1}+p^{x-2}+\ldots+p+1\right)=p^{x}-1=2^{2^{n-1}}$$
It follows that $x$ is odd since squares are $\equiv 0$ or $1 \bmod 4$ and using the fact that $p \equiv 1 \bmod 2^{n}$ we find
$$p^{x-1}+p^{x-2}+\ldots+p+1 \equiv x \bmod 2^{n}$$
implying $x=1$. But then $2^{2^{n-1}}+1$ is a prime and
$$\varphi\left(2^{2^{n-1}}+1\right)=2^{2^{n-1}}$$
and since $n \geq 4$ we have $2^{n-1} \geq 2 n$ and we are done in this case as well.