degrade into solving system of linear congruence

This is a special case of quadratic congruence. The general quadratic congruence is not easy to solve with composite moduli.

But since gcd(n, n+1) = 1 and 2000=2^4x5^3. So we can solve the following four linear congruence cases instead:

1) n=0( mod125) and n+1 = 0(mod 16), n=1375 (plug into original equation, it is an extraneous one)

2) n=0 (mod16) and n+1=0(mod 125); n=624 (plug into n(n+1)/2 , is a good solution)

3) n=0(mod2000), n =0, 2000 (the one we already have)

4) n+1=(mod 2000), n =1999, this is also a good solution.

所有跟帖： 

• 我觉得一般性的二次同余是不会出现在AIME中（I might be wrong），但是这个是线性同余in disguise. -calligraphy- ♂ (0 bytes) () 12/30/2014 postreply 07:30:27

• 赞！ -ca981- ♂ (0 bytes) () 12/30/2014 postreply 08:27:15