uniolympiads English

IMC 2020, Ημέρα 2, Θέμα 6

Find all prime numbers pp for which there exists a unique a∈{1,2,…,p}a \in \{1, 2, \dots, p\} such that a3−3a+1a^3 - 3a + 1 is divisible by pp.

Géza Kós, Loránd Eötvös University, Budapest

Πρωτότυπο από το επίσημο PDFFind all prime numbers p for which there exists a unique a ∈ {1, 2, . . . , p} such that a − 3a + 1 is divisible by p . Géza Kós, Loránd Eötvös University, Budapest Problem 6. 3

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.

Χρόνος σε αυτό το θέμα 0:00

Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.

Επίσημη λύση

Géza Kós, Loránd Eötvös University, Budapest

Solution 1. We show that p=3p = 3 the only prime that satsfies the condition.

Let f(x)=x3−3x+1f(x) = x^3 - 3x + 1. As preparation, let's compute the roots of f(x)f(x). By Cardano's formula, it can be seen that the roots are

2Re−12+(−12)2−(−33)33=2Recos⁡2π3+isin⁡2π33={2cos⁡2π9,2cos⁡4π9,2cos⁡8π9}2\mathrm{Re}\sqrt[3]{\frac{-1}{2} + \sqrt{\left(\frac{-1}{2}\right)^2 - \left(\frac{-3}{3}\right)^3}} = 2\mathrm{Re}\sqrt[3]{\cos\frac{2\pi}{3} + i\sin\frac{2\pi}{3}} = \left\{2\cos\frac{2\pi}{9}, 2\cos\frac{4\pi}{9}, 2\cos\frac{8\pi}{9}\right\}
where all three values of the complex cubic root were taken.

Notice that, by the trigonometric identity 2cos⁡2t=(2cos⁡t)2−22\cos 2t = (2\cos t)^2 - 2, the map φ(x)=x2−2\varphi(x) = x^2 - 2 cyclically permutes the three roots. We will use this map to find another root of ff, when it is considered over Fp\mathbb{F}_p.

Suppose that f(a)=0f(a) = 0 for some a∈Fpa \in \mathbb{F}_p and consider

g(x)=f(x)x−a=f(x)−f(a)x−a=x2+ax+(a2−3).g(x) = \frac{f(x)}{x - a} = \frac{f(x) - f(a)}{x - a} = x^2 + ax + (a^2 - 3).
We claim that b=a2−2b = a^2 - 2 is a root of g(x)g(x). Indeed,
g(b)=(a2−2)2+a(a2−2)+(a2−3)=(a+1)⋅f(a)=0.g(b) = (a^2 - 2)^2 + a(a^2 - 2) + (a^2 - 3) = (a + 1) \cdot f(a) = 0.
By Vieta's formulas, the other root of g(x)g(x) is c=−a−b=−a2−a+2c = -a - b = -a^2 - a + 2.

If ff has a single root then the three roots must coincide, so

a=a2−2=−a2−a+2.a = a^2 - 2 = -a^2 - a + 2.
Here the quadratic equation a=a2−2a = a^2 - 2, or equivalently (a+1)(a−2)=0(a + 1)(a - 2) = 0, has two solutions, a=−1a = -1 and a=2a = 2. By f(−1)=f(2)=3f(-1) = f(2) = 3, in both cases we have 0=f(a)=30 = f(a) = 3, so the only choice is p=3p = 3.

Finally, for p=3p = 3 we have f(1)=−1f(1) = -1, f(2)=3f(2) = 3 and f(3)=19f(3) = 19, from these values only f(2)f(2) is divisible by 33, so p=3p = 3 satisfies the condition.

Solution 2 (outline) Define f(x)f(x) and g(x)g(x) like in Solution 1. The discriminant of g(x)g(x) is

Δg=a2−4(a2−3)=12−3a2.\Delta_g = a^2 - 4(a^2 - 3) = 12 - 3a^2.
We show that Δg\Delta_g has a square root in Fp\mathbb{F}_p.

Take two integers k,mk, m (to be determinated later) and consider

Δg=Δg+(ka+m)f(a)=ka4+ma3−(3k+1)a2+(k−3m)a+(m+12).\Delta_g = \Delta_g + (ka + m)f(a) = ka^4 + ma^3 - (3k + 1)a^2 + (k - 3m)a + (m + 12).
Our goal is to choose k,mk, m in such a way that the last expression is a complete square. Either by direct calculations or guessing, we can find that k=m=4k = m = 4 works:
Δg=Δg+(4a+4)f(a)=4a4+4a3−15a2−8a+16=(2a2+a−4)2.\Delta_g = \Delta_g + (4a + 4)f(a) = 4a^4 + 4a^3 - 15a^2 - 8a + 16 = (2a^2 + a - 4)^2.

If p≠2p \neq 2 then we can conclude that f(x)f(x) has either no or three roots, therefore pp is suitable if and only is f(x)f(x) is a complete cube: x3−3x+1=(x−a)3x^3 - 3x + 1 = (x - a)^3. From Vieta's formulas a3=1a^3 = 1, so a≠0a \neq 0 and 3a=03a = 0, which is possible if p=3p = 3.

For p=3p = 3 we have f(x)=(x+1)3f(x) = (x + 1)^3, so p=3p = 3 is suitable.

The case p=2p = 2 must be checked separately because the quadratic formula contains a division by 2. f(1)=−1f(1) = -1 and f(2)=3f(2) = 3, so p=2p = 2 is not suitable.

Solution 3 (outline) Assume p>3p > 3; the cases p=2p = 2 and p=3p = 3 will be checked separately.

Let f(x)=x3−3x+1f(x) = x^3 - 3x + 1 and suppose that a∈Fpa \in \mathbb{F}_p is a root of f(x)f(x), and let b,c∈Fp2b, c \in \mathbb{F}_{p^2} be the other two roots. The discriminant Δf\Delta_f of f(x)f(x) can be expressed by the elementary symmetric polynomials of a,b,ca, b, c; it can be calculated that

Δf=(b−c)2(a−b)2(a−c)2=81=92,\Delta_f = (b - c)^2(a - b)^2(a - c)^2 = 81 = 9^2,
so
(b−c)(a−b)(a−c)=±9∈Fp.(b - c)(a - b)(a - c) = \pm 9 \in \mathbb{F}_p.
Notice that Δf≠0\Delta_f \neq 0, so the three roots are distinct.

Either b,c∈Fpb, c \in \mathbb{F}_p or b,cb, c are conjugate elements in Fp2∖Fp\mathbb{F}_{p^2} \setminus \mathbb{F}_p, we have (a−b)(a−c)∈Fp(a - b)(a - c) \in \mathbb{F}_p, so b−c=(b−c)(a−b)(a−c)(a−b)(a−c)∈Fpb - c = \frac{(b-c)(a-b)(a-c)}{(a-b)(a-c)} \in \mathbb{F}_p. From Vieta's formulas we have b+c∈Fpb + c \in \mathbb{F}_p as well; since p≠2p \neq 2, it follows that b,c∈Fpb, c \in \mathbb{F}_p. Now f(x)f(x) has three distinct roots in Fp\mathbb{F}_p, so pp cannot be suitable.

p=2p = 2 does not satisfies the condition because both f(1)=−1f(1) = -1 and f(2)=3f(2) = 3 are odd. p=3p = 3 is suitable, because f(2)=3f(2) = 3 is divisible by 3 while f(1)=−1f(1) = -1 and f(3)=19f(3) = 19 are not.

Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδες 1–3. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.

Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.

Πώς πήγε;