Maths Olympiad Prep

Library /

Algebra Difficulty 4.7 AIME Prove it Hong Kong

Let nn be a positive integer not exceeding 20142014 with the property that x2+x+1x^2 + x + 1 is a factor of x2n+xn+1x^{2n} + x^n + 1. Find the sum of all possible values of nn.

nn 為不超過 20142014 的正整數,且 x2+x+1x^2 + x + 1x2n+xn+1x^{2n} + x^n + 1 的因式。求 nn 所有可能值之和。

Solution

Let ω\omega be a root of x2+x+1=0x^2 + x + 1 = 0. Then ω3=1\omega^3 = 1 and ω1\omega \ne 1.

Since x2+x+1x^2 + x + 1 divides x2n+xn+1x^{2n} + x^n + 1, we have ω2n+ωn+1=0\omega^{2n} + \omega^n + 1 = 0.

Let y=ωny = \omega^n. Then y2+y+1=0y^2 + y + 1 = 0, so y=ωy = \omega or y=ω2y = \omega^2.

Thus, ωn=ω\omega^n = \omega or ωn=ω2\omega^n = \omega^2.

This means n1(mod3)n \equiv 1 \pmod{3} or n2(mod3)n \equiv 2 \pmod{3}.

So nn is any positive integer not exceeding 20142014 such that n≢0(mod3)n \not\equiv 0 \pmod{3}.

The possible values of nn are those with 1n20141 \le n \le 2014 and n≢0(mod3)n \not\equiv 0 \pmod{3}.

Let us compute the sum of all such nn.

First, the sum of all nn from 11 to 20142014 is:
S=1+2++2014=2014×20152=2,029,105 S = 1 + 2 + \cdots + 2014 = \frac{2014 \times 2015}{2} = 2,029,105

Now, subtract the sum of all nn divisible by 33 in this range.

The smallest such nn is 33, the largest is 20132013.

The sequence is 3,6,9,,20133, 6, 9, \ldots, 2013.

Number of terms:
Let kk be the number of terms. 3k=2013    k=6713k = 2013 \implies k = 671.

Sum of these terms:
S3=3+6+9++2013=3(1+2++671)=3×671×6722=3×225,456=676,368 S_3 = 3 + 6 + 9 + \cdots + 2013 = 3(1 + 2 + \cdots + 671) = 3 \times \frac{671 \times 672}{2} = 3 \times 225,456 = 676,368

Therefore, the sum of all nn not divisible by 33 is:
2,029,105676,368=1,352,737 2,029,105 - 676,368 = 1,352,737

Answer: 1,352,7371,352,737

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 and solution reproduced as published; topic and difficulty added by this site.