Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let be $ a_{1},a_{2},a_{3},...,a_{2011},a_{2012} $ integers.Exatly 29 of them divisible by number 3.Show that $ a_{1}^2+a_{2}^2+a_{3}^2+...+a_{2011}^2+a_{2012}^2 $ is divisible by number 3.

share|improve this question
5  
If $n$ is not divisible by $3$, then what is $n^2\pmod 3$? –  Thomas Andrews Jan 22 '13 at 19:24
2  
$2012-29$ is divisible by $3$. –  André Nicolas Jan 22 '13 at 19:33
    
@AndréNicolas: I found that, too. I think the point is to show that the sum of squares of any 3 numbers, each of which are not divisible by 3, is divisible by 3. –  Ron Gordon Jan 22 '13 at 19:35
1  
Observe (this is the remark of Thomas Andrews) that if $a$ is not divisible by $3$, then the remainder when you divide $a^2$ by $3$ is $1$. –  André Nicolas Jan 22 '13 at 19:39
    
@AndréNicolas: of course! QED. –  Ron Gordon Jan 22 '13 at 19:50

2 Answers 2

up vote 1 down vote accepted

This is very easy to solve once you know congruences, and harder when you are young and do not. That is to say a "tricky", though nice, kind of problem.

There are 2012 - 29 = 1983 squares that are all 1 mod 3, since squares can only be 0 or 1 mod 3 (if a = 2 mod 3 then a^2 = 4 mod 3 = 1 mod 3) and we have excluded all those who were divisible by 3. Their sum will be equal to 1983 mod 3 = 0 mod 3, and so divisible by 3 since 1983 is divisible by 3.

share|improve this answer

Hint $\, $ mod prime $p:\ a\not\equiv 0\,\Rightarrow\, a^{p-1}\!\equiv 1,\,$ so $\,a_1^{p-1}\! +\cdots+ a_n^{p-1}\! \equiv\:$the number of $a_i\! \not\equiv 0$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.