You may also like

problem icon

More Mods

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

problem icon

N000ughty Thoughts

Factorial one hundred (written 100!) has 24 noughts when written in full and that 1000! has 249 noughts? Convince yourself that the above is true. Perhaps your methodology will help you find the number of noughts in 10 000! and 100 000! or even 1 000 000!

problem icon

Novemberish

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.