More adventures with modular arithmetic
Problem
This problem follows on from Clock Arithmetic.
Start by considering arithmetic modulo 7.
Consider $20 \text{ mod } 7$, $60 \text{ mod 7}$ and $80 \text{ mod 7}$.
Is $80 \text{ mod } 7$ the same as $20 \text{ mod } 7 + 60 \text{ mod } 7?$
Consider other pairs of numbers $A \equiv a \text{ mod } 7$ and $B \equiv b \text{ mod }7$.
Is it always true that $A+B \equiv (a + b) \text{ mod } 7?$
What if we have $A \equiv a \text{ mod }n$ and $B \equiv b \text{ mod }n?$
Consider $4 \text{ mod } 7$, $20 \text{ mod 7}$ and $80 \text{ mod 7}$.
Is $80 \text{ mod } 7$ the same as $(4 \text{ mod } 7)\times (20 \text{ mod } 7)$?
If $A \equiv a \text{ mod }n$ and $B \equiv b \text{ mod }n$ is it always true that $AB \equiv ab \text{ mod }n$? Can you use the proof sorter for $A+B$ to help you construct a similar proof for $A \times B$? Once you have tried this, click the button below to compare your proof to ours.
If $B \equiv b \text{ mod } n$ then $B=b +nq$ for some integer $q$
$AB=(a+np)(b+nq)$
$AB=ab + npb + nqa + n^2 pq$
$AB = ab + n(pb+qa+npq)$
$ab + n(pb+qa+npq)$ has the form $ab + nK$
$ab + n(pb+qa+npq) \equiv ab \text{ mod }n$
Therefore $AB \equiv ab \text{ mod }n$
Equations with modulo arithmetic
Consider the equation $3x \equiv 1 \text{ mod } 7$ where $x<7$. By considering $x=0, 1, ... , 6$ find a possible value of $x$.
Find numbers that solve $3x \equiv b \text{ mod } 7$ for $b=2, 3, 4, 5, 6$.
Find numbers that solve $6x \equiv b \text{ mod } 7$ for $b=1, 2, 3, 4, 5, 6$.
Find numbers that solve $4x \equiv b \text{ mod } 10$ for $b= 1, 2, ... , 9$.
Can you find a number $a$ so that $ax \equiv b \text{ mod } 10$ has a solution for every $b=1, 2, ... , 9$?
You should have discovered that sometimes it is possible to find solutions to modular arithmetic equations, and sometimes it isn't. The interactivity below can be used to model what is happening when finding multiples of a number in different modulos.
You can change the number of dots by using the slider (which represents the modulo we are working in). Choose a starting point and drag to another point, then see what happens as the jumps are repeated.
For example, to model $4x \equiv b \text{ mod }10$, you can change the number of dots to $10$ and then drag between two dots which are 4 spaces apart. This shows that only 5 out of the 10 dots are visited, which shows that $4x \equiv b \text{ mod }10$ only has solutions for 5 values of $b$.
Investigate other equations of the form $ax \equiv b \text{ mod } n $, where $0 \le x \le n-1$.
Can you find a condition for solutions to exist?
Can you find a way of working out how many solutions there are?
If you have enjoyed working on this problem, then you may enjoy Euler's Totient Function.
We are very grateful to the Heilbronn Institute for Mathematical Research for their generous support for the development of this resource.
Getting Started
If $4x \equiv 1 \text{ mod } 7$, one possible value of $x$ is $2$ (since $4 \times 2 = 8 \equiv 1 \text{ mod }7$).
Find the value of $4x \text{ mod }7$ when $x = 9, 16, 23, ...$
Can you use this to help you find a general form for $x$?
Student Solutions
Olivia from Roedean in the UK tried different values of $x$ to solve the equations $3x \equiv 1 \text{ mod } 7$ and $3x \equiv b \text{ mod } 7$:
Mahdi from Mahatma Gandhi International School in India used the rules proved earlier in the problem:
For the equation $6x \equiv b \text{ mod } 7$, Olivia wrote:
Mahdi wrote:
Since $7$ is prime, for every value of $a$ and $b$, there is a unique solution for $x$ in the equation $ax\equiv b \text{ mod 7}$
For the equations $4x \equiv b \text{ mod } 10$ and $ax \equiv b \text{ mod } 10$, Olivia wrote:
To find numbers that solve $4x \equiv b \text{ mod } 10$, we make a table again
Mahdi wrote:
The problem that Mahdi mentions is Stars. Olivia also used the interactivity to explain how to choose possible values of $a$:
Considering the proof that, when $A \equiv a \text{ mod }n$ and $B \equiv b \text{ mod }n$ it is always true that $AB \equiv ab \text{ mod }n$, Amy asked whether this proof could be adapted to find which values of $a$ and $b$ give solutions to the equation $ax \equiv b \text{ mod }n$.
Since the proof shows that the first rule is true for all $a$ and $b$, but later we want to find the specific values of $a$ and $b$ which give solutions, one cannot be adapted easily to give the other. However, a similar argument can be used to demonstrate which values of $a$ and $b$ will work for each $n$.
This is linked to Mahdi's first method. Consider applying Mahdi's first method to $4x\equiv b \text{ mod 10}$:
$4x \equiv 2\text{ mod 10} $
$\Rightarrow 4x \equiv 12\text{ mod 10}$
$\Rightarrow x \equiv 3\text{ mod 10}$
However
$4x \equiv 1\text{ mod 10} $
$\Rightarrow 4x \equiv 11\text{ mod 10}\equiv 21,31, 41, 51, ...\text{ mod 10}$
And none of those numbers are divisible by $4$.
Can you generalise this?
Teachers' Resources
Why do this problem?
This problem follows on from Clock Arithmetic. It gives students the opportunity to consider the properties of numbers when we add or multiply numbers using modular arithmetic, and to then move on to equations with modulo arithmetic.
At the end students are challenged to discover that in general $ax \equiv b \text{ mod }n$ has solutions if, and only if, the highest common factor of $a$ and $n$ divides $b$. This means that if $a$ and $n$ have no common factors greater than 1 then $ax \equiv b \text{ mod }n$ has a solution for all values of $b$ (where $0 \le b \le n-1$).
Possible approach
This problem featured in an NRICH Secondary webinar in April 2021.
Start by asking students to think of two numbers, and find what they are modulo $7$. Ask them to add their original numbers and find out what this sum is modulo $7$. What do they notice?
It might be helpful to work through an example:
15 &\equiv 1 \text{ mod }7\\
26 &\equiv 5 \text{ mod }7\\
15+26&=41
\end{align}
Then give the students time to try a few examples of their own and write down what they notice. Encourage them to try some modulos other than $7$.
Bring the students together and display the proof sorter to work on as a class.
Work on multiplication in the same way as addition, but this time students can have a go at writing their own proof before comparing it to the proof on the problem page.
For the final part of this problem, students could start by playing with the Stars interactivity and seeing which combinations of number of dots and step size ensures that every dot is visited. This can be linked to the equation $ax \equiv b \text{ mod }n$ by taking number of dots $=n$ and step size $=a$.
Key questions
Possible support
This problem follow on from Clock Arithmetic. Students might like to work on Stars before trying to link this to modular equations.