Sum Of Squares
Find the smallest positive integer k such that 1 2 + 2 2 + 3 2 + … + k 2 is a multiple of 200.
The answer is 112.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Why are you using k ( k + 1 ) ( 2 k + 1 ) ?
Log in to reply
Because 1 2 + 2 2 + ⋯ + k 2 = 6 k ( k + 1 ) ( 2 k + 1 ) .
General formula for sum of squares...
Sum(k²)=n(n+1)(2n+1)/6=200q n(n+1)(2n+1)=1200q 2n³+3n²+n-1200q=0/ 4,2n=m m³+3m²+2m-4800q=0,m=t-1 t³-t-4800q=0 (t-1)t(t+1)=25 3 2 32q So one of numbers t-1,t,t+1 is divided by 25,other by 32 So 25a-32b=1 So a=1 (mod 8) a=8c+1 200c+24-32b=0 25c=4b-3, c=1 (mod 4) c=4d+1 100d+28=4b b=25d+7 a=32d+9 Smallest solution is for d=0 a=9,b=7 So one number is 9 25=225 Other is 7 32=224 t=2n+1 is odd number so t=225 n=112 is such smallest number Other case 25a-32b=2 , a,b are integers So a=2c, 25c-16b=1 c=1 (mod 8), c=8d+1 200d+24-16b=0 2b=25d+3,d=2e+1 b=25e+14,a=32e+18 So min. Is for e=-1 b=-11,a=-14 32 11-25 14=2 t+1=352, 2n+2=352 n=175, so min. Is min(112,175)=112
wolframalpha code
{mod(sum(n^2,n=1 to k),200)=0, k>0}
choose least as n=0 in k=16(75n+7)
=112
Can you explain why k=15 mod 16, k=12,24 mod 25 satisfies the condition? I don't quite get it.
Log in to reply
@Patrick Corn
The factors k , k + 1 , and 2 k + 1 are relatively prime, so if the product is a multiple of 1 6 then one of the factors is. So either 1 6 divides k or 1 6 divides k + 1 ( 1 6 can't divide 2 k + 1 , which is odd).
Similarly, the three cases 0 , 1 2 , 2 4 mod 2 5 arise from setting k , 2 k + 1 , k + 1 congruent to 0 mod 2 5 respectively.
Does that make sense?
You also need to notice that k , k + 1 , 2 k + 1 are pairwise relatively prime - that's why you cannot distribute e.g. 2 4 into different factors, leaving you with the six possibilities Patrick Corn lists.
Log in to reply
Would you please explain why he said "This leads to six solutions mod 400: 0,112,175,224,287,3990,112,175,224,287,399." Did he do it using chinese remainder theorem?
We get that k ( k + 1 ) ( 2 k + 1 ) is a multiple of 1 2 0 0 = 2 4 ⋅ 3 ⋅ 5 2 . It's a multiple of 3 for free. To be a multiple of 1 6 we need k ≡ 0 , 1 5 mod 1 6 . To be a multiple of 2 5 we need k ≡ 0 , 1 2 , 2 4 mod 2 5 . This leads to six solutions mod 4 0 0 : 0 , 1 1 2 , 1 7 5 , 2 2 4 , 2 8 7 , 3 9 9 . The smallest positive integer in these congruence classes is 1 1 2 .