List

Working with Numbers

 

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?

Exploring and noticing Working systematically Conjecturing and generalising Visualising and representing Reasoning, convincing and proving
Being curious Being resourceful Being resilient Being collaborative

Problem

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.

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?

Exploring and noticing Working systematically Conjecturing and generalising Visualising and representing Reasoning, convincing and proving
Being curious Being resourceful Being resilient Being collaborative

Problem

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.
 

Image
Four bags, containing 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:

Image
What numbers can we make?

The numbers in the bags can be represented as:

Image
What numbers can we make?

Similarly, numbers which are two more than a multiple of three can be represented as:

Image
What numbers can we make?

When I choose three numbers, I end up with a multiple of three $+3$ which will be a multiple of three.

Image
What numbers can we make?

 



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



 

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?

Exploring and noticing Working systematically Conjecturing and generalising Visualising and representing Reasoning, convincing and proving
Being curious Being resourceful Being resilient Being collaborative

Problem

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.

Did you know ... ?

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.

 

What numbers can we make now?

Imagine we have four bags containing numbers from a sequence. What numbers can we make now?

Exploring and noticing Working systematically Conjecturing and generalising Visualising and representing Reasoning, convincing and proving
Being curious Being resourceful Being resilient Being collaborative

Problem

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:

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?

Exploring and noticing Working systematically Conjecturing and generalising Visualising and representing Reasoning, convincing and proving
Being curious Being resourceful Being resilient Being collaborative

Problem

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.

 

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.

Exploring and noticing Working systematically Conjecturing and generalising Visualising and representing Reasoning, convincing and proving
Being curious Being resourceful Being resilient Being collaborative

Problem

Got It poster

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.

 

Age
14 to 18
| Article by
Vicky Neale
| Published

An introduction to modular arithmetic



The best way to introduce modular arithmetic is to think of the face of a clock.

Image
An introduction to modular arithmetic

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).

Image
An introduction to modular arithmetic

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).

Image
An introduction to modular arithmetic

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.