You may also like

problem icon

More Mods

What is the units digit for the number 123^(456) ?

problem icon

N000ughty Thoughts

How many noughts are at the end of these giant numbers?

problem icon


a) A four digit number (in base 10) aabb is a perfect square. Discuss ways of systematically finding this number. (b) Prove that 11^{10}-1 is divisible by 100.

Mod 3

Stage: 4 Challenge Level: Challenge Level:1

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.