International Mathematics Competition
for University Students
2024

IMC2024: Day 2, Problem 10

Problem 10. We say that a square-free positive integer \(\displaystyle n\) is almost prime if

\(\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 square-free if it is not divisible by \(\displaystyle d^2\) for any integer \(\displaystyle d>1\).)

Tigran Hakobyan, Yerevan State University, Vanadzor, Armenia

Solution. We first prove the following claims.

Lemma. [1] If \(\displaystyle n\) is almost prime then \(\displaystyle \gcd(n,\varphi(n))=1\).

Proof. Assume to the contrary that \(\displaystyle \gcd(n,\varphi(n))>1\) so that there are primes \(\displaystyle p\) and \(\displaystyle q\) dividing \(\displaystyle n\) such that \(\displaystyle p\equiv 1(\text{mod}\ q)\). For \(\displaystyle 0\leq i\leq p-2\) let \(\displaystyle h_i\) be the number of positive divisors of \(\displaystyle n\) congruent to \(\displaystyle i\) modulo \(\displaystyle p-1\) and similarly for \(\displaystyle 0\leq j\leq q-1\) let \(\displaystyle \nu_j\) denote the number of positive divisors of \(\displaystyle n\) congruent to \(\displaystyle j\) modulo \(\displaystyle q\). Observe that the polynomial \(\displaystyle F_n(x)=x^{d_1}+x^{d_2}+...+x^{d_k}-kx\) defines the zero function on \(\displaystyle \mathbb{F}_p\) due to the condition of the problem. On the other hand, \(\displaystyle F_n(x)=(h_1-k)x+\sum_{i\neq 1}h_i x^i\) in \(\displaystyle \mathbb{F}_p[x]\), so that \(\displaystyle p|h_i\) for all \(\displaystyle 0\leq i\leq p-2, i\neq 1\). It follows that \(\displaystyle 2^{\omega(n)-1}=\nu_0=h_0+h_q+h_{2q}+...\equiv 0(\text{mod}\ p)\) which is a contradiction (here \(\displaystyle \omega(n)\) means the number of distinct prime divisors of \(\displaystyle n\)). Therefore our assumption was wrong and the lemma is proved. \(\displaystyle \Box\)

Lemma. [2] Let \(\displaystyle q\) be a prime number and let \(\displaystyle h\) be a positive integer coprime to \(\displaystyle q-1\). If \(\displaystyle l\) is the order of \(\displaystyle h\) modulo \(\displaystyle q-1\), then there exists \(\displaystyle a\in\mathbb{F}_q\) such that \(\displaystyle a^{h^l}=a\) and

\(\displaystyle a-a^h+a^{h^2}-...+(-1)^{l-1}a^{h^{l-1}}\neq 0\)

Proof. Observe that \(\displaystyle a^{h^l}=a\) for any \(\displaystyle a\in\mathbb{F}_q\) since \(\displaystyle q-1|h^l-1\). On the other hand, the numbers \(\displaystyle h^0,h^1,...,h^{l-1}\) leave different remainders upon division by \(\displaystyle q-1\) and therefore the polynomial

\(\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\)

Lemma. [3] If \(\displaystyle n\) is almost prime then for any primes \(\displaystyle p\) and \(\displaystyle q\) dividing \(\displaystyle n\), the order of \(\displaystyle p\) modulo \(\displaystyle q-1\) is an odd number.

Proof. Observe that due to Lemma 1 the order \(\displaystyle l\) of \(\displaystyle p\) modulo \(\displaystyle q-1\) is well defined and assume to the contrary that \(\displaystyle l\) is an even number. According to Lemma 2 there exists \(\displaystyle a\in\mathbb{F}_q\) such that \(\displaystyle a^{p^l}=a\) and \(\displaystyle f(a)\neq 0\), where \(\displaystyle f(x)=x-x^p+x^{p^2}-...+(-1)^{l-1}x^{p^{l-1}}\). Let us consider the sequence \(\displaystyle (a_i)_{i=0}^l\subset\mathbb{F}_q\) defined by \(\displaystyle a_0=a\) and \(\displaystyle a_{i+1}=-a^p_i\) for \(\displaystyle 0\leq i\leq l-1\). Notice that since \(\displaystyle l\) is even by the assumption, we have \(\displaystyle a_{l}=a^{p^l}_0=a_0\). It follows that

\(\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\)