Maths Olympiad Prep

Library / /14 of 34

, 2010

Number theory Difficulty 5.7 AIME, harder Prove it Austria

Let
f(n)=k=02010nk=1+n+n2++n2010. f(n) = \sum_{k=0}^{2010} n^k = 1 + n + n^2 + \dots + n^{2010}.
Prove that for every integer mm with 2m20102 \le m \le 2010, there is no non-negative integer nn such that f(n)f(n) is divisible by mm.

Solution

Assume that mm divides f(n)f(n) for some integer nn and some 2m20102 \le m \le 2010. As f(1)=2011f(1) = 2011 and 20112011 is a prime number, mm cannot be a divisor of f(1)f(1), so we may restrict ourselves to the case n1n \ne 1.
In this case, we can write f(n)f(n) as
f(n)=n20111n1. f(n) = \frac{n^{2011} - 1}{n - 1}.
Let pp be a prime divisor of mm. Then we have pf(n)n20111p \mid f(n) \mid n^{2011} - 1, which results in
n20111(modp).(1) n^{2011} \equiv 1 \pmod{p}. \qquad (1)
This immediately implies that nn and pp are coprime.
By (1), the order ordp(n)\text{ord}_p(n) of nn modulo pp, i.e., the smallest positive exponent kk such that nk1(modp)n^k \equiv 1 \pmod{p}, is a divisor of 20112011. As 20112011 is prime, this results in ordp(n){1,2011}\text{ord}_p(n) \in \{1, 2011\}.
If ordp(n)=1\text{ord}_p(n) = 1, we have n1(modp)n \equiv 1 \pmod{p}, which results in 0f(n)2011(modp)0 \equiv f(n) \equiv 2011 \pmod{p} (by the original definition of f(n)f(n)). This implies p2011p \mid 2011 and therefore p=2011p = 2011, contradiction.
We conclude that ordp(n)=2011\text{ord}_p(n) = 2011. As ordp(n)\text{ord}_p(n) always divides φ(p)=p1\varphi(p) = p-1 by Fermat's theorem, we conclude that p1p-1 is a multiple of 20112011. This is a contradiction to 1<p<20111 < p < 2011. qed

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.