Maths Olympiad Prep

Library / /13 of 43

Number theory Difficulty 7.7 National olympiad, round 2 Find the answer

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

A number or a short expression. Spacing and $ signs are ignored.

Solution

We show that p=3p=3 is the only prime that satisfies the condition. Let f(x)=x33x+1f(x)=x^{3}-3 x+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 2Re12+(12)2(33)33=2Recos2π3+isin2π33={2cos2π9,2cos4π9,2cos8π9}2 \operatorname{Re} \sqrt[3]{\frac{-1}{2}+\sqrt{\left(\frac{-1}{2}\right)^{2}-\left(\frac{-3}{3}\right)^{3}}}=2 \operatorname{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 2cos2t=(2cost)222 \cos 2 t=(2 \cos t)^{2}-2, the map φ(x)=x22\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 aFpa \in \mathbb{F}_{p} and consider g(x)=f(x)xa=f(x)f(a)xa=x2+ax+(a23)g(x)=\frac{f(x)}{x-a}=\frac{f(x)-f(a)}{x-a}=x^{2}+a x+\left(a^{2}-3\right). We claim that b=a22b=a^{2}-2 is a root of g(x)g(x). Indeed, g(b)=(a22)2+a(a22)+(a23)=(a+1)f(a)=0g(b)=\left(a^{2}-2\right)^{2}+a\left(a^{2}-2\right)+\left(a^{2}-3\right)=(a+1) \cdot f(a)=0. By Vieta's formulas, the other root of g(x)g(x) is c=ab=a2a+2c=-a-b=-a^{2}-a+2. If ff has a single root then the three roots must coincide, so a=a22=a2a+2a=a^{2}-2=-a^{2}-a+2. Here the quadratic equation a=a22a=a^{2}-2, or equivalently (a+1)(a2)=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)=1,f(2)=3f(1)=-1, f(2)=3 and f(3)=19f(3)=19, from these values only f(2)f(2) is divisible by 3, so p=3p=3 satisfies the condition.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.