Copyright © University of Cambridge. All rights reserved.

'Mod 3' printed from

Show menu

Well done Richard Mycroft, age 16 from Melbourn Village College, Cambridgeshire and Selvan Gnanakumaran and Tony Cardell for your solutions.

We assume here that $a$ and $b$ are integers and $a^2+ b^2$ is divisible by $3$.

Here is Richard's which uses modulus arithmetic.

Any number is either $-1$, $0$, or $1\pmod{3}$. For any number $n$ we have $n^2 = 0$ or $1 \pmod3$ As $-1^2 = 1, 0^2 = 0$and $1^2 = 1$

Therefore $n^2 = 0 \pmod 3$ if $n = 0 \pmod 3$, or $n^2= 1 \pmod 3$ if $n = 1$ or $-1 \pmod 3$.

If $a^2 + b^2$ is divisible by 3 then $a^2 + b^2 = 0 \pmod 3$. Now, $N \pmod 3 + M \pmod 3 =N +M \pmod 3$. Therefore if both $a$ and $b$ are not divisible by 3 then $$a^2 + b^2 = 2 = -1 \pmod 3$$ If one of $a$ and $b$ is not divisible by $3$ (but the other is) then: $$a^2 + b^2 =1 \pmod 3.$$

In both cases $a^2 + b^2$ is not divisible by $3$. So if $a^2 + b^2$ is divisible by $3$ then both $a$ and $b$ are divisible by $3$.

Here is Tony's proof which is of course equivalent. Any number $n$ falls into one of three categories, having a remainder of $0$, $1$ or $2$ when divided by $3$. Therefore any number $n^2$ will have a remainder $0^2 = 0$, $1^2 = 1$, or $2^2 = 4$, also giving a remainder $1$ when divided by $3$. For $a^2+ b^2$ to be divisible by $3$, it must be congruent to $0 \pmod 3$. The only way for this to happen, since $a^2$ and $b^2$ can only be zero or one mod $3$ and so their maximum sum is two, is for them both to be zero mod $3$. If $a^2$ and $b^2$ are both zero mod $3$, they are both divisible by three, and thus both $a$ and $b$ are divisible by three.

Selvan proved this result in a different way: First say that if $a^2+ b^2$ is a multiple of $3$ then $a^2 + b^2 = 3n$ , where $n$ is a positive integer.

Now if $b$ is not a multiple of $3$, $b$ can be expressed in the form $3x \pm 1$, where $x$ is an integer. Therefore $$a^2 + (3x \pm 1)^2= 3n$$ so $$a^2= 3n - 9x^2 \pm 6x -1$$ and therefore $a^2$ is not a multiple of three as it is expressed as a multiple of three minus $1$. Hence $a$ is not a multiple of $3$, and therefore $a$ can be expressed in the form $$3y\pm 1$$where $y$ is a positive integer.

Therefore $$(3y \pm 1)^2 = 3n - 9x^2 \pm 6x - 1$$ and so $$9y^2 \pm 6y + 1 = 3n - 9x^2\pm 6x - 1$$ $$9y^2\pm 6y + 2 = 3n -9x^2 \pm 6x$$

The right hand side of the expression is a multiple of three, but the left hand side however is clearly not, as it is a multiple of three add $2$. Here is a contradiction.

When $b$ was said to be a non multiple of three, it led to saying that a must also be a non multiple, and a contradiction occurred. Therefore neither $a$ nor $b$ can be non multiples of three, hence if $a^2 + b^2$ is a multiple of three then $a$ and $b$ are both multiples of three.