Section 9.4 Congruence revisited
One very important relation is congruence modulo
\(n\text{.}\) It is not too hard to show that it is an equivalence relation, and its equivalence classes have some very useful properties. The reader should quickly revisit
Section 5.3,
Definition 5.3.1 and
Theorem 5.3.3.
By Theorem
Theorem 9.2.6, congruence modulo
\(n\) is an equivalence relation and so has equivalence classes. For example, if we fix the modulus as
\(4\text{,}\) then we can write down the four equivalence classes of integers modulo 4:
\begin{align*}
[0]\amp =\set{\dots,-8,-4,0,4,8,\dots} \amp
[1]\amp=\set{\dots,-7,-3,1,5,9,\dots}\\
[2]\amp=\set{\dots,-6,-2,2,6,10,\dots} \amp
[3]\amp=\set{\dots,-5,-1,3,7,11,\dots}
\end{align*}
Notice that we are representing each equivalence class by the smallest non-negative integer in that class.
One reason that this equivalence relation, congruence modulo
\(m\text{,}\) is so important is that its equivalence classes interact very nicely with arithmetic giving rise to
modular arithmetic. We saw this idea back in
Theorem 5.3.3. Let us rewrite that result in terms of equivalence classes.
Theorem 9.4.2. Modular arithmetic redux.
Let \(n \in \mathbb{N}\text{,}\) and let \(a,b,c,d \in \mathbb{Z}\) so that
\begin{equation*}
c \in [a] \qquad \text{and} \qquad d \in [b],
\end{equation*}
where \([x]\) denotes the equivalence class of \(x\) under congruence modulo \(n\text{.}\) Then
\begin{align*}
c+d \amp \in [a+b], \amp c-d \amp \in [a-b] \amp \text{and}\\
c\cdot d \amp \in [a\cdot b]
\end{align*}
Proof.
The proof of this statement is essentially identical to the proof of
Theorem 5.3.3.
As an illustration of this result, consider the numbers 5 and 7. When we multiply them together we get 35. But now, think about these numbers modulo 4, and the equivalence classes they lie in:
\begin{equation*}
5 \in [1] \qquad 7 \in [3] \qquad 35 \in [3]
\end{equation*}
The above theorem tells us that since \(5 \equiv 1 \mod 4\) and \(7 \equiv 3 \mod 4\text{,}\) their product
\begin{equation*}
\underbrace{35}_{5\times 7} \equiv \underbrace{3}_{3 \times 1} \mod 4
\end{equation*}
Notice that this will hold no matter which elements of \([1]\) and \([3]\) we multiply together, we will always get an element of \([3]\text{.}\) This suggests (with a little bending of notation and avoiding any confusion with cartesian products):
\begin{equation*}
[1] \cdot [3] = [3]
\end{equation*}
and similarly
\begin{equation*}
[1] + [3] = [4] = [0].
\end{equation*}
This can be made to work more generally, but first we should define things carefully and then prove things carefully.
Definition 9.4.3.
Let \(n \in \mathbb{N}\text{,}\) and let \(a,b \in \mathbb{Z}\text{.}\) Then we define the following arithmetic operations on the equivalence classes modulo \(n\text{:}\)
\begin{align*}
[a]+[b] \amp= [a+b]\\
[a]-[b] \amp= [a-b]\\
[a] \cdot [b] \amp= [a \cdot b]
\end{align*}
where we have used “\(\cdot\)” to denote multiplication to avoid confusion with the cartesian product of sets.
There is a small problem with this definition — we need to make sure that it makes sense and is well defined and that our choice of representative elements \(a,b\) does not change the results \([a+b],[a-b], [a\cdot b]\text{.}\) For example, in our modulo 4 example, we know that
\begin{equation*}
[1]=[5]=[-3] \qquad \text{ and } [3]=[7]=[-1]
\end{equation*}
so we need to be sure that
\begin{equation*}
\underbrace{[1]+[3]}_{[4]} = \underbrace{[5]+[7]}_{[12]} = \underbrace{[-3]+[-1]}_{[-4]} = [0]
\end{equation*}
Corollary 9.4.4. Modular arithmetic.
Let \(n \in \mathbb{N}\text{,}\) and let \(a,b \in \mathbb{Z}\text{.}\) Then the sets
\begin{equation*}
[a + b] \qquad [a - b] \qquad [a\cdot b]
\end{equation*}
are well defined and do not depend on the choice of representative elements.
Proof.
Let \(a,b,n\) be as in the statement of the result, and let \(c \in [a], d\in [b]\text{.}\)
By definition
\([c]+[d] = [c+d]\text{.}\) It suffices to show that
\([c+d]=[a+b]\text{.}\) By Theorem
Theorem 5.3.3, we know that
\(c+d \in [a+b]\) and so by Corollary
Corollary 9.3.7 \([c+d]=[a+b]\) as required.
The same argument shows that \([c]-[d] = [c-d]=[a-b]\text{,}\) and that \([c] \cdot [d] = [c\times d] = [a \cdot b]\text{.}\)
This result turns out to be very useful. It tells us that
\begin{equation*}
[7] \cdot [9] = [3] \cdot [1] = [3 \cdot 1] = [3].
\end{equation*}
Of course, that one is easy enough to check in our head:
\begin{equation*}
7 \times 9 = 63 \qquad \text{and} \qquad 63 \equiv 3 \mod 4.
\end{equation*}
But (minutely) less easy:
\begin{equation*}
[19] \cdot [11] = [3] \cdot [3] = [9] = [1]
\end{equation*}
(which is true since \(19 \times 11 = 209 = 208 + 1 = 52\times 4 + 1\)).
Now, just before we switch gears to modulo 10, we should make some notation to emphasise the modulus so that we don’t mix equivalence classes from different equivalence relations
111 . We can rewrite the above equivalence classes with the modulus as a subscript:
\begin{equation*}
[7]_4 \cdot [9]_4 = [3]_4
\end{equation*}
This makes it much easier to talk about different modulii without confusing the reader. Of course, if the modulus is clear by context, then we don’t need the subscript.
Another, more complicated one, For example, let \(a=17321289, b=23492871\) and we compute their product as
\begin{equation*}
17321289 \times 23492871 = 406926808030718.
\end{equation*}
If you look at this for amoment, you realise that the product is wrong — the last number definitely should not be an “8”. We can show this by computing the product modulo 10:
\begin{equation*}
[17321289]_{10} \cdot [23492871]_{10} = [9]_{10} \cdot [1]_{10} = [9]_{10}.
\end{equation*}
This is a very simple example of using modular arithmetic as a way of error-checking. Some simple techniques based on modular arithmetic are often used in credit-card numbers and similar.
Example 9.4.5. Checking long numbers — Luhn algorithm.
The author is going to assume that everyone has had to either write down a telephone number or a credit card number and messed it up. Very common mistakes are
Single digit error: \(1 \mapsto 2\)
Transposition: \(12 \mapsto 21\)
Phonetic errors: \(60 \mapsto 16\)
Everyone has dialed a wrong number
112 , but thankfully, credit card numbers have some built-in checks that prevent simple errors like the above. In particular, a credit card has a “check digit”.
Since people rarely mess transcribing up the first or last digit of a long number, one can exploit the last digit to check up on the others. So say you have a long number (like a credit card or phone number), that you want to protect against simple errors, then you should append a single special digit to the end of that number. For example, say we have the first 8 digits of a number “31415926” and we want to make sure that it can be checked when copied down by someone else. A really simple check is to sum up the digits modulo ten:
\begin{equation*}
3+1+4+1+5+9+2+6 = 31 \equiv 1 \mod 10
\end{equation*}
So we can append “1” to the end of the number to get “314159261”.
Now when we read it out to a friend over the phone, they copy down “313159261”. They can then compute the check number:
\begin{equation*}
3+1+3+1+5+9+2+6 = 30 \equiv 0 \mod 10
\end{equation*}
Since \(0 \neq 1\) they know there is an error. This will proof against a single-digit substitution error, but it will not be safe against a transposition. If they wrote down “314519261” then the check gives
\begin{equation*}
3+1+4+5+1+9+2+6 = 31 \equiv 1 \mod 10
\end{equation*}
So the error goes undetected.
However there is a better way. The Luhn algorithm
113 is used in many applications including in credit cards.
Start with our number \(3,1,4,1,5,9,2,6\text{.}\)
Double every second digit (starting from the rightmost): \(3,2,4,2,5,18,2,12\text{.}\) Notice that our list of digits becomes longer
Now sum
all:
\begin{equation*}
3+2+4+2+5+(1+8)+2+(1+2) = 30
\end{equation*}
Multiply the result by 9 and compute the result modulo ten:
\begin{equation*}
30 \times 9 = 270 \equiv 0 \mod 10
\end{equation*}
Append the result as the check digit: “314159260”
Let us try this against the two transcription errors above:
“31
3159260” becomes “3,2,3,2,5,18,2,12” which gives
\begin{equation*}
3+2+3+3+2+5+(1+8)+2+(1+2) = 32.
\end{equation*}
Multiply by 9 to get
\(32\times 9 = 288\) giving check-digit “8”. Error detected!
“314
519261” becomes “3,2,4,10,1,18,2,12” which gives
\begin{equation*}
3+2+4+(1+0)+1+(1+8)+2+(1+2) = 25.
\end{equation*}
Multiply by 9 to get
\(225\) giving check-digit “5”. Error detected!
This is not too hard to do by hand, but it is very easy for a computer.
This is not perfect, some errors will go undetected. The interested reader should search-engine their way to more information.
Example 9.4.6. Chinese remainder theorem.
You can push this idea further, and instead of doing arithmetic with very large numbers, you can do the same arithmetic modulo several different primes and then reconstruct the big-number result using the results modulo each prime. The piece of mathematics that tells you how to reconstruct the result is called the Chinese Remainder Theorem. It was first stated in the 3rd century AD by the Chinese mathematician Sunzi, but the first real method for this reconstruction is due to Aryabhata (an Indian mathematician of the 6th century AD). It seems to have been rediscovered a few times and seems to have entered European mathematics via Fibonacci in the 12th century. It’s not quite clear when it got its name, but perhaps sometime between 1850 and 1930?
We won’t do the Chinese remainder theorem in this course (its a good one to do in a number theory course), but we’ll do a few more applications of congruences.
Example 9.4.7. No integer solutions.
Show that the equation
\begin{align*}
x^2 - 4y^2 &= 3
\end{align*}
has no integer solutions.
Scratchwork.
A sneaky way to look at this is to realise that if there is an integer solution, then if you look at that solution modulo, say \(7\text{,}\) then it will still be a solution. ie
\begin{align*}
(x^2 - 4y^2) \mod 7 &= 3 \mod 7.
\end{align*}
Hence if we can prove that the equation has no solution modulo (again say) 7, then it cannot have a solution over the integers (by taking the contrapositive). Notice that the converse is very false — just because we can find a solution modulo 7, does not mean there is an integer solution.
Now, because one of the coefficients in the equation is a 4, it simplifies considerably modulo 4. In particular
\begin{gather*}
4y^2 \mod 4 = 0
\end{gather*}
no matter what \(y\) we put in. So modulo 4 the equation simplifies to
\begin{align*}
(x^2 - 4y^2)\mod 4 &= x^2 \mod 4 = 3 \mod 4
\end{align*}
So now we look at squares modulo 4.
\begin{align*}
0^2 \mod 4 &= 0 &
1^2 \mod 4 &= 1 &
2^2 \mod 4 &= 0\\
3^2 \mod 4 &= 1 &
4^2 \mod 4 &= 0 &
5^2 \mod 4 &= 1
\end{align*}
So — it looks like squares modulo 4 are either 0 or 1, depending on their parity. If this is true then we are done — there is no solution modulo 4, so there cannot be an integer solution.
Proof.
The equation either has a solution \(x,y \in \mathbb{Z}\) or it does not. If the equation does have a solution, then \(x\) is either even or odd.
If
\(x\) is even then
\(x=2k\) for some
\(k \in \mathbb{Z}\text{,}\) and so
\begin{align*}
x^2 - 4y^2 &= 4(k^2-y^2)
\end{align*}
and so
\(x^2-4y^2 \equiv 0 \mod 4\text{.}\)
On the other hand, if
\(x\) is odd, then
\(x=2k+1\) for some
\(k \in \mathbb{Z}\) and so
\begin{align*}
x^2 - 4y^2 &= 4k^2+4k+1-4y^2 = 4(k^2+4k-y^2) + 1
\end{align*}
and so
\(x^2 - 4y^2 \equiv 1 \mod 4\text{.}\)
In either case \(x^2-4y^2\) is not congruent to 3 modulo 4. Hence there cannot be a solution.
Now, noticeably absent from Theorem
Theorem 5.3.3 above is any discussion of division. Consider the equation
\(x = \frac{13}{2}\text{;}\) here we are really solving the equation
\(2x=13\text{.}\) Consider this equation modulo
\(4\) — find any
\(x\) so that
\begin{equation*}
[2]_4 \cdot [x]_4 =[1]_4
\end{equation*}
(since \([13]_4 = [1]_4\)). Similarly modulo 5 we get:
\begin{equation*}
[2]_5 \cdot [x]_5 = [1]_5.
\end{equation*}
We can try to solve these equations by brute-force by just writing out the multiplication tables modulo 4 and 5:
| \(\cdot\) |
[0] |
[1] |
[2] |
[3] |
| [0] |
[0] |
[0] |
[0] |
[0] |
| [1] |
[0] |
[1] |
[2] |
[3] |
| [2] |
[0] |
[2] |
[0] |
[2] |
| [3] |
[0] |
[3] |
[2] |
[1] |
| \(\cdot\) |
[0] |
[1] |
[2] |
[3] |
[4] |
| [0] |
[0] |
[0] |
[0] |
[0] |
[0] |
| [1] |
[0] |
[1] |
[2] |
[3] |
[4] |
| [2] |
[0] |
[2] |
[4] |
[1] |
[3] |
| [3] |
[0] |
[3] |
[1] |
[4] |
[2] |
| [4] |
[0] |
[4] |
[3] |
[2] |
[1] |
Now - we see that modulo 5 we have a solution since:
\begin{equation*}
[2]_5 \cdot [3]_5 = [1]_5
\end{equation*}
but modulo 4 there is no solution since
\begin{equation*}
[2]_4 \cdot [x]_4 = [0]_4 \text{ or } [2]_4.
\end{equation*}
The existence of solutions to the equation
\begin{equation*}
[a]_n \cdot [x]_n = [1]_n
\end{equation*}
depends on the divisors of \(a\) and \(n\text{.}\)
Lemma 9.4.8.
Let \(a \in \mathbb{Z}, n \in \mathbb{N}\text{.}\) If \(d>1\) divides both \(a,n\) then the equation
\begin{equation*}
[a]_n \cdot [x]_n = [1]_n
\end{equation*}
does not have a solution.
Proof.
Say that the equation
\begin{equation*}
[a]_n \cdot [x]_n = [1]_n
\end{equation*}
has a solution \(x=b\text{.}\) Then for some \(k \in \mathbb{Z}\)
\begin{equation*}
ab + kn = 1.
\end{equation*}
Now if, \(d>1\) divides both \(a,n\) the left-hand side is divisible by \(d\text{.}\) However this does not make sense because the right-hand side is only divisible by \(\pm 1\text{.}\) Hence no such solution can exist.
Example 9.4.10. Pseudo random numbers.
Consider the following sequence of numbers
\begin{equation*}
1,10,7,8,4,9,0,3,2,\dots
\end{equation*}
The numbers bounce around and look fairly ``random’’. However, they are not actually random at all; they satisfy the simple relation
\begin{equation*}
x_{k+1} \equiv (7 x_k + 3) \mod{11},
\end{equation*}
or, using the % operator (ie integer remainder operator)
\begin{equation*}
x_{k+1} = (7x_k+3)\% 11.
\end{equation*}
This is an example of a linear congruent generator; the next term in the sequence is determined by a simple linear equation involving a congruence:
\begin{equation*}
x_{k+1} = a x_k + c \mod n
\end{equation*}
If one chooses \(a\) and \(c\) carefully, then the resulting sequence of numbers will look quite random. However, since the numbers are not actually random, they are usually called pseudo random numbers.
Many computer algorithms for generating pseudo random numbers are based on this idea. Of course, one does need to be quite careful and make sure that your pseudo-random numbers are actually fairly random. For example, if we choose \(a=7, c=5, n=11\) in the above, then we get the sequence
\begin{equation*}
1,1,1,1,\dots
\end{equation*}
since \(7\cdot 1 + 5 = 12 \equiv 1 \mod{11}\text{.}\) Not very random at all.
There is a lot of interesting mathematics to be found in generating pseudo-random numbers and testing their randomness; we recommend that the interested reader take a trip to their favourite search engine.
This author has gotten into difficulties in a piece of research when their coauthor (for very valid reasons) instead chose to represent equivalence classes by the integer closest to zero.
In some situations it is very helpful to mix results from different moduli, but one does it very deliberately, and not by accident. For a good example of carefully mixing moduli, see
Example 9.4.6 below.
I think? Well, the author definitely has
Named for the computer scientist Hans Peter Luhn (1896–1964).
