Square remainders
Problem
Show that every odd square leaves remainder $1$ when divided by $8$, and that every even square leaves remainder $0$ or $4$.
Deduce that a number of the form $8n+7,$ where $n$ is a positive integer, cannot be expressed as a sum of three squares.
STEP Mathematics III, Specimen paper, Q10(i). Question reproduced by kind permission of Cambridge Assessment Group Archives. The question remains Copyright University of Cambridge Local Examinations Syndicate ("UCLES"), All rights reserved.
Getting Started
If a number is even then it can be written in the form $2k$, where $k$ is an integer. Similarly, if a number if odd then it can be written in the form $2k+1$.
What can you say about the reminder when $a^2+b^2+c^2$ is divided by $8$ if $a, b, c$ are all odd?
Student Solutions
Faridah from Robert Gordon’s College in the UK explained what happens for odd squares:
When I square an odd number, like 3, 5, or 7, I always get an odd square.
For example, when I square 3, you get 9, and when I square 5, you get 25.
Now, we have to see what happens when I divide these odd squares by 8.
Every time I divide an odd square by 8, you are left with a remainder of 1.
So, no matter which odd square I choose, whether it's 9 or 25 or any other odd square, I will always have 1 left over when I divide it by 8.
Mahe from School 21 in the UK and Rishik K began using algebra to prove what Faridah observed. This is Rishik's work:
Every odd number is either 1 less or more than an even number. To solve this problem, I will choose to denote an odd number in the form $2x+1$ or $2x-1.$
(Note that in fact, all odd numbers are both one more than an even number and one more than an even number)
If an odd number is squared, its result must be odd as an odd multiplied by another odd will always be an odd.
This can be shown by many examples including:
$3 \times 5 = 15$
$9 \times 7 = 63$
$11 \times 11 = 121$
Using the notation above, if an odd number is squared then the two possible results are either:
$(2x+1)^2 = 4x^2 + 4x + 1$
$(2x-1)^2 = 4x^2 – 4x +1$
Robbie from Taunton School in England and Julia started earlier - they wanted to make sure that a square is only odd if it is the square of an odd number. Here is Julia's work:
Julia from The Latyer School in the UK, Ziwei (Gilbert) from Stowe School in the UK, Nishad, James, Robbie and Julia all used the same idea as Rishik K to set up and prove that if $n^2$ is odd, then it leaves a remainder of $1$ when divided by $8.$ This is James's work:
Nishad's reasoning is the same, but Nishad used $2n+1$ instead of $2n-1$ for a generic odd number. Nishad also used the notation $\equiv1(\text{mod }n)$ to mean "is congruent to 1 modulo 8", or "has a remainer of 1 when divided by 8". This is Nishad's work (click on the image to open a larger version):
Joshua from Bohunt Sixth Form, James from Stowe School, Luke from Magdalen College School and Pratyush from Wilson's School all in the UK and Igor from Park Lane International School in the Czech Republic all used a slightly different argument to show that $n(n+1)$ is even. This is Joshua's work:
Instead of using an odd-even or odd-odd/even-even argument, Dylan from Brooke Weston separately considered the case where $k$ is odd and where $k$ is even. Click to see Dylan's work.
Oliver from Belfast Royal Academy in Northern Ireland used proof by induction. Click to see Oliver's work (and click on the image itself to open a larger version).
Rishik K explained why even squares have a remainder of 0 or 4 when divided by 8:
In this problem, I will denote an even number as $2x.$ After squaring an even number, we will obviously receive an even number because an even multiplied by an even result in an even number. This is shown by the examples:
$8 \times 8 = 64$
$16 \times 6 = 96$
$24 \times 10 = 240$
$(2x)^2$ results in $4x^2$
As $4$ is a factor of $8$ and $8\div4 = 2,$ in the list of multiples for $4,$ a common multiple of $8$ will occur every other time.
$4\times = 4, \underline8, 12, \underline{16}, 20, \underline{24}, 28, \underline{32}$
$8\times = \underline{8}, \underline{16}, \underline{24}, \underline{32}$
Therefore, in each even square number when they are divided by $8,$ there will either be a remainder of $4$ or $0$ because every second multiple of $4$ is a multiple of $8,$ as demonstrated above.
Both Julias, both Jameses, Joshua, Nishad, Dylan, Pratyush, Ziwei (Gilbert), Luke, Oliver and Igor used algebra to write a rigorous proof. This is Ziwei (Gilbert)'s work:
This is Igor's work:
To show that the sum of three squares can never be written as $8n+7$, Robbie and Pratyush demonstrated what happens algebraically when you add every possible combination of three squares. For both of them, this meant they didn't get to use what they had already discovered. Click to see Robbie's work.
Now if we assume the first square is even, the next two have to sum to an odd number so that the total sum is odd. This can only happen with one more even square and an odd square.
If we assume the first square is odd, the next two have to sum to an even number so that the total sum is odd. This can only happen with either two more even squares (giving us the same case as if the first is even) or with
two more odd squares (a unique case).
Therefore we have to consider two cases; where there are two even squares and one odd square, and where there are three odd squares.
Let's consider the case with three odd squares first. Odd squares can be expressed as $(2n-1)^2,$ which expands to $4n^2-4n+1.$ This means that with three odd squares, we can write the sum as
$4(x(x-1) + y(y-1) + z(z-1)) + 3 = 8n + 7$ [subtract 3 from both sides]
$4(x(x-1) + y(y-1) + z(z-1)) = 8n + 4$ [divide by 4]
$x(x-1) + y(y-1) + z(z-1) = 2n + 1$
Now as $2n + 1$ is odd (even+odd), $x(x-1) + y(y-1) + z(z-1)$ must be odd - however as $x, y$ and $z$ are all integers, one of $x$ and $x-1$ is odd and the other is even, meaning that the product is even. This logic also applies for $y(y-1)$ and $z(z-1),$ meaning that it is a sum of three even numbers, yielding another even number. This is a contradiction, so therefore three odd squares cannot sum to $8n+7.$
Now let's consider the case with one odd square and two even squares. An even square can be expressed as $(2n)^2,$ which expands to $4n^2,$ and odd squares can expand to $4n^2 - 4n + 1$ as shown earlier. Therefore this sum can be expressed as
$4(x^2 - x + y^2 + z^2) + 1 = 8n + 7$ [subtract 1 from both sides]
$4(x^2 - x + y^2 + z^2) = 8n + 6$ [divide by 4]
$x^2 - x + y^2 + z^2 = 2n + \frac64$
It can clearly be seen that $2n + \frac64$ is not an integer if $n$ is an integer. However, as $x, y$ and $z$ are all also integers, $x^2 - x + y^2 + z^2$ must also be an integer - this is a contradiction, therefore two even squares
and an odd square cannot sum to give $8n + 7.$
As neither of the cases can be equal to $8n+7,$ there is therefore no set of three squares which sums to give any $8n + 7.$
Julia from The Latymer School, Mahe and Oliver used what they had already found about remainders when dividing by 8. This is Julia's work:
First note that $N=8n+7$ is an odd number which has a remainder of $7$ when divided by $8.$
Assume $N$ can be written as a sum of three squares: $N=a^2 + b^2 + c^2.$ As a square of an odd number is odd and a square of an even number is even, we can only have (i) all three $a, b$ and $c$ as odd numbers, or (ii) two of them even and one odd. Having $a,b,c$ all even numbers is not possible as this will make $N=a^2 + b^2 + c^2$ an even number. Similarly if one of $a,b$ or $c$ is even
and the other two are odd then $N$ would be an even number.
(i) we can write $N=8A +1 + 8B + 1 + 8C +1,$ as we know from first part that an even square has a remainder of $1$ when divided by $8.$ Therefore $N$ has remainder of $3$ when divided by $8$ which is impossible since we know that $N$ had a remainder of $7$ when divided by $8.$
ii) if one of $a, b$ or $c$ is odd and two are even, then using the result proven in part 1) then $N=8A+ 1 + 8B +0 +8C +0$ when each of the two even squares have remeinders of $0$,
or $N=8A+ 1 + 8B +0 +8C +4$ when one of the even square has a remainder $0$ and one of the even squares has a remainder $4$ when divided by $8,$
or $N= 8A+ 1 + 8B +4 +8C +4$ when each of the even squares have a remainder of $4.$
Therefore the remainder of $N$ when divided by $8$ is either $1$ or $5$ which is impossible since we know that $N$ had a reminder of $7$ when divided by $8.$
Therefore our assumption that $N$ can be written as a sum of three squares is impossible. Therefore this proves that $8n+7$ cannot be written as a sum of three squares.
Both Jameses, Ziwei (Gilbert), Dylan, Luke and Rishik K used the exact same idea, but ignored all of the multiples of 8 and just added up the remainders. This is James from Stowe School's work:
We can divide all the square numbers into two types. Odd squares and even squares.
We already know that if you divide an odd square by 8 you will get a remainder of 1. And if you divide an even square by 8 you will get a remainder of 4 or 0.
Now, we just need to focus on the remainder.
- So, we need to try all the possible combination until we add (1,0, or 4) up to 7.
Here is the rule:
- We can use the same number once, more than once or not at all.
- But we must use three numbers in total.
If we use those numbers (1, 0 and 4) to add up to a result of 7, that means $8n+7$ can be expressed to a sum of three squares.
But if we can’t use those number (1, 0 and 4) to add up to a result of 7, that means $8n+7$ cannot be expressed to a sum of three square.
- This is because the remainder doesn’t fit, we can’t get a remainder of 7 using 1,0 and 4.
OK, let's start now.
| Number 1 | Number 2 | Number 3 | result | 7 or not | |
|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 3 | No |
| 2 | 0 | 0 | 0 | 0 | No |
| 3 | 4 | 4 | 4 | 12 | No |
| 4 | 1 | 1 | 4 | 6 | No |
| 5 | 1 | 1 | 0 | 2 | No |
| 6 | 4 | 4 | 0 | 8 | No |
| 7 | 4 | 4 | 1 | 9 | No |
| 8 | 0 | 0 | 1 | 1 | No |
| 9 | 0 | 0 | 4 | 4 | No |
| 10 | 4 | 1 | 0 | 5 | No |
To make sure I didn’t miss any of the combination we can separate the combination into three categories.
- All three numbers are the same.
- First two numbers are the same but the third one is different.
- All three numbers are different.
This proves why $8n+7$ cannot be expressed as a sum of three squares.
Nishad, Igor, Joshua and the non-Latymer Julia used "mod" notation to express the same idea. This is Julia's work:
Teachers' Resources
Why do this problem?
This problem asks students to use number theory to prove some results, and also show that some results are not possible.
Possible approach
To begin with students could consider what happens when they divide square numbers by $8$ by working systematically through the first few numbers.
If students are not familiar with standard expressions for odd and even numbers then they could be asked to find the rule for the $n$th term of the sequences:
- $2, 4, 6, 8, 10, ...$ $n$th term is given by $2n$
- $1, 3, 5, 7, 9, ...$ $n$th term is given by $2n-1$, although $2n+1$ might be nicer to use!
Key questions
- If an odd number can be written as $2k+1$, what would be the expression for this number squared?
- If we want to show that adding two odd numbers gives an even number, should we consider $(2a+1)+(2a-1)$ or $(2a+1)+(2b+1)$? Why?
- What can you say about the parity of the two numbers $k$ and $k+1$? The parity of a number is referring to whether it is odd or even.
- If you add two numbers of the form $8a+1$ and $8b+1$, what would be the remainder if you divided the sum by $8$?
Possible extension
Here is a list of number theory problems.