Maths Olympiad Prep

Library / /453 of 860

Number theory Difficulty 5.2 AIME, harder Find the answer

For a positive integer nn, let θ(n)\theta(n) denote the number of integers 0x<20100 \leq x<2010 such that x2nx^{2}-n is divisible by 2010. Determine the remainder when n=02009nθ(n)\sum_{n=0}^{2009} n \cdot \theta(n) is divided by 2010.

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

Solution

Let us consider the sumn=02009nθ(n)(mod2010)\operatorname{sum} \sum_{n=0}^{2009} n \cdot \theta(n)(\bmod 2010) in a another way. Consider the sum 02+12+22++20072(mod2010)0^{2}+1^{2}+2^{2}+\cdots+2007^{2}(\bmod 2010). For each 0n<20100 \leq n<2010, in the latter sum, the term nn appears θ(n)\theta(n) times, so the sum is congruent to n=02009nθ(n)\sum_{n=0}^{2009} n \cdot \theta(n). In other words, n=02009nθ(n)=n=02009n2=(2009)(2009+1)(22009+1)6(1)20106(1)=335(mod2010)\sum_{n=0}^{2009} n \cdot \theta(n)=\sum_{n=0}^{2009} n^{2}=\frac{(2009)(2009+1)(2 \cdot 2009+1)}{6} \equiv(-1) \cdot \frac{2010}{6} \cdot(-1)=335 \quad(\bmod 2010)

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.