Maths Olympiad Prep

Library / /91 of 1394

, 2023

Number theory Difficulty 4.7 AIME Find the answer United States

Problem:
Let
P=i=02016(i3i1)2 P=\prod_{i=0}^{2016}\left(i^{3}-i-1\right)^{2}
The remainder when PP is divided by the prime 20172017 is not zero. Compute this remainder.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Solution:
Let Q(x)=x3x1=(xa)(xb)(xc)Q(x)=x^{3}-x-1=(x-a)(x-b)(x-c), for a,b,cFp3a, b, c \in \mathbb{F}_{p^{3}}. Then, we can write
P=i=02016(ia)(ib)(ic) P=\prod_{i=0}^{2016}(i-a)(i-b)(i-c)
If we consider each root separately, then
P=(a2017a)(b2017b)(c2017c) P=-\left(a^{2017}-a\right)\left(b^{2017}-b\right)\left(c^{2017}-c\right)
The key observation is that a2017,b2017,c2017a^{2017}, b^{2017}, c^{2017} is some nontrivial cycle of a,b,ca, b, c. This is because by Frobenius' identity, (a+b)p=ap+bp(a+b)^{p}=a^{p}+b^{p}. So, if P(x)=0,P(x2017)=0P(x)=0, P\left(x^{2017}\right)=0. But, x2017xx^{2017} \neq x, since xFpx \notin \mathbb{F}_{p}. This implies the claim. So, in the end, we wish to compute
(ba)2(cb)2(ac)2 (b-a)^{2}(c-b)^{2}(a-c)^{2}
Note that P(x)=3x21=(xb)(xc)+(xa)(xb)+(xc)(xa)P^{\prime}(x)=3 x^{2}-1=(x-b)(x-c)+(x-a)(x-b)+(x-c)(x-a). So it suffices to compute
(13a2)(13b2)(13c2)=27P(13)P(13) \left(1-3 a^{2}\right)\left(1-3 b^{2}\right)\left(1-3 c^{2}\right)=-27 P\left(\frac{1}{\sqrt{3}}\right) P\left(-\frac{1}{\sqrt{3}}\right)
We can compute this is equal to 27(1233)(1+233)=23-27\left(1-\frac{2}{3 \sqrt{3}}\right)\left(1+\frac{2}{3 \sqrt{3}}\right)=-23.

Alternatively, this is the discriminant of P(x)P(x). We utilize the well-known formula that the discriminant of x3+ax+bx^{3}+a x+b is 4a327b2=23-4 a^{3}-27 b^{2}=-23. So, the answer is 19941994.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.