IMC 2024 · Day 2 · P10

We first prove the following claims.

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

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

Lemma 2. Let $q$ be a prime number and let $h$ be a positive integer coprime to $q - 1$. If $l$ is the order of $h$ modulo $q - 1$, then there exists $a \in \mathbb{F}_q$ such that $a^{h^l} = a$ and $$a - a^h + a^{h^2} - \dots + (-1)^{l-1} a^{h^{l-1}} \ne 0$$ Proof. Observe that $a^{h^l} = a$ for any $a \in \mathbb{F}_q$ since $q - 1 \mid h^l - 1$. On the other hand, the numbers $h^0, h^1, \dots, h^{l-1}$ leave different remainders upon division by $q - 1$ and therefore the polynomial $$f(x) = x - x^h + x^{h^2} - \dots + (-1)^{l-1} x^{h^{l-1}}$$ defines a function on $\mathbb{F}_q$, which is not identically zero. Hence the existence of an element with the required properties is proved. $\square$

Lemma 3. If $n$ is almost prime then for any primes $p$ and $q$ dividing $n$, the order of $p$ modulo $q - 1$ is an odd number.

Proof. Observe that due to Lemma 1 the order $l$ of $p$ modulo $q - 1$ is well defined and assume to the contrary that $l$ is an even number. According to Lemma 2 there exists $a \in \mathbb{F}_q$ such that $a^{p^l} = a$ and $f(a) \ne 0$, where $f(x) = x - x^p + x^{p^2} - \dots + (-1)^{l-1} x^{p^{l-1}}$. Let us consider the sequence $(a_i)_{i=0}^{l} \subset \mathbb{F}_q$ defined by $a_0 = a$ and $a_{i+1} = -a_i^p$ for $0 \le i \le l-1$. Notice that since $l$ is even by the assumption, we have $a_l = a_0^{p^l} = a_0$. It follows that $$\sum_{i=0}^{l-1} \sum_{d \mid n} a_i^d = \sum_{i=0}^{l-1} \left( \sum_{d \mid \frac{n}{p}} a_i^d + \sum_{d \mid \frac{n}{p}} a_i^{pd} \right) = \sum_{i=0}^{l-1} \sum_{d \mid \frac{n}{p}} \bigl( a_{i+1}^d + a_i^{pd} \bigr) = 0,$$ since $d$ is always odd being a divisor of $n$ (Recall that $\gcd(n, \varphi(n)) = 1$ due to Lemma 1, so that $n$ is odd, except the trivial case $n = 2$), and $a_{i+1} = -a_i^p$ for all $0 \le i \le l-1$. On the other hand, according to the condition of the problem, $\sum_{d \mid n} a_i^d = k a_i$ in $\mathbb{F}_q$ for all $i$, which shows that $$k f(a) = k \sum_{i=0}^{l-1} a_i = \sum_{i=0}^{l-1} k a_i = \sum_{i=0}^{l-1} \sum_{d \mid n} a_i^d = 0$$ in $\mathbb{F}_q$ which is impossible, since $f(a) \ne 0$ by construction and $k = 2^{\omega(n)-1}$

is coprime to $q$. The attained contradiction shows that our assumption was wrong and concludes the proof of the lemma. $\square$

Let us get back to the problem. Suppose that $p | n$ is prime and $r = 2^{2^m} + 1$ is a Fermat's prime such that $p \equiv 1 \pmod r$. If $q$ is any prime divisor of $n$, then by Lemma 3 we have that $q^l \equiv 1 \pmod{p-1}$ for some odd $l$, so that $q^l \equiv 1 \pmod r$ and therefore $q = q^{\gcd(l, r-1)} \equiv 1 \pmod r$. Hence $d \equiv 1 \pmod r$ for any divisor $d$ of $n$. $\square$