The problems in this masterclass package are intended to be used in a computer room to introduce students to ideas in Number Theory.
Working on a selection of these activities builds on students' knowledge of multiples and allows them to develop and formalise their understanding of linear sequences, remainders and modular arithmetic.
Shifting Times Tables
Can you find a way to identify times tables after they have been shifted up or down?
Shifting Times Tables printable worksheet
The numbers in the four times table are
$$4, 8, 12, 16... 36, 40, 44... 100, 104, 108...$$
I could shift the four times table up by 3 and end up with
$$7, 11, 15, 19... 39, 43, 47... 103, 107, 111...$$
What do you notice about the differences between consecutive terms in each sequence?
The interactivity displays five numbers from a shifted times table.
On Levels 1 and 2 it will always display five consecutive terms from the shifted times table.
On Levels 3 and 4 it could display any five terms from the shifted times table.
Use the interactivity to generate some sets of five numbers.
Can you work out the times table and by how much it has been shifted?
Once you are confident that you can work out the times table and the shift quite easily, here are some questions to consider:
What can you say if the numbers are all odd?
What about if they are all even?
Or a mixture of odd and even?
What can you say if the units digits are all identical?
What if there are only two different units digits?
What can you say if the difference between two numbers is prime?
What can you say if the difference between two numbers is composite (not prime)?
Can you explain how you worked out the table and shift each time, and why your method will always work?
You may also be interested in the other problems in our Dynamic Explorations Feature.
For the Level 3 and 4 problems, start by rearranging the numbers so that they are in order. Then look at the pairs of numbers that are closest together.
For this problem, lots of people submitted their methods for finding the times table and the shift, and some people sent in answers to the questions in the problem.
Here are your methods for level 1 and level 2, followed by your answers to the questions, followed by your methods for level 3 and level 4.
Van Anh from British Vietnamese International School in Vietnam sent in a useful insight for finding the times table and shift at level 1 and level 2:
In the times table, even if the times table is shifted, the distance between the two numbers will be the same. Let's say our 2 times table, which has a distance of 2, when shifted by 101, will become 103,105,... which still has a distance of 2. You can use this to help when come dealing with these kinds of problems.
Roshni from Tanglin Trust School in Singapore, EDSR from Priestlands School in the UK and Oren from Sunnynook Primary School in New Zealand used the same method for finding the times table and shift at levels 1 and 2. This is Roshni's work:
In this level, there is a common difference(d) between consecutive terms (this is the distance that Van Anh was talking about). To work out the common difference(d), you simply find the difference between any two adjacent numbers. For example in the sequence 14,22,30,38,46, I could work out the common difference by doing: 22-14 or 30-22 or 38-30 or 46-38, all of which give the same answer of 8. Once you have found the common difference, you can then subtract (common difference $\times$ n), so you are subtracting 8,16,24,32,40 from the sequence which results in 6,6,6,6,6
Therefore, the shift is up 6. If the difference between the (common difference $\times$ n) and the sequence is negative, then it is a shift down.
Sequence: 14, 22, 30, 38, 46
Common difference $\times$ n: 8, 16, 24, 32, 40
[Result of] subtraction: 6, 6, 6, 6, 6
So, for the example used above the table is 8, it is shifted up by 6.
What can you say if the numbers are all odd?
Anh Minh from British Vietnamese International School Hanoi said: the times table you are looking for will always be 2, it will shift up/down 1.
Anh Minh is right that shifting the 2 times table (all even numbers) up or down by 1 will give only odd numbers, but this is not the only way that the numbers could all be odd.
Alex said: That means all the numbers are from an even number's time table and that the shift is an odd number. This is because any number times any even number will always give an even number, and when even numbers are shifted by an odd number they always give an odd number.
What about if they are all even?
The Marshmallows and EDSR correctly said: the multiplication table is bound to be even.
John and Jack from Trinity Grammar in Australia gave a fuller explanation: It must be an even number [times table] shifted up by an even number.
Or a mixture of odd and even?
Alex said: This means the time table is an odd number as they're the only ones that alternate between odd and even numbers. The shift can be anything because it may turn odds into evens and viceversa but there will still be both odds and evens.
What can you say if the units digits are all identical?
The Marshmallows said: the times table is bound to end in zero, which Alex and John and Jack described as a multiple of ten.
What if there are only two different units digits?
EDSR said: The table's units digit will have to be a five, which Alex and John and Jack described as a multiple of five - although it must be a multiple of five but not a multiple of ten.
What can you say if the difference between two numbers is prime?
EDSR identified that: The prime number will be the multiplication table.
Alex was more precise: Those 2 numbers are consecutive terms of a prime number's time table. The shift can be anything as it won't change the difference.
What can you say if the difference between two numbers is composite (not prime)?
EDSR and The Marshmallows both explained the same idea. The Marshmallows said: The times table could be composite but it could have numerous times tables i.e. 4 times table is also in the 2 times table.
Again, Alex was more precise: The numbers are either multiples of a non-prime times table or non-consecutive terms of a prime times table.
Can you explain how you worked out the table and shift each time, and why your method will always work?
The Marshmallows explained the steps which form the foundations of all of the methods which were sent in:
First you must find the difference between all the numbers. If they are all the same then you know the times table then add (or subtract) to the original table then you have the shifted answer.
If the difference between the numbers is not the same throughout, then you need to find a common times table before working out the shift.
How can you find the common times table?
Hayley from Tarremah Steiner School in Australia, Charlotte from Ryde School in the UK and EDSR all assumed that the common times table would be the smallest of the differences. This is Hayley's example:
My numbers were:
180 438 481 610 653
First you have to find out how much there is between each number, for instance, the difference between 481 & 438 is 43 & the difference between 653 & 610 is also 43.
Then you get the lowest number you have (180) and divide it by your difference (43)
180$\div$43 is approximately 4, then you go 4 $\times$ 43 = 172, then you take 172 from 180 which is 8
So you end up with your times table (43) and the number that you've shifted it by (8).
It is almost like a linear equation $y=mx+c$ .
So you have to find your multiple (43) and your constant (8) so you end up with $y=43x+8$
Charlotte gave the steps of this method in more detail. Click here to see Charlotte's work.
Alex explained why this method doesn't always work:
The highest common factor of the differences will be the times table. At first I thought it would just be smallest difference but then I came across this:
given that the 5 numbers are 9 18 24 30 39
the differences would be 9 6 6 9
so you could think the time table is 6, but it's actually the HCF of 6 and 9, which is 3. This is true because using the 6 times table you can go from 18 to 24, but not from 9 to 18. So the largest time table that will satisfy both will be 3.
Ms Rusnock from Stuart Country Day School of the Sacred Heart in the USA, Roshni and Oren used a more robust method. This is Roshni's work:
You should first reorder the sequence given to you to increasing order. For example, you are given 128,213,60,264,179. The new version would be 60,128,179,213,264.
First, work out the difference between any two numbers next to each other - for example do 179-128 which is 51.
Then work out the difference between another pair of numbers that are next to each other (one of the numbers may have been used for the previous subtraction), so for example do 213 and 179 which is 34.
Noticeably, the differences are different - 51 and 34. So you should find the Highest Common Factor of [all of] the differences, which is 17 in this case, which will give you the table.
Then, for each number in the sequence, find the closest [multiple of 17] that is less than that number. So for the example it is 51, 119, 170, 204, 255. Then, calculate the difference between the closest [multiple of 17] and the ordered sequence which is 9,9,9,9,9.
Sequence: 129,213,60, 264,179
Ordered Sequence(OS): 60, 128,179,213,264
Difference: 68, 51, 34, 51
Highest Common factor for difference: 17
Table closest to OS: 51, 119,170,204,255
Diff between tab and OS: 9, 9, 9, 9, 9
So, for the example used above the table is 17, shifted up by 9
Alex wrote a program to find the times table and the shift. This is Alex's description of the program:
I wrote a python script to which you input all 5 numbers one at a time followed by an enter, they are all put into a list which is then sorted by ascending order. Then the difference between each pair of 2 consecutive terms is then calculated (So the difference between the 1st and 2nd, 2nd and 3rd, 3rd and 4th, etc) listed and sorted in the same way as previously.
The highest common factor of the differences will be the times table. I work out the HCF using the Euclidean algorithm, which takes in only 2 values at a time, however we need to calculate the HCF of the whole thing, to do so we use the following property:
HCF(w,x,y,z) = HCF(HCF(w,x),HCF(y,z))
So this way it arrives at a single term which is the times table.
I used the Euclidean algorithm for the HCF as it makes the code shorter and more efficient, but it could also be computed with a classical list of factors and then picking the largest one.
The shift is calculated using the MOD function (the remainder of a division). When any of the numbers is divided by the times table the remainder will be the shift upwards.
So if the number is 57 and the times table is 20, so MOD(57, 20)= 17 (in python MOD is written as %) so here the shift would be 17 upwards.
The times table and the shift are then outputted.
Click here to see Alex's code, or here to see it as a PDF.
Why do this problem?
This problem encourages students to think about the properties of numbers. The use of an interactivity provides an engaging "hook" to stimulate students' curiosity and draws them into the structure of linear sequences and straight line graphs. It also provides a natural language, that of the "times table" and "shift" for talking about remainders and modular arithmetic.
Possible approach
This printable worksheet may be useful: Shifting Times Tables
The solutions are available here.
"I'm thinking of a times table. I wonder if you can work out which it is? $6, 12, 18, 24$" (writing the numbers on the board as you say them.)
Now show the interactivity from the problem, and alert the students that it does something slightly different (but don't tell them what!). Generate a set of numbers using Level 1 or 2, and give the class a short time to discuss with their partner what they think the computer has done.
Do the same a couple more times, without any whole-class sharing, but giving pairs a little time to refine their ideas. Then bring the class together and discuss what they think is going on. Link what they say to the terminology of "Table" and "Shift" used in the interactivity.
Emphasise that the table should always be the largest possible, and the shift should always be less than the table. This example could be used to bring these ideas out:
Possible suggestions that might emerge:
But we are interested in
Group students in pairs at a computer or with a tablet and challenge them to develop a strategy to find the table and shift with ease for Levels 1 and 2. Once they can confidently answer Level 1 and 2 questions, they can move on to Levels 3 and 4 where they are given random terms from the shifted times table instead of the first five terms. While students are working, circulate and listen out for students who have developed useful strategies that they can share with the rest of the class.
If computers are not available for students, use the interactivity to generate a dozen or so examples at appropriate levels, and write them on the board for the class to work on. Students could also work in pairs and create examples for their partners to work out, or work on the examples on this worksheet.
Once students are confident at finding the times table and the shift, ask them to work on the following questions:
- What can you say if the numbers are all odd?
What about if they are all even?
Or a mixture of odd and even?
- What can you say if the units digits are all identical?
What if there are only two different units digits?
- What can you say if the difference between two numbers is prime?
What can you say if the difference between two numbers is composite (not prime)?
Finally, bring the class together to discuss these questions and then generate a Level 4 example. Invite students to explain how they would tackle it.
Here is an account of one teacher's approach to using this problem.
Key questions
What is the same between numbers in a times table and numbers in the shifted times table?
Possible support
Perhaps start with the Factors and Multiples Game to practise working with multiples and factors. This could then be followed up by looking at the problem Remainders.
Possible extension
Here are some follow-up resources that may build on students' thinking about this problem:
What numbers can we make?
Imagine we have four bags containing a large number of 1s, 4s, 7s and 10s. What numbers can we make?
What Numbers Can We Make? printable sheet with Charlie and Alison's representations
What Numbers Can We Make? printable sheet without Charlie and Alison's representations
Imagine you had four bags containing a large number of 1s, 4s, 7s and 10s.
You can choose numbers from the bags and add them to make different totals. You don't have to use numbers from every bag, and there will always be as many of each number as you need.
Choose some sets of $3$ numbers and add them together.
What is special about your answers?
Can you explain what you've noticed?
Charlie and Alison came up with some ways to represent what was happening.
Charlie's representation:
All multiples of three can be represented as:
The numbers in the bags can be represented as:
Similarly, numbers which are two more than a multiple of three can be represented as:
When I choose three numbers, I end up with a multiple of three $+3$ which will be a multiple of three.
Alison's representation:
Since all multiples of three can be written in the form $3n$, the numbers in the bags can be written in the form $3n+1$.
Similarly, numbers which are two more than a multiple of three can be written in the form $3n+2$.
As long as I remember I'm working with multiples of three, I could call these numbers $+0$, $+1$ and $+2$ numbers for short.
When I choose three numbers, I'm adding together three $+1$s, so I end up with a multiple of three $+3$ which will be a multiple of three.
What if you choose sets of $4$ numbers and add them together?
What if you choose sets of $5$ numbers, $6$ numbers, $7$ numbers...?
What totals do you think it would be possible to make if you choose $99$ numbers? Or 100 numbers?
Can you use Charlie's and Alison's representations to convince yourself?
Printable NRICH Roadshow resource.
Next, you might like to work on What Numbers Can We Make Now? or Take Three From Five
Begin by exploring what happens when you add two, three, four... numbers chosen from a set of bags containing $2$s, $4$s, $6$s and $8$s. Can you explain your findings?
Lots of people added together three numbers and noticed something special! For example, Emma, from Interlakes Elementary, told us her findings:
I figured out that, if you kept adding the numbers together, they will always come to a multiple of 3 every time you do it.
Charlie, from St. Cecilia's Wandsworth, noticed:
What we did was: we started with 3 numbers, then we added them together, and we noticed that some were odd and some were even but they were all multiples of 3. Then we tried adding 4 numbers, and we found that the answers were 1 more than the numbers in the 3 times table. Choosing 5 numbers we got answers which were 2 more than the 3 times table. We guessed that adding 6 numbers would give answers back in the 3 times table.
Great observations! Bethan, Gareth and Aditya, from St. Nicolas CE Junior School, offered an explanation of this. Bethan wrote:
When you have your three numbers, say 4, 7 and 1, each of these numbers is 1 more than a multiple of 3.
So 3+1, 6+1 and 0+1.
Then when you add them together, you can add the 3, 6 and 0 together which makes a multiple of 3, plus the three 1s left over will add together to also make a multiple of 3.
This makes your overall answer a multiple of 3.
Good! (Is this related to either Charlie's or Alison's method?) Aditya used the same method to notice:
Adding together 99 numbers would give a multiple of 3, and 100 numbers would equal a multiple of 3 plus 1.
Brandyn from Garden International School considered what happened when he added sets of 3, 4, 5, 6 and 99 numbers from the bags below:
| 1 | 4 | 7 | 10 | TOTAL |
| 3 | 3 | |||
| 3 | 12 | |||
| 3 | 21 | |||
| 3 | 30 | |||
| 2 | 1 | 6 | ||
| 2 | 1 | 9 | ||
| 2 | 1 | 12 | ||
| 1 | 2 | 9 | ||
| 2 | 1 | 15 | ||
| 2 | 1 | 18 | ||
| 1 | 2 | 15 | ||
| 1 | 2 | 18 | ||
| 2 | 1 | 24 | ||
| 1 | 2 | 21 | ||
| 1 | 2 | 24 | ||
| 1 | 2 | 27 | ||
| 1 | 1 | 1 | 12 | |
| 1 | 1 | 1 | 15 | |
| 1 | 1 | 1 | 18 | |
| 1 | 1 | 1 | 21 |
Choosing four numbers from the bags above gave the following totals, all 1 more than (or 2 less than) multiples of 3:
| 1 | 4 | 7 | 10 | TOTAL |
| 4 | 4 | |||
| 4 | 16 | |||
| 4 | 28 | |||
| 4 | 40 | |||
| 3 | 1 | 7 | ||
| 3 | 1 | 10 | ||
| 3 | 1 | 13 | ||
| 1 | 3 | 13 | ||
| 3 | 1 | 19 | ||
| 3 | 1 | 22 | ||
| 1 | 3 | 22 | ||
| 1 | 3 | 25 | ||
| 3 | 1 | 31 | ||
| 1 | 3 | 31 | ||
| 1 | 3 | 34 | ||
| 1 | 3 | 37 | ||
| 2 | 2 | 10 | ||
| 2 | 2 | 16 | ||
| 2 | 2 | 22 | ||
| 2 | 2 | 22 | ||
| 2 | 2 | 28 | ||
| 2 | 2 | 34 | ||
| 2 | 1 | 1 | 13 | |
| 2 | 1 | 1 | 16 | |
| 2 | 1 | 1 | 19 | |
| 1 | 2 | 1 | 16 | |
| 1 | 2 | 1 | 19 | |
| 2 | 1 | 1 | 25 | |
| 1 | 1 | 2 | 19 | |
| 1 | 2 | 1 | 25 | |
| 1 | 2 | 1 | 28 | |
| 1 | 1 | 2 | 25 | |
| 1 | 1 | 2 | 28 | |
| 1 | 1 | 2 | 31 | |
| 1 | 1 | 1 | 1 | 22 |
Excellent. Thanks!
Why do this problem?
This problem offers students the opportunity to consider the underlying structure behind multiples and remainders, as well as leading to some very nice generalisations and justifications.
Possible approach
Display the image of the four bags (available as a PowerPoint slide).
Alternatively, you could start with this image, with 7s, 10s, 13s and 16s.
Key questions
Possible support
Begin by asking students to explore what happens when they add two, three, four... numbers chosen from a set of bags containing $2$s, $4$s, $6$s and $8$s. Can they explain their findings?
Possible extension
Take Three from Five and What Numbers Can We Make Now? are suitable follow-up problems.
Take Three From Five
Caroline and James pick sets of five numbers. Charlie tries to find three that add together to make a multiple of three. Can they stop him?
Take Three from Five printable sheet
This problem builds on What Numbers Can We Make?
Take a look at the video below.
Will Charlie always find three integers that add up to a multiple of 3?
If you can't see the video, click below to read a description.
Charlie invited James and Caroline to give him sets of five integers (whole numbers).
Each time he chose three integers that added together to make a multiple of 3:
| TOTAL | ||||||
| 3 | 6 | 5 | 7 | 2 | 18 | |
| 7 | 17 | 15 | 8 | 10 | 39 | |
| 20 | 15 | 6 | 11 | 12 | 33 | |
| 23 | 16 | 9 | 21 | 36 | 48 | |
| 99 | 57 | 5 | 72 | 23 | 228 | |
| 312 | 97 | 445 | 452 | 29 | 861 | |
| -1 | -1 | 0 | 1 | 1 | 0 |
Charlie challenged Caroline and James to find a set of five integers that didn't include three that added up to a multiple of 3.
Can you find a set of five integers that doesn't include three integers that add up to a multiple of 3?
If not, can you provide a convincing argument that you can always find three integers that add up to a multiple of 3?
You can test sets of five integers using the interactivity below.
Click here for a poster of this problem.
Although number theory - the study of the natural numbers - does not typically feature in school curricula it plays a leading role in university at first year and beyond. Having a good grasp of the fundamentals of number theory is useful across all disciplines of mathematics. Moreover, problems in number theory are a great leisure past time as many require only minimal knowledge of mathematical 'content'.
We are very grateful to the Heilbronn Institute for Mathematical Research for their generous support for the development of this resource.
Start with the problem What Numbers Can We Make?
Think of a simpler problem:
If you choose two integers from a set of three integers, you can always select two integers that add up to an even number. Can you explain why?
Miraya from Heckmondwike Grammar School in the UK wrote:
According to all numbers I have tried, I think it is not possible to find a set of five numbers that do not have a set of three that sum up to a multiple of three.
Samuel from Seely Primary School in England, Jimin (James) from BSKL in Malaysia, Harvey from St Nicholas in the UK, Ekaansh from Dulwich College Beijing in China, Kai and Wesley from Wilson's School in England, Ariel from Diocesan Girls' School in Hong Kong and Aditya from Bishop Vesey's Grammar School in the UK used the idea of remainders when dividing by 3. Ekaansh wrote:
I do not think this is possible. This is because any integers we pick would be one of these:
- Exactly divisible by 3 e.g. 3,6,9 etc.
- Multiple of 3 plus remainder 1 e.g. 4, 7, 10 etc.
- Multiple of 3 plus remainder 2 e.g. 5, 8, 11 etc.
Harvey represented the numbers in a different way, but the idea the same:
You can have three groups of numbers: multiples of three minus 1, multiples of three, and multiples of three plus one. If you continuously add or subtract three you can get one of three numbers: 1, 2, or 3.
Jimin (James) continued:
We only have to add up these [remainders] (1-2-0) because if they add up and make a number which is a multiple of 3, the left over 3s in the number will make a multiple of 3 anyways.
Samuel exaplined this idea using letters for the types of number:
I represented the numbers that are one more than a multiple of three as $x$, numbers that are 2 more than a multiple of 3 as $y$, and numbers that are a multiple of 3 as $z$.
$x$+$y$+$z$= a multiple of 3.
Example: 1+2+3=6
$z$+$z$+$z$=a multiple of 3
Example: 3+3+3=9
$y$+$y$+$y$=a multiple of 3
Example: 2+2+2=6
$x$+$x$+$x$=a multiple of 3
Example: 1+1+1=3
Since every number has to be either $x$, $y$ or $z$, and that these combinations work, it is impossible to produce a set of 5 whole numbers that any 3 of them do not add up to a multiple of 3.
This is because in a group of 5, it is not possible to have no groups of 3 [of the same type], whilst also not having one of each type.
This is Ariel's explanation of why there will always be three numbers that add up to a multiple of 3:
First, if there is at least 3 of a kind, there must be 3 integers that add up to a multiple of 3 because any 3 of a kind sums up to a multiple of 3.
Secondly, if there is no 3 of a kind, the combination of the remainders must be 2, 2, 1, in any order. In that case,there must be 3 integers that add up to a multiple of 3 since 0+1+2 sums up to a multiple of 3.
Therefore, there must be 3 integers that add up to a multiple of 3 no matter what 5 integers you choose.
To be absolutely sure that it's impossible, Aditya found all of the possible sets of remainders that 5 numbers could have:
This idea of using remainders is very useful in number theory and is called modular arithmetic.
Emily from Garden International School in Malaysia, Rin from Wren Academy in England, Mahdi from Mahatma Gandhi International School in India and Sunhari all used the same idea, but expressed the numbers using algebra. This is Emily's work:
[All] integer[s] can be divided in three groups which are $3n,$ $3n+1$ or $3n+2$. $n$ can be any whole number.
We have 2 [ways of making a multiple of 3]
The 1st option is we have at least one number from each group. We can use the letters $n,$ $m$ and $l$ to show the different numbers. So when we add up the numbers it'll look something like this, $$3n+(3m+1)+(3l+2)= 3(n+m+l)+3= 3(n+m+l+1)$$As you can see this number is definitely a multiple of $3$ because we can look at the
numbers in the bracket as [an] integer and $3$ has to multiply that number. Therefore $3(n+m+l+1)$ can be divided by $3$.
Note that $3n, 3n+1$ and $3n+2$ represent a multiple of $3$, the number $1$ more than that multiple of $3$ and the number $2$ more than that multiple of $3$. That is why it is important to use $m$ and $l$ as well as $n$.
The second option is we have at least three numbers from one group.
Sunhari showed this option algebraically:
$(3t+1) + (3j+1) + (3w+1)$
$= 3t + 1 + 3j + 1 + 3w + 1$
$= 3(t+j+w) + 3$
Therefore, it would be a multiple of $3$.
$(3x+2) + (3g+2) + (3d+2)$
$= 3x + 2 + 3g + 2 + 3d + 2$
$= 3(x+g+d) + 6$
Therefore, it would be a multiple of $3$.
Rin explained why this means that there will always be three numbers that add up to a multiple of three.
- If there are three or more multiples of $3$ within the five given numbers, we can add those to make a multiple of $3.$
- If there are one or two multiples of $3$, other three numbers must be either $3n+1$ or $3n+2.$ If the remaining numbers include:
- Three or more $3n+1$ s
We can add these three to get a multiple of 3. - Three or more $3n+1$ s
Similarly, we can add these to get a multiple of 3. - Otherwise
We can pick one each from groups of $3n, 3n+1, 3n+2$ and add together.
- Three or more $3n+1$ s
- If there is no multiple of 3, the five numbers can be written as either $3n+1$ or $3n+2.$
For any combination of five numbers, three or more must be in the form of $3n+1$ or $3n+2.$
Adding numbers in the same group would give a multiple of $3.$
Therefore for every combination of five numbers, there are three numbers that add to give a multiple of $3.$
Mahdi used the same idea, but with $-1$ instead of $2$. Everything else works out the same.
Why do this problem?
This problem looks like a number task, possibly involving revision about multiples, but it becomes a question about establishing why something can never happen, and creating a convincing argument to show this. Students are used to considering the cases where numbers are either odd or even, and here they are being introduced to the idea that numbers can also be categorised into 1 more than, 2 more than, or exactly a multiple of 3. This provides an introduction to number theory and a possible springboard to the ideas of modulo arithmetic.
Algebraic proofs are often seen as the "gold standard" of mathematical rigour, but here is a nice example in which the visual proof can offer a deeper insight into the structure of the numbers modulo 3.
Possible approach
Allow negative numbers, as long as they will allow you negative multiples of $3$ (and zero).
At some stage there may be mutterings that it's impossible. A possible response might be:
"Well if you think it's impossible, there must be a reason. If you can find a reason then we'll be sure."
Once they have had sufficient thinking time, bring the class together to share ideas.
If it hasn't emerged, share with students Charlie's representation from What Numbers Can We Make?
All numbers fall into one of these 3 categories:
Type A (multiple of $3$, i.e. of the form $3n$)
Type B (of the form $3n+1$)
Type C (of the form $3n+2$)
We have found that trying to use algebraic expressions as above, is tricky - students often end up with n having two or more values at once. For example, when considering the general sum of a type A, a type B and a type C number, students tend to write $3n+(3n+1)+(3n+2)$ without realising that this restricts them to the sum of three consecutive numbers. Instead students need to realise that they should write something of the form $3n+(3m+1)+(3p+2)$.
Students are unlikely to know the notation of modular arithmetic, but the crosses notation above is sufficient for the context, and it suggests a geometrical image that students can use in explaining their ideas.
"Which combinations of A, B and C give a multiple of three?"
"Can you find examples in our list on the board where you gave me one of those combinations?"
A few minutes later...
"Great, then all you have to do is find a combination of As, Bs and Cs that doesn't include AAA, BBB, CCC or ABC!"
Later still...
"It's impossible! All the combinations will include either AAA, BBB, CCC or ABC!"
"OK, but can you prove it? Can you convince me that it's impossible?"
Possible support
Possible extension
What size set of integers do you need so that you can always get a multiple of $5$ when selecting $5$ of them?
What we like to see
We have written an article on what we are looking for when we decide which solutions to publish.
Explain your methods clearly for other school students to read.
Give reasons and convincing arguments or proofs where you can.
You can share your work with us by typing into the form or uploading a file (must be less than 10MB.)
What can I upload?
- Word documents
- PDF files
- Images - any format
- Screenshots
- Photos of written work
If your work is on another app
You can also send us a link to your work on:
- Youtube/Vimeo
- Google Docs
- Sharepoint/Office 365
- Anywhere sensible on the internet!
How we use your information
By uploading your solution here you are giving us permission to publish your work, either as a whole or edited extracts, on the NRICH website and in associated educational materials for students and teachers, at our discretion.
For our full terms of use regarding submitted solutions and user contributions please see https://nrich.maths.org/terms
Your information (first name, school name etc) is optional. If supplied, it may be used for attribution purposes only if your work is published on the website. Data that you supply on this form (e.g. age if supplied, location if supplied) may also be anonymised and used for evaluation and reporting.
For more information about the University's policies and procedures on handling personal information, and your rights under data protection legislation, please see https://www.information-compliance.admin.cam.ac.uk/data-protection/general-data.
What numbers can we make now?
Imagine we have four bags containing numbers from a sequence. What numbers can we make now?
What Numbers Can We Make Now? printable sheet
This problem follows on from What Numbers Can We Make?
The interactivity below creates sets of bags similar to those in What Numbers Can We Make?
Investigate what numbers you can make when you choose three numbers from the bags. Once you think you know what is special about the numbers you can check your answer.
You can also find what is special when you choose four, five or six numbers.
When you have an efficient strategy, test it by choosing 99 or 100 numbers.
Always enter the biggest possible multiple. The "plus" number may include zero.
Can you explain your strategies?
And finally...
If the bags contained 3s, 7s, 11s and 15s, can you describe a quick way to check whether it is possible to choose 30 numbers that will add up to 412?
There are a few related problems that you might like to try:
This problem follows on from What Numbers Can We Make?, so you could start by exploring that first.
Henry, from St. Hugh's, answered our question at the end:
If the bags contained 3s, 7s, 11s and 15s, can you describe a quick way to check whether it is possible to choose 30 numbers that will add up to 412?
He said the following:
It is impossible to make 412.
The starting number is 3 and the difference between the numbers is 4.
If I choose 30 numbers and add them all up, I will get a number that is 30x3=90 more than a multiple of 4.
But, 90÷4=22 remainder 2, so I will get a number that is 2 more than a multiple of 4.
But since 412 is a multiple of 4 (not 2 more than a multiple of 4), it won't work.
Well spotted! Luke, from Cottenham Village College, said this in a more algebraic way, using a tool called 'modular arithmetic':
All of our numbers are of the form 4x-1, for x=1, 2, 3 or 4. Therefore the sum of 30 of them comes to $4(x_1+x_2+\dots +x_{30})-30$, which is 2 mod 4 (i.e. 2 more than a multiple of 4). But 412 is 0 mod 4 (i.e. 0 more than a multiple of 4), so this sum cannot be equal to 412.
If you are unfamiliar with Modular Arithmetic, you might like to take a look at this introductory article.
Luke also gave his thoughts on the interactivity:
The numbers in the bag always form part of a linear arithmetic sequence, and so the number in the x-th bag is mx+c. Consecutive numbers are always a fixed distance m apart. This means that we can read off the value of m easily, and then find the value of c. We can then conclude that, if you choose z numbers from the bags, their sum will be of the form $m(x_1+x_2+\dots +x_z) + cz$, as all the numbers are of the form mx+c, for different values of x. This is obviously cz more than a multiple of m.
To illustrate this method with an example, take the numbers in the bag to be 1, 4, 7 and 10, as in the original example, with z=4.
Their differences are all a multiple of 3, so by analysing them mod 3 (i.e. by looking at their remainders when they are divided by 3) we find that they are all of the form 3x+1.
As z=4 and c=1, they must be cz=4 more than a multiple of 3.
Since 4 is 1 mod 3 (i.e. dividing 4 by 3 gives remainder 1), 4 numbers selected from the bags must add to give 1 more than a multiple of 3.
Nice!
Why do this problem?
This problem offers students the opportunity to consider the underlying structure behind multiples and remainders, as well as leading to some very nice generalisations and justifications.
Possible approach
Key questions
Possible support
Begin by asking students to explore what happens when they add numbers chosen from a set of bags containing 2s, 4s, 6s and 8s.
They could then consider what happens when they add numbers chosen from a set of bags containing 1s, 11s, 21s and 31s.
Can they explain their findings?
Possible extension
There are a few related problems that students could work on next:
Take Three from Five
Shifting Times Tables
Charlie's Delightful Machine
A Little Light Thinking
Remainders
Where Can We Visit?
Cinema Problem
Charlie's delightful machine
Here is a machine with four coloured lights. Can you develop a strategy to work out the rules controlling each light?
You may wish to look at Shifting Times Tables before trying this problem.
Can you work out how to switch the lights on?
Charlie's Delightful Machine has four coloured lights. Each light is controlled by a rule.
If you choose a number that satisfies the rule, the light will go on.
Some numbers may turn on more than one light!
Start by exploring Level 1. Type in some numbers and see which lights you can switch on.
To start again with a new set of rules, click the Level 1 button.
Can you develop a strategy to work out the rules controlling each light?
Once you have a strategy, challenge yourself to find some four-digit numbers that turn on each light.
Once you are confident that you can work out the rules for Level 1 lights, have a go at A Little Light Thinking, where you can explore how to turn on several lights at once.
You may also wish to explore the Level 2 and 3 lights (which use a different type of sequence) in the same way.
You may also be interested in the other problems in our Cracking Codes Feature.
You could start by exploring Shifting Times Tables to get a feel for the sequences that turn on the lights.
Try exploring just one light at a time.
Vinay from Ripley Valley State Secondary College in Australia, Leala from Notredame in the UK, Tyler from Burnside Primary School in Australia and R from the UK worked out the rules for specific versions of the game. Every time you play, the rules are different, so people's answers are different. Here are some examples of the sets of rules they found.
Tyler:
Blue light turned on by repeating pattern of adding 2 starting from 1 so the pattern is 1,3,5,7,9,11 and so on.
Yellow is every 3 starting from 2, so 2, 5 8, 11, 14, 17,20 etc.
Green is every 9 starting from 2, so 2, 11, 20, 29, 38, 47 etc
Red is every 8 starting from 5, so 5, 13, 21, 29, 37, 45 etc.
Leala:
Yellow- multiples of 3
Red- going up in 8 them minus 2 (8$n$-2)
Blue- going up in 8 then minus 5 (8$n$-5)
Green- going up in 6 and then minus 2 (6$n$-2)
Shaunak from Ganit Manthan, Vicharvatika in India explained how to find the rules. You can read Shaunak's method below, or watch Shaunak's video by clicking here.
Here is a strategy to work out the rules controlling the lights:
1: Find the rules for the Yellow light - Start by keeping zero in the box. Keep on increasing the number in the box by one. Note down the first 5 numbers that satisfy the rule for the Yellow light.
Next, find the difference between any two consecutive numbers in this list. Call this difference $n.$
Then, find the remainder obtained by dividing any number from this list [by $n$]. Call this number $b.$
The rule is - Numbers $b$ more than [a multiple of] $n.$
So, any number that can be expressed as $a\times n + b,$ where $n$ and $b$ are those computed above, and a is any number, satisfies the condition for the Yellow light.
In a similar manner, one can find the rules for the Red, Blue and Green lights. These three also follow the $a\times n + b$ property.
Example:
I started with 0. The first five numbers that satisfy the rule for the Yellow light are - 2, 5, 8, 11, and 14.
Now, I need to find $n,$ which is the difference between two consecutive numbers in this list. 2 and 5 are consecutive numbers in this list, so
$n$ = 5 - 2 = 3
Next, I should find $b$, which is the remainder obtained by dividing $n$ by any number in this list. Because 11 is a number in the list, and $n$ is 3, so the remainder obtained is 2 (from 11$\div$3).
The rule is - Numbers 2 more than multiples of 3.
So, any number that can be expressed as 3$a$ + 2, satisfies the above rule.
If $a$ is 343, I will get a number larger than 999, or a 4-digit number.
Let me put $a$ as 343 and see if the Yellow light gets switched on...Yes! It worked!
Using the same strategy one can find the rules and properties for Red, Blue and Green lights.
Why do this problem?
Many standard questions give exactly the information required to solve them. In this problem, students are encouraged to be curious, to go in search of the information they require, and to work in a systematic way in order to make sense of the results they gather.
The problem could be used to reinforce work on recording and describing linear and quadratic sequences.
Possible approach
This task will require students to have access to computers. If this is not possible, Four Coloured Lights provides students the opportunity to make sense of numerical rules without the need for computers.
- Odd numbers
- Numbers which are 1 more than multiples of 4
- Numbers which are 2 less than multiples of 5
- Numbers which are 3 more than multiples of 7
Level 1 rules are linear sequences of the form $an+b$, with a and b between 2 and 12.
Students could then work in pairs at a computer, trying to light up each of the lights. Challenge them to develop an efficient strategy for working out the rules controlling each light.
While the class is working, note any particularly good ways of recording or working systematically, and highlight them to the rest of the class.
Bring the class together to share insights and conclusions before moving on to A Little Light Thinking, in which students are invited to find sequences that turn several Level 1 lights on simultaneously.
Key questions
Which numbers will you try first?
Can you suggest a number bigger than 1000 that you think will turn on the light?
Possible support
Shifting Times Tables offers students a way of thinking about linear sequences and opportunities to explore how they work.
Students could use a 100 square to record which lights turn on for each number they try.
Possible extension
Level 2 rules are quadratic sequences of the form $an^2+bn+c$ with a=0 or 1
Level 3 rules are quadratic sequences of the form $an^2+bn+c$ with a=0, 0.5, 1, 2 or 3.
Level 3 sequences can be used as a starting point for some detailed exploration into graphical representations of quadratic functions.
Got It
A game for two people, or play online. Given a target number, say 23, and a range of numbers to choose from, say 1-4, players take it in turns to add to the running total to hit their target.
Got It is an adding game for two players. You can play against the computer or with a friend. It is a version of a well-known game called Nim.
Start with the Got It target 23.
The first player chooses a whole number from 1 to 4.
Players take turns to add a whole number from 1 to 4 to the running total.
The player who hits the target of 23 wins the game.
Play the game several times.
Can you find a winning strategy?
Can you always win?
Does your strategy depend on whether or not you go first?
To change the game, choose a new Got It target or a new range of numbers to add on.
Test out the strategy you found earlier. Does it need adapting?
Can you work out a winning strategy for any target?
Can you work out a winning strategy for any range of numbers?
Is it best to start the game? Always?
Away from the computer, challenge your friends:
One of you names the target and range and lets the other player start.
Extensions:
Can you play without writing anything down?
Consider playing the game where a player CANNOT add the same number as that used previously by the opponent.
Try to work out the 'stepping stones' that you must 'land on' on your way to the target?
Alter the settings on the game to have a lower target and a shorter range of numbers (e.g. a target of $10$ using the numbers $1$ and $2$). As you play, note down the running totals to refer back to later.
Students at Clifton Hill Primary in Australia worked hard to beat the computer at Got It with a target of 23, and with numbers 1, 2, 3 and 4 to choose from.
J and C said:
You can win the game with a target number of 23 and range numbers of 1-4 by trying as hard as possible to land on the number 18. By landing on 18, you make your opponent off by 1 of getting the end number. If you get the number 18, your opponent will be stuck and you have a guaranteed win.
Danica and Eve took this a little bit further:
Can you find a winning strategy?
Yes, you can by getting to 13 then the other player has to say their number (1-4) you can get to 18.
After that, no matter what number they say there will always be a way for you to get to 23.
Leon and Jack built on this even further:
There are three key numbers:
8
13
18
Firstly, you have to be the one that gets the total to eight. You can do this by starting with 3 and the opponent has to let you get to 8. Once you have accomplished that, it is their turn with a total of 8. They then can't stop you from getting to 13. After you get 13 they can't stop you from getting to 18. After this, they can't stop you from reaching 23.
So, in fact rather than there being three ‘key numbers’, it sounds like you’re saying there are four key numbers: 3, 8, 13, 18.
Golden Eagles Class at Ditchingham Primary Academy described their strategy in a similar way:
We found that it was easier to win once we had found the stepping stones for the target number. This was a key number that if we reached we could win any game.
As we could add up to 4 each time the difference between each number was 5. The stepping stones were 3, 8, 13, 18 for 23.
For example, if we started with 3, our opponent could only make it up to 7, we could then add 1 to make 8. The most they could then make is 12 but with all variation of numbers we could then make 13 and so on up to 23.
When we played the computer using this strategy and we went first we always won, however if the computer started we always lost. It was possible to beat an opponent if they went first, but only if they hadn't worked the stepping stones out. Once they had we always drew.
We tried using 17 as a target number and found stepping stones at 2, 7, 12 using the numbers 1-4. This was again as the difference between these numbers was 5.
We would like to try dropping the 4, using numbers 1-3 and seeing if the stepping stones reduced to a difference of 4.
I like the fact that you are making a conjecture about how you could apply your strategy to a version of the game using only numbers 1, 2 and 3, Golden Eagles Class. This is exactly what mathematicians do!
This idea of ‘key numbers’ of ‘stepping stones’ is crucial in this game. Mateusz and Joseph from St Ann’s Primary agreed with this approach, so did Amelie and Sam from St Francis of Assisi Primary School; Gabriel from Yavneh College; Alaric from Haydon Wick Primary; Harry from St Michael’s Preparatory School; Ruby, Alice, Meiyla, Lilly, Olivia and Sophie from Anston Greenland’s Primary; Joy, Akosua, Asuo and Kumi from Torrens Valley Christian School in Australia; as well as three groups of students from Ganit Kreeda, Vicharvatika, India.
Anirudh from Hamilton Primary School shared this video, in which he explains how he worked backwards to find the stepping stones:
And in this video, Kaana from Ganit Kreeda explains the importance of multiples of 5:
Can you see how Anirudh’s and Kaana’s solutions are connected?
Joseph from Jesmond Park Academy sent a very comprehensive solution:
I initially approached this problem by just playing some games with the computer and tried to recognise some patterns. I started by playing first but then swapped to the computer playing first. It was here that I noticed that it would always start with the same first number depending on the target number.
I noted this down and also noted that it would try to reach certain values consistently. I called these 'landing values' and wrote them down.
From here, I noticed that there was a fixed distance between each landing value that was 1 greater than the largest number I could choose. This revelation led to further investigations that led to the process below.
For anyone who wanted to consider solving this problem, or ones like it, I think the best first step is to just play around and consider different values. After you've considered different values, you can assess whether there is a pattern or not. This pattern is the real starting off point for finding a general solution.
Thank you, Joseph, what a lovely description of the process you went through. We agree that ‘playing around’ with a new problem is a great way to start. The exploration then leads to some noticing, as Joseph said, and then some more systematic working, some generalising and even proof.
Here is Joseph’s general strategy for winning at Got It:
The numbers that are chosen to be added up range from 1 -> n, where n is a positive integer and the spaces between 1 and "n" are integers. (In fact I wonder whether they have to be consecutive numbers, Joseph...)
For example, "1, 2, 3, 4" where n is 4.
The player will have a target number, which we will call "m". To begin, player 1 will write down the target and subtract (n+1) away from the number "m" until there is a number that they are able to choose, we will call this "b".
For example, consider the target is 22 (so m=22) and the player can add up to 4 (so n=4), they will subtract 5 (n+1) until they reach the number 2 (so b=2).
Player 1 will choose this number and begin the game. From this point forward, it is Player 1's objective to reach the next multiple of (n+1) that starts from "b". In our example, these "Landing Values" would be 7, 12, 17 and finally, 22. Player 1 will always be able to force a Landing Value on their turn assuming they started from "b" and their opponent plays perfectly.
If player 1 aims for these numbers, Player 2's choice will not matter as they will end up unable to reach the target number.
The exception to this trend comes if the target number is a multiple of (n+1). This is because you can't keep subtracting (n+1) to reach the initial number "b" as you will eventually reach (n+1) and the next number would be 0.
For example, if we could choose to add up numbers between 1 and 4, if the target was 10, we could subtract 5 (n+1) once.
Following this, subtracting 5 again would reach 0, which isn't an option with our initial conditions.
Thus, the first player would have to choose any number between 1 and 4.
Assuming that there is a perfect opponent, they would reach the multiple of (n+1) instead, in this example it would be 5. The game would continue as stated previously, resulting in player 2 winning instead.
Thus, you can reach the conclusion that it is only sensible to be Player 1 if the target number is not a multiple of (n+1). If it is, then you should choose to be Player 2.
Abishai expressed a general solution in a very similar way, so did Xavier, and so did students from Ganit Kreeda, India. Thank you to you all. How fantastic that we have used our mathematics to find a winning strategy that will ALWAYS work when playing Got It.
Why play this game?
Got It is a motivating context in which learners can apply simple addition and subtraction. However, the real challenge here is to find a winning strategy that always works, and this involves working systematically, conjecturing, refining ideas, generalising, and using knowledge of factors and multiples.
Possible approach
This problem featured in an NRICH Secondary webinar in June 2021.
Introduce the game to the class by inviting a volunteer to play against the computer. Do this a couple of times, giving them the option of going first or second each time (you can use the "Change settings" button to do this).
Ask the students to play the game in pairs, either at computers or on paper. Challenge them to find a strategy for beating the computer. As they play, circulate around the classroom and ask them what they think is important so far. Some might suggest that in order to win, they must be on 18. Others may have thought further back and have ideas about how they can make sure they get to 18, and therefore 23.
After a suitable length of time bring the whole class together and invite one pair to demonstrate their strategy, explaining their decisions as they go along. Use other ideas to refine the strategy.
Demonstrate how you can vary the game by choosing different targets and different ranges of numbers. Ask the students to play the game in pairs, either at computers or on paper, using settings of their own choice. Challenge them to find a winning strategy that will ensure they will always win, whatever the setting.
Key questions
Possible extension
Possible support
An introduction to modular arithmetic
The best way to introduce modular arithmetic is to think of the face of a clock.
The numbers go from $1$ to $12$, but when you get to "$13$ o'clock", it actually becomes $1$ o'clock again (think of how the $24$ hour clock numbering works). So $13$ becomes $1$, $14$ becomes $2$, and so on.
This can keep going, so when you get to "$25$ o'clock'', you are actually back round to where $1$ o'clock is on the clock face (and also where $13$ o'clock was too).
So in this clock world, you only care where you are in relation to the numbers $1$ to $12$. In this world, $1, 13, 25, 37, \ldots$ are all thought of as the same thing, as are $2, 14, 26, 38, \ldots$ and so on.
What we are saying is "$13=1+$ some multiple of $12$", and "$38=2+$ some multiple of $12$", or, alternatively, "the remainder when you divide $13$ by $12$ is $1$" and "the remainder when you divide $38$ by 12 is 2''. The way we write this mathematically is $13\equiv 1 \text{ mod } 12$, $38\equiv 2 \text{ mod } 12$, and so on. This is read as "$13$ is congruent to $1$ mod (or modulo) $12$" and "$38$ is congruent to $2 \text{ mod } 12$".
But you don't have to work only in mod $12$ (that's the technical term for it). For example, you could work mod $7$, or mod $46$ instead if you wanted to (just think of clocks numbered from $1$ to $7$ and $1$ to $46$ respectively; every time you get past the biggest number, you reset to $1$ again).
Let's go back to the normal clock face with the numbers $1$ to $12$ on it for a moment. Mathematicians usually prefer to put a $0$ where the $12$ would normally be, so that you would usually write (for example) $24\equiv 0 \text{ mod } 12$ rather than $24\equiv 12 \text{ mod } 12$, although both of these are correct. That is, we think of a normal clock face as being numbered from $0$ to $11$ instead. This makes sense: we'd normally say that $24$ leaves a remainder of $0$ when we divide by $12$, rather than saying it leaves a remainder of $12$ when we divide by $12$!
Let's be a bit more formal. In general, if you are working in mod $n$ (where $n$ is any whole number), we write $a\equiv b \text{ mod } n$ if $a$ and $b$ leave the same remainder when you divide them by $n$. This is the same as saying that we write $a\equiv b \text{ mod } n$ if $n$ divides $a-b$. (Look at what we did earlier to see that this definition fits with our examples above.)
So far, we've only talked about notation. Now let's do some maths, and see how congruences (what we've described above) can make things a bit clearer.
Here are some useful properties. We can add congruences. That is, if $a\equiv b \text{ mod } n$ and $c\equiv d \text{ mod } n$, then $a+c\equiv (b+d) \text{ mod } n$. Why is this? Well, $a\equiv b \text{ mod } n$ means that $a=b+k n$, where $k$ is an integer. Similarly, $c\equiv d \text{ mod } n$ means that $c=d+l n$, where $l$ is an integer. So $a+c=(b+k n)+(d+l n)=(b+d)+(k+l)n$, so $a+c\equiv (b+d) \text{ mod } n$. For example, $17\equiv 4 \text{ mod } 13$, and $42\equiv 3 \text{ mod } 13$, so $17+42\equiv 4+3\equiv 7 \text{ mod } 13$. Note that both of the congruences that we're adding are mod $n$, and so is the answer - we don't add the moduli.
Now you prove that if $a\equiv b \text{ mod } n$ and $c\equiv d \text{ mod }n$ then $a-c\equiv (b-d) \text{ mod } n$. Also, prove that we can do something similar for multiplication: if $a\equiv b \text{ mod }n$ and $c\equiv d \text{ mod } n$, then $a c\equiv b d \text{ mod } n$. You can prove this in the same way that we used above for addition. Again, both of the congruences that we're multiplying are mod $n$, and so is the answer - we don't multiply the moduli. Can you come up with an example to disprove the claim that $a\equiv b \text{ mod } n$ and $c\equiv d \text{ mod } m$ means that $a c \equiv bd \text{ mod } mn$?
Division is a bit more tricky: you have to be really careful. Here's an example of why. $10\equiv 2 \text{ mod } 8$. But if we "divide both sides by 2", we'd have $5\equiv 1 \text{ mod } 8$, which is clearly nonsense! To get a true congruence, we'd have to divide the $8$ by $2$ as well: $5\equiv 1 \text{ mod } 4$ is fine. Why? Well, $a\equiv b \text{ mod } n$ means that $a=b+k n$ for some integer $n$. But now this is a normal equation, and if we're going to divide $a$ by something, then we have to divide all of the right-hand side by $2$ as well, including $k n$. In general, it's best not to divide congruences; instead, think about what they really mean (rather than using the shorthand) and work from there.
Things are quite special if we work mod $p$, where $p$ is prime, because then each number that isn't 0 mod $p$ has what we call an inverse (or a multiplicative inverse , if we're being fancy). What that means is that for each $a\not\equiv 0 \text{ mod } p$, there is a $b$ such that $a b\equiv 1 \text{ mod } p$.
Let's think about an example. We'll work mod $7$. Then really the only non-zero things are $1, 2, 3, 4, 5$ and $6$ (because every other whole number is equivalent to one of them or $0$). So let's find inverses for them. Well, $1$ is pretty easy: $1\times 1\equiv 1 \text{ mod } 7$. What about $2$? $2\times 4\equiv 1 \text{ mod } 7$. So $4$ is the inverse of $2$. In fact, we can also see from this that $2$ is the inverse of $4$ - so that's saved us some work! $3\times 5\equiv 1 \text{ mod } 7$, so $3$ and $5$ are inverses. And finally, $6\times 6\equiv 1 \text{ mod } 7$, so $6$ is the inverse of itself. So yes, each of the non-zero elements mod $7$ has an inverse. Try some primes out yourself: $11$ and $13$ are fairly small! If you're feeling confident, see whether you can discover which numbers have inverses mod $4$, or mod $6$, or mod $8$. What about mod $15$? Do you notice any patterns?
To prove this, things are going to get a tiny bit more tricky, so I'm going to save the proof for the end and first give an example of using congruences to do useful mathematics.
Suppose we're given the number $11111111$ and someone asks us whether it's divisible by $3$. We could try to actually divide it. But you probably know a much easier method: we add up the digits and see whether that's divisible by $3$. There's a whole article about this sort of divisibility test here . Let's prove this using congruence notation.
Suppose that our number is $a_n 10^n+a_{n-1}10^{n-1}+\ldots+10a_1+a_0$, so it looks like $a_n a_{n-1}\ldots a_1 a_0$. Then the sum of its digits is $a_n+a_{n-1}+\ldots+a_1+a_0$. We'd like to prove that $a_n10^n+a_{n-1}10^{n-1}+\ldots+10a_1+a_0$ is divisible by $3$ if and only if $a_n+a_{n-1}+\ldots+a_1+a_0$ is divisible by $3$. Now we notice that $10\equiv 1 \text{ mod } 3$, so $10\times 10\equiv 1 \text{ mod } 3$, and more generally $10^k\equiv 1 \text{ mod } 3$ for all $k$. Using our results from earlier about adding and multiplying congruences, we discover
$$ a_n10^n+a_{n-1}10^{n-1}+\ldots+10a_1+a_0\equiv a_n+a_{n-1}+\ldots+a_1+a_0 \text{ mod } 3 $$ So if our number is divisible by $3$ (that is, if $a_n10^n+a_{n-1}10^{n-1}+\ldots+10a_1+a_0\equiv 0 \text{ mod } 3$), then certainly so is the sum of its digits, and vice versa, as we wanted! The congruence notation hasn't really done any of the maths for us, but it's hopefully made it a bit easier to write out the proof clearly. See whether you can use the notation to prove any of the other divisibility tests in that article.
Now for the proof I promised you earlier. We're going to show that if $a$ and $n$ have no common factors, then $a$ has a multiplicative inverse mod $n$ (reminder: that means a number $b$ such that $a\times b\equiv 1 \text{ mod } n$). In particular, if $n$ is prime, then its only factor apart from 1 is itself, so saying "$a$ and $n$ share no common factors'' is just the same as saying "$a$ isn't divisible by $n$'', that is, $a\not\equiv 0 \text{ mod } p$: this is what we had above. I'm going to assume that you know about using Euclid's algorithm to solve equations of the form $a x+b y=1$ where $a$ and $b$ have no common factors. There's a really good article explaining this here , so have a read, and then come back.
If you're reading this far, then hopefully you'll agree that if $a$ and $n$ share no common factors, then we can find $x$ and $y$ such that $a x+n y=1$. (The fancy name for this is Bezout's Theorem .) So we've got our $x$ and $y$ such that $a x+n y=1$. We can rewrite this as $a x=1-y n$, and now let's use the congruence notation from earlier: we have $a x\equiv 1 \text{ mod }n$. So now $x$ is the multiplicative inverse of $a \text{ mod } n$, and we're done!
Here's a challenge: use this technique based on Euclid's algorithm to find the inverse of $14 \text{ mod } 37$.
Understanding this is the beginning of a branch of mathematics called Number Theory, which contains some beautiful, fascinating and amazing theorems. Enjoy!
This article is based on a contribution to Ask NRICH by Matthew Buckley.