uniolympiads Ελληνικά

IMC 2024, Day 2, Problem 10

We say that a square-free positive integer nn is almost prime if

n∣xd1+xd2+⋯+xdk−kxn \mid x^{d_1} + x^{d_2} + \dots + x^{d_k} - kx

for all integers xx, where 1=d1<d2<⋯<dk=n1 = d_1 < d_2 < \dots < d_k = n are all the positive divisors of nn. Suppose that rr is a Fermat prime (i.e. it is a prime of the form 22m+12^{2^m} + 1 for an integer m≥0m \ge 0), pp is a prime divisor of an almost prime integer nn, and p≡1(modr)p \equiv 1 \pmod r. Show that, with the above notation, di≡1(modr)d_i \equiv 1 \pmod r for all 1≤i≤k1 \le i \le k.

(An integer nn is called square-free if it is not divisible by d2d^2 for any integer d>1d > 1.)

Original from the official PDFWe say that a square-free positive integer n is almost prime if n | x d 1 + x d 2 + ... + x d k − kx for all integers x, where 1 = d 1 < d 2 < ... < d k = n are all the positive divisors of n. Suppose m that r is a Fermat prime (i.e. it is a prime of the form 2 2 + 1 for an integer m ≥ 0), p is a prime divisor of an almost prime integer n, and p ≡ 1 (mod r). Show that, with the above notation, d i ≡ 1 (mod r) for all 1 ≤ i ≤ k. (An integer n is called square-free if it is not divisible by d 2 for any integer d > 1.) After the end of contest, the solutions and preliminary results will be posted at https://imc-math.org.uk/?year=2024&item=problems and https://imc-math.org.uk/?year=2024&item=results.

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

(proposed by Tigran Hakobyan, Yerevan State University, Vanadzor, Armenia)

Solution. We first prove the following claims.

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

Proof. Assume to the contrary that gcd⁡(n,φ(n))>1\gcd(n, \varphi(n)) > 1 so that there are primes pp and qq dividing nn such that p≡1(mod q)p \equiv 1 (\mathrm{mod}\ q). For 0≤i≤p−20 \le i \le p-2 let hih_i be the number of positive divisors of nn congruent to ii modulo p−1p-1 and similarly for 0≤j≤q−10 \le j \le q-1 let νj\nu_j denote the number of positive divisors of nn congruent to jj modulo qq. Observe that the polynomial Fn(x)=xd1+xd2+…+xdk−kxF_n(x) = x^{d_1} + x^{d_2} + \ldots + x^{d_k} - kx defines the zero function on Fp\mathbb{F}_p due to the condition of the problem. On the other hand, Fn(x)=(h1−k)x+∑i≠1hixiF_n(x) = (h_1 - k)x + \sum_{i \neq 1} h_ix^i in Fp[x]\mathbb{F}_p[x], so that p∣hip | h_i for all 0≤i≤p−2,i≠10 \le i \le p-2, i \neq 1. It follows that 2ω(n)−1=ν0=h0+hq+h2q+…≡0(mod p)2^{\omega(n)-1} = \nu_0 = h_0 + h_q + h_{2q} + \ldots \equiv 0 (\mathrm{mod}\ p) which is a contradiction (here ω(n)\omega(n) means the number of distinct prime divisors of nn). Therefore our assumption was wrong and the lemma is proved. □\square

Lemma 2. Let qq be a prime number and let hh be a positive integer coprime to q−1q-1. If ll is the order of hh modulo q−1q-1, then there exists a∈Fqa \in \mathbb{F}_q such that ahl=aa^{h^l} = a and

a−ah+ah2−…+(−1)l−1ahl−1≠0a - a^h + a^{h^2} - \ldots + (-1)^{l-1}a^{h^{l-1}} \neq 0

Proof. Observe that ahl=aa^{h^l} = a for any a∈Fqa \in \mathbb{F}_q since q−1∣hl−1q - 1 | h^l - 1. On the other hand, the numbers h0,h1,…,hl−1h^0, h^1, \ldots, h^{l-1} leave different remainders upon division by q−1q-1 and therefore the polynomial

f(x)=x−xh+xh2−…+(−1)l−1xhl−1f(x) = x - x^h + x^{h^2} - \ldots + (-1)^{l-1}x^{h^{l-1}}
defines a function on Fq\mathbb{F}_q, which is not identically zero. Hence the existence of an element with the required properties is proved. □\square

Lemma 3. If nn is almost prime then for any primes pp and qq dividing nn, the order of pp modulo q−1q-1 is an odd number.

Proof. Observe that due to Lemma 1 the order ll of pp modulo q−1q-1 is well defined and assume to the contrary that ll is an even number. According to Lemma 2 there exists a∈Fqa \in \mathbb{F}_q such that apl=aa^{p^l} = a and f(a)≠0f(a) \neq 0, where f(x)=x−xp+xp2−…+(−1)l−1xpl−1f(x) = x - x^p + x^{p^2} - \ldots + (-1)^{l-1}x^{p^{l-1}}. Let us consider the sequence (ai)i=0l⊂Fq(a_i)_{i=0}^{l} \subset \mathbb{F}_q defined by a0=aa_0 = a and ai+1=−aipa_{i+1} = -a_i^p for 0≤i≤l−10 \le i \le l-1. Notice that since ll is even by the assumption, we have al=a0pl=a0a_l = a_0^{p^l} = a_0. It follows that

∑i=0l−1∑d∣naid=∑i=0l−1(∑d∣npaid+∑d∣npaipd)=∑i=0l−1∑d∣np(ai+1d+aipd)=0,\sum_{i=0}^{l-1}\sum_{d|n} a_i^d = \sum_{i=0}^{l-1}\bigg(\sum_{d|\frac{n}{p}} a_i^d + \sum_{d|\frac{n}{p}} a_i^{pd}\bigg) = \sum_{i=0}^{l-1}\sum_{d|\frac{n}{p}}\Big(a_{i+1}^d + a_i^{pd}\Big) = 0,
since dd is always odd being a divisor of nn (Recall that gcd⁡(n,φ(n))=1\gcd(n, \varphi(n)) = 1 due to Lemma 1, so that nn is odd, except the trivial case n=2n = 2), and ai+1=−aipa_{i+1} = -a_i^p for all 0≤i≤l−10 \le i \le l-1. On the other hand, according to the condition of the problem, ∑d∣naid=kai\sum_{d|n} a_i^d = ka_i in Fq\mathbb{F}_q for all ii, which shows that
kf(a)=k∑i=0l−1ai=∑i=0l−1kai=∑i=0l−1∑d∣naid=0kf(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_i^d = 0
in Fq\mathbb{F}_q which is impossible, since f(a)≠0f(a) \neq 0 by construction and k=2ω(n)−1k = 2^{\omega(n)-1} is coprime to qq. 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∣np|n is prime and r=22m+1r = 2^{2^m} + 1 is a Fermat's prime such that p≡1(mod r)p \equiv 1 (\mathrm{mod}\ r). If qq is any prime divisor of nn, then by Lemma 3 we have that ql≡1(mod p−1)q^l \equiv 1 (\mathrm{mod}\ p-1) for some odd ll, so that ql≡1(mod r)q^l \equiv 1 (\mathrm{mod}\ r) and therefore q=qgcd⁡(l,r−1)≡1(mod r)q = q^{\gcd(l, r-1)} \equiv 1 (\mathrm{mod}\ r). Hence d≡1(mod r)d \equiv 1 (\mathrm{mod}\ r) for any divisor dd of nn. □\square

Transcribed from the official solutions, pages 5–6. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?