8
$\begingroup$

Let $a_{1},a_{2},a_{3},\ldots,a_{2011},a_{2012}$ be integers. Exactly 29 of them are divisible by 3. Show that $a_{1}^2+a_{2}^2+a_{3}^2+\ldots+a_{2011}^2+a_{2012}^2$ is also divisible by 3.

$\endgroup$
5
  • 5
    $\begingroup$ If $n$ is not divisible by $3$, then what is $n^2\pmod 3$? $\endgroup$ Jan 22, 2013 at 19:24
  • 2
    $\begingroup$ $2012-29$ is divisible by $3$. $\endgroup$ Jan 22, 2013 at 19:33
  • $\begingroup$ @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. $\endgroup$
    – Ron Gordon
    Jan 22, 2013 at 19:35
  • 1
    $\begingroup$ 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$. $\endgroup$ Jan 22, 2013 at 19:39
  • $\begingroup$ @AndréNicolas: of course! QED. $\endgroup$
    – Ron Gordon
    Jan 22, 2013 at 19:50

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .