Let $\varphi$ denote the Euler phi-function. Prove that for every positive integer $n$ $$2^{n(n+1)} | 32 \cdot \varphi \left( 2^{2^n} - 1 \right).$$
Problem
Source: Swiss Final Round 2020 First Exam Problem 4
Tags: number theory, Euler, totient function, function
02.03.2020 00:46
Where did you get these problems? Btw this is easy by induction using the multiplicity of phi funciton. We just need to prove $2^{2n}|\phi(2^{2^{n-1}}+1)$. That's trivial though. If $2^{2^{n-1}}+1$ is a prime I am done. If It is not then it was at least $2$ different prime divisors (Mihailescu) both of which do this: $ord_p(2)|2^n$ $ord_p(2) |x 2^{n-1}$. Hence, $2^n=ord_p(2)|p-1$ etc
02.03.2020 00:51
02.03.2020 13:35
We can in fact do better for larger $n$. We will consider the case $n > 4$. Note that $\varphi \left( 2^{2^n} - 1 \right) = \prod_{i=0}^{n-1} \varphi \left( 2^{2^i} + 1 \right)$ as $\varphi$ is multiplicative and $\gcd(2^{2^i} + 1, 2^{2^j} + 1) > 1$ iff $i = j$. Now note that, by Lucas' theorem, for $n \ge 1$, any prime divisor of $2^{2^n} + 1$ is $1$ modulo $2^{n+2}$. Consider $n \ge 4$. If $2^{2^n} + 1$ is prime, then $p$ is $1$ modulo $2^{2^n}$, and $2^n \ge 2n+4$, so $p$ is $1$ modulo $2^{2n+4}$. Otherwise, we have at least $2$ prime divisors, and they are both $1$ modulo $2^{n+2}$, so $2^{2n+4}$ divides $\varphi (2^{2^n} + 1)$. So $\varphi \left( 2^{2^n} - 1 \right) = \prod_{i=0}^{3} \varphi \left( 2^{2^i} + 1 \right) \prod_{i=4}^{n-1} \varphi \left( 2^{2^i} + 1 \right)$ The first term on the left is $2 \cdot 4 \cdot 16 \cdot 256$ and the second term is divisible by $\prod_{i=1}^{n-4} 2^{2i+10}$, which is $2^{(n-3)(n-4) + 10(n-4)} = 2^{n^2 + 3n - 28}$. So the whole thing is divisible by $2^{n^2 + 3n - 13}$ for $n > 4$ which is better than the given divisibility for $n > 4$.
23.05.2020 18:31
i have very nice proof for this: use induction for solving this problem . (suppose problem for $n-1$ be true) $2^{n(n+1)} | 32 . \phi ( 2^{2^n} - 1 )$$=32 . \phi (2^{2^{n-1}}-1) \phi (2^{2^{n-1}}+1)$ so if we have : $2^{2n}|\phi (2^{2^{n-1}}+1)$ problem obvious. claim1: all the prime divisor of $ 2^{2^{n-1}}+1$ in form $4k+1$ proof without word: $if : p=4k+3 ,p|a^2+1 \implies p|1$ contradiction. claim 2: $2^{2^{n-1}}+1$ have atleast $n$ prime divisor. proof: in fact $2^{2^{n-1}}=( 2^{2^{n-2}}+1)(2^{2^{n-3}}+1)... $ it means on $2^{2^{n-1}}$ at least we have $n$ different prime divisor also notice that all of the prime divisor in for $4k+1$ and $(p_1-1)(p_2-1)....(p_n-1)| \phi (2^{2^{n-1}}+1)$ done!
29.12.2021 22:00
Induction and Zsigmondy theorem