Number theoryDifficulty 5.2AIME, harderFind the answer
For a positive integer n, let θ(n) denote the number of integers 0≤x<2010 such that x2−n is divisible by 2010. Determine the remainder when ∑n=02009n⋅θ(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 sum∑n=02009n⋅θ(n)(mod2010) in a another way. Consider the sum 02+12+22+⋯+20072(mod2010). For each 0≤n<2010, in the latter sum, the term n appears θ(n) times, so the sum is congruent to ∑n=02009n⋅θ(n). In other words, n=0∑2009n⋅θ(n)=n=0∑2009n2=6(2009)(2009+1)(2⋅2009+1)≡(−1)⋅62010⋅(−1)=335(mod2010)
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.