| |||||||||||||||

## IMC2024: Day 2, Problem 10
\(\displaystyle n \mid x^{d_1}+x^{d_2}+...+x^{d_k}-kx \) for all integers \(\displaystyle x\), where \(\displaystyle 1=d_1<d_2<...<d_k=n\) are all the positive divisors of \(\displaystyle n\). Suppose that \(\displaystyle r\) is a Fermat prime (i.e., it is a prime of the form \(\displaystyle 2^{2^m}+1\) for an integer \(\displaystyle m\geq 0\)), \(\displaystyle p\) is a prime divisor of an almost prime integer \(\displaystyle n\), and \(\displaystyle p\equiv 1\ (\mathrm{mod}\ r)\). Show that, with the above notation, \(\displaystyle d_i\equiv 1\ (\mathrm{mod}\ r)\) for all \(\displaystyle 1\leq i\leq k\). (An integer \(\displaystyle n\) is called Tigran Hakobyan, Yerevan State University, Vanadzor, Armenia
\(\displaystyle a-a^h+a^{h^2}-...+(-1)^{l-1}a^{h^{l-1}}\neq 0\)
\(\displaystyle f(x)=x-x^h+x^{h^2}-...+(-1)^{l-1}x^{h^{l-1}}\) defines a function on \(\displaystyle \mathbb{F}_q\), which is not identically zero. Hence the existence of an element with the required properties is proved. \(\displaystyle \Box\)
\(\displaystyle \sum_{i=0}^{l-1}\sum_{d|n}a^d_i=\sum_{i=0}^{l-1}\left(\sum_{d|\frac{n}{p}}a^d_i+\sum_{d|\frac{n}{p}}a^{pd}_i\right)=\sum_{i=0}^{l-1}\sum_{d|\frac{n}{p}}\left(a^d_{i+1}+a^{pd}_i\right)=0,\) since \(\displaystyle d\) is always odd being a divisor of \(\displaystyle n\) (Recall that \(\displaystyle \gcd(n,\varphi(n))=1\) due to Lemma 1, so that \(\displaystyle n\) is odd, except the trivial case \(\displaystyle n=2\)), and \(\displaystyle a_{i+1}=-a^p_i\) for all \(\displaystyle 0\leq i\leq l-1\). On the other hand, according to the condition of the problem, \(\displaystyle \sum_{d|n}a^d_i=ka_i\) in \(\displaystyle \mathbb{F}_q\) for all \(\displaystyle i\), which shows that \(\displaystyle kf(a)=k\sum_{i=0}^{l-1}a_i=\sum_{i=0}^{l-1}ka_i=\sum_{i=0}^{l-1}\sum_{d|n}a^d_i=0\) in \(\displaystyle \mathbb{F}_q\) which is impossible, since \(\displaystyle f(a)\neq 0\) by construction and \(\displaystyle k=2^{\omega(n)-1}\) is coprime to \(\displaystyle q\). The attained contradiction shows that our assumption was wrong and concludes the proof of the lemma. \(\displaystyle \Box\) Let us get back to the problem. Suppose that \(\displaystyle p|n\) is prime and \(\displaystyle r=2^{2^m}+1\) is a Fermat's prime such that \(\displaystyle p\equiv 1(\text{mod}\ r)\). If \(\displaystyle q\) is any prime divisor of \(\displaystyle n\), then by Lemma 3 we have that \(\displaystyle q^l\equiv 1(\text{mod}\ p-1)\) for some odd \(\displaystyle l\), so that \(\displaystyle q^l\equiv 1(\text{mod}\ r)\) and therefore \(\displaystyle q=q^{\gcd(l,r-1)}\equiv 1(\text{mod}\ r)\). Hence \(\displaystyle d\equiv 1(\text{mod}\ r)\) for any divisor \(\displaystyle d\) of \(\displaystyle n\). \(\displaystyle \Box\) | |||||||||||||||

© IMC |