-
Introduction
In this unit we introduce some elementary concepts from number theory that are used in many modern ciphers and related security systems. We start with some basic definitions before discussing the division algorithm which lies at the heart of the important Euclidean algorithm. The discussion then moves on to look at prime numbers and describes how prime factorisation can be applied to express any integer, greater than one, as a product of primes. The concept of a greatest common divisor (GCD) of two positive integers is described and we discuss how prime factorisation can be used to calculate this quantity when the numbers are relatively small. We then introduce the Euclidean algorithm which provides an efficient method for calculating the GCD of two integers regardless of their size.
The Euclidean algorithm leads on to the idea of congruence of two integers modulo $m$, where $m$ is some given integer. We present some properties of congruence and describe how congruence modulo $m$ is an equivalence relation. A discussion on modular arithmetic follows and we introduce multiplication tables and describe how we can use the tables to identify multiplicative inverses modulo $m$ when they exist. As the value of the modulus $m$ increases tables are no longer practical for identifying inverses and so we introduce the Extended Euclidean Algorithm. The algorithm provides a method for writing the GCD of two integers as a linear combination of these integers and gives a more efficient method for determining the inverse of an integer modulo $m$, when it exists. Linear congruence equations are briefly investigated later in the unit and we demonstrate how the Extended Euclidean Algorithm is used to, where possible, solve these equations. We also present some further properties from modular arithmetic, that are applied in cryptography, including repeated squaring - a technique that enables us to find remainders when calculations involve very large numbers.
The final section of the unit brings together the ideas from number theory we have described to look at their application in the field of cryptography. We discuss different types of ciphers including character ciphers (Caesar cipher) and block ciphers (Vigenere and Hill ciphers). The unit closes with a brief discussion on exponential ciphers and RSA ciphers (public key cryptography) which provide significantly increased security when compared with additive and multiplicative ciphers.
-
2. Numbers and their properties
This section provides some basic definitions and properties of the integers, i.e. the set
$\mathbb{Z} = \{ 0,\; \pm \,1, \; \pm \,2, \dots. \}$,
and the related set of natural numbers (positive integers)
$ \mathbb{N} = \{1,\, 2,\, 3, \dots \}$.
2.1 Multiples and factors
Let $m$ and $n$ be integers. If $n = km$ for some integer $k$ then $n$ is called a multiple of $m$. Another way to express the relationship between $m$ and $n$ is to say that $m$ is a factor of $n$. A factor of a given number is a number that divides exactly into that number. Alternatively we say that $n$ is divisible by $m$, or $m$ divides $n$ and write $m \mid n$. If $m$ does not divide $n$ we write $m \nmid n$.
Example 1
(i). $60$ is a multiple of $3$ since $60 = 3 \times 20$
(i). $36$ is a multiple of $9$ since $36 = 9 \times 4$
(iii). $22$ is not a multiple of $3$ as there is no integer which multiplied by $3$ gives $22$.
End of Example 1Example 2
(i). The numbers $1, 2, 3, 4, 6$ and $12$ are all factors of $12$ as they each divide exactly into $12$.
(i). The numbers $1, 2, 4, 5, 10$ and $20$ are all factors of $20$ as they each divide exactly into $20$.
(iii). The number $3$ is not a factor of $20$ as $3$ does not divide exactly into $20$.
End of Example 22.2. The division algorithm
Let $a$ and $b$ be integers with $b > 0$. Then there exist unique integers $q$ and $r$ such that
$a = bq + r$ with $0 \le r < b$.
The numbers $q$ and $r$ are called the quotient and remainder respectively when $a$ is divided by $b$.
Watch the video at the following link:
Example 3
(i). Let $a = 34$ and $b = 6$. Dividing $a$ by $b$ gives that $q = 5$ and $r = 4$. We can easily check this is correct as, $34 = 6 \times 5 + 4$ .
(ii). Let $a = -34$ and $b = 6$. When dividing $a$ by $b$ it might be tempting to write that $q = -5$ and $r = -4$.
However, this would be incorrect as $r$ must be non-negative. The correct answer is, $q = -6$ and $r = 2$.
We can easily check this is correct as $-34 = 6 \times ( -6 ) + 2$ .
End of Example 32.3. Prime and Composite Numbers
🔗 Recognizing prime and composite numbers
A prime number is a positive integer, greater than $1$, that is divisible only by 1 and itself.
A composite number is a positive integer greater than $1$ which is not prime, i.e. it has at least one factor other than $1$ and itself.
Example 4
(i). $7$ is a prime number, since it is only divisible by $1$ and $7$.
(ii). $13$ is a prime number, since it is only divisible by $1$ and $13$.
(iii). $4$ is a composite (not prime) number, since it is divisible by $1, 2$ and $4$.
(iii). $12$ is a composite (not prime) number, since it is divisible by $1, 2, 3, 4$ and $6$.
The prime numbers less than $25$ are $2, 3, 5, 7, 11, 13, 17, 19, 23$.
The composite numbers less than $25$ are: $4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24$.
Notes
(a). The numbers $0$ and $1$ are neither prime nor composite.
(b). The only even prime number is $2$.
(c). In order to determine whether a number, $n$, is prime it is sufficient to show that it is not divisible by any of the integers from $2$ up to the square root of $n$.
(d). There are infinitely many primes!
End of Example 42.3.1. Prime Factors
The prime factors of a number are the prime numbers that divide that number exactly with no remainder.
Example 5
Find all prime factors of $40$.
Solution
The factors of $40$ are $1, 2, 4, 5, 8, 10, 20, 40$. Only $2$ and $5$ are prime numbers and so the prime factors of $40$ are $2$ and $5$.
End of Example 52.3.2. Prime Factorisation
The fundamental theorem of arithmetic states that every positive integer greater than $1$ is either prime or can be written as a product of prime numbers in a unique way (except for the order of the factors). The process is known as prime factorisation.
Example 6
(i). Find the prime factorisation of $264$.
(ii). Find the prime factorisation of $675$.
Solution
(i). First note that $264$ is an even number and can therefore be divided by $2$, i.e.
$ 264 = 2 \times 132$
$= 2 \times 2 \times 66$
$= 2 \times 2 \times 2 \times 33$
$= 2 \times 2 \times 2 \times 3 \times 11 $
These are all prime numbers and we have found the prime factorisation of $264$.
(ii). First note that $675$ is divisible by $3$ (a number is divisible by $3$ if the sum of its digits is divisible by $3$)
$675 = 3 \times 225$
$= 3 \times 5 \times 45$
$= 3 \times 5 \times 3 \times 15$
$= 3 \times 5 \times 3 \times 3 \times 5$
$= 3 \times 3 \times 3 \times 5 \times 5 $
These are all prime numbers and we have found the prime factorisation of $675$.
For more practice a prime factorisation calculator is available here: 🔗 Prime Factors Calculator
End of Example 62.3.3. Least common multiple (LCM)
The least common multiple (LCM) of two non-zero integers $a$ and $b$, is the smallest positive integer that is divisible by both $a$ and $b$.
Example 7
Find the LCM of 9 and 12.
Solution
There are several different approaches to calculating the LCM.
(i). For “small” numbers like $9$ and $12$ the easiest method is to proceed as follows:
Write down several multiples of the smaller number:
Multiples of $9$ are: $9, 18, 27, 36, 45, 54, \dots $
Write down the multiples of the larger number until one of them is also a multiple of the smaller number:
Multiples of $12$ are: $12, 24, 36, \dots $
Now, $36$ is also a multiple of $9$ and so lcm $( 9, 12 ) = 36$ .
(ii). An alternative approach uses prime factorisation:
Write the prime factorisation of each number in exponential form:
$9 = 3 \times 3 = 3^2$
$12 = 2 \times 2 \times 3 = 2^2 \times 3. $
Multiply all the factors with the highest powers to obtain the LCM.
lcm $(9, 12) = 3^2 \times 2^2 = 36$.
End of Example 72.3.4. Greatest common divisor (GCD)
The greatest common divisor (GCD) of two integers $a$ and $b$, which are not both zero, is the largest integer that divides exactly into both numbers. The GCD is also known as the highest common factor (HCF).
Example 8
Find the GCD of 24 and 32.
Solution
There are several different approaches to calculating the GCD.
(i). For “small” numbers like $24$ and $32$ the easiest method is to proceed as follows:
Write down the factors of the smaller number, starting from the largest factor.
The factors of $24$ are:$24, 12, 8, 6, 4, 3, 2, 1$.
Write down the factors of the larger number, starting from the largest factor.
The factors of $32$ are:$32, 16, 8, 4, 2, 1$.
Reading from left to right, the first factor of the smaller number that is also a factor of the larger number is $8$ and so $8$ is defined to be the GCD of $24$ and $32$.
Hence, gcd$(24, 32) = 8$.
(ii). An alternative approach uses prime factorisation.
Determine the prime factorisation of each number:
$24 = 2 \times 2 \times 2 \times 3$
$32 = 2 \times 2 \times 2 \times 2 \times 2$
List the factors common to both and multiply them together. The number $2$ appears three times in each prime factorisation and so
gcd $( 24, 32 ) = 2 \times 2 \times 2 = 8$.
The methods in the previous example work well when the integers are relatively small but are inefficient as the numbers become larger. A more systematic approach for calculating the GCD of two positive integers is provided by the Euclidean algorithm which is named after the ancient Greek mathematician Euclid.
Before discussing the Eucildean algorithm in detail we present an interesting relaionship between the GCD and the LCM.
Theorem
Let $a$ and $b$ be positive integers (natural numbers) then
gcd$( a, b ) \times \;$lcm$( a, b ) = a \times b$.
In words, the product of the LCM and GCD of two natural numbers is equal to the product of the numbers.
Example
(i). gcd$( 24, 32 ) = 8$ and lcm$( 24, 32 ) = 96$.
gcd$( 24, 32) \times$ lcm$( 24, 32 ) = 8 \times 96 = 768$
Also, $24 \times 32 = 768$.
(ii). lcm$(16, 28) = {\Large\frac{16 \times 28}{\text{gcd}(16, 28)}} = {\Large\frac{448}{4}} = 112$.
End of Example 82.4. The Euclidean algorithm
In order to find the GCD of two positive integers $a$ and $b$ the Euclidean algorithm generates a sequence of equations, through successive application of the division algorithm. The process continues until a zero remainder is obtained. The last non-zero remainder in the sequence is defined to be the GCD of $a$ and $b$.
More formally, define $a$ and $b$ to be positive integers with $b < a$. To find gcd $(a, b)$ apply the division algorithm and write,
$a = q_1b + r_1$ $0 \le r_1 < b$ If $r_1 \neq 0;$ $b = q_2r_1 + r_2$, $0 \le r_2 < r_1$. If $r_2 \neq 0$; $r_1 = q_3r_2 + r_3$, $0 \le r_3 < r_2$. If $r_3 \neq 0$; $r_2 = q_4r_3 + r_4$, $0 \le r_4 < r_3$. If $r_4 \neq 0$; $r_3 = q_5r_4 + r_5$, $0 \le r_5 < r_4$. Continue in this way until a zero remainder is obtained, i.e. $r_{k+1} = 0$ .
Then gcd $(a, b)$ is given by the last (non-zero) remainder in the sequence, i.e. $r_k$.
The Euclidean algorithm is an extremely fast and efficient method for calculating the GCD of large numbers.
Example 9
Find the greatest common divisor of $1200$ and $836$.
Solution
Apply the Euclidean algorithm, as described above, to find gcd $( 1200, 836 )$.
$1200 = 1 \times 836 + 364$
$836 = 2 \times 364 + 108$
$364 = 3 \times 108 + 40$
$108 = 2 \times 40 + 28$
$40 = 1 \times 28 + 12$
$28 = 2 \times 12 + 4$
$12 = 3 \times 4 + 0$
The last non-zero remainder in the sequence is $4$ and so gcd $( 1200, 836 ) = 4$.
End of Example 9Example 10
Find the greatest common divisor of $25936$ and $5872$.
Solution
Apply the Euclidean algorithm to find gcd $( 25936, 5872 )$.
$25936 = 4 \times 5872 + 2448$
$5872 = 2 \times 2448 + 976$
$2448 = 2 \times 976 + 496$
$976 = 1 \times 496 + 480$
$496 = 1 \times 480 + 16$
$480 = 30 \times 16 + 0 $
The last non-zero remainder in the sequence is $16$ and so gcd $( 25936, 5872 ) = 16$ .
End of Example 10Example 11
Apply the Euclidean algorithm to find gcd $( 256, 175 )$.
Solution
The algorithm gives:
$256 = 1 \times 175 + 81$
$175 = 2 \times 81 + 13$
$81 = 6 \times 13 + 3$
$13 = 4 \times 3 + 1$
$3 = 3 \times 1 + 0$
The last non-zero remainder in the sequence is $1$ and so gcd $( 256, 175 ) = 1$.
End of Example 112.5 Relatively Prime Integers
Two integers $a$ and $b$ are said to be relatively prime (or coprime or mutually prime) if they have no common factors other than $1$, i.e. gcd $( a, b ) = 1$.
Example 12
(i). From the previous example, gcd $(256, 175) = 1$ and so $175$ and $256$ are relatively prime.
(ii). Two prime numbers, $a$ and $b$, are always relatively prime as gcd $( a, b ) = 1$.
End of Example 12Example 13
(i). An alternative approach for identifying whether two integers are relatively prime involves determining the prime factorisation of each number and then checking whether or not they have any common factors. If there are no common factors the numbers are relatively prime. From the previous example we have that
$256 = 2^8$ and $175 = 5 \times 5 \times 7$
Clearly these prime factorisations have no factors in common and so $175$ and $256$ are relatively prime.
This method works reasonably well when numbers are relatively small but becomes inefficient as numbers grow larger. The Euclidean algorithm is the preferred option in such cases.
End of Example 13 -
3. Congruence modulo $m$
- The congruence of integers was first studied in detail by the German mathematician Gauss in the early 19th century. The significance of the term “modulo $m$” will be explained shortly but in the meantime here are some examples of where congruences occur in practice.
- Generating sequences of pseudorandom numbers using the linear congruential method. These sequences are based on the recurrence relation formula, $x_{n+1} = (ax_n + b)(mod\; m)$ for given values of $a$, $b$ and $m$ and some starting value $x_0 = c$. The generator produces sequences of integers between $0$ and $m - 1$.
- The International Standard Book number (ISBN). A 10-digit ISBN, $b_1 b_2 \dots b_{10}$ must have the property that
$ B = 10b_1 + 9b_2 + \dots + 2b_9 + b_{10}$
is exactly divisible by $11$, i.e. we write $B \equiv 0( mod 11 )$. In 2007 the ISBN’s assigned to books changed from $10$ digits to $13$. - Assigning memory locations in computing through the use of hashing functions.
Definition
Let $a,\; b$ and $m$ be integers with $m > 0$. We say that $a$ is congruent to $b$ modulo $m$, and write $a \equiv b (mod\; m)$, if and only if $m \mid (a - b)$. The integer $m$ is called the modulus of the congruence and $b$ is the remainder or residue.
If $a - b$ is not divisible by $m$ we write $a \not\equiv b ( mod \;m )$ and say that $a$ is not congruent to $b$ modulo $m$.
- Note that the following statements are equivalent:
- $a \equiv b (mod\; m)$
- $m \mid (a - b)$
- $\frac{a - b}{m} = k, \;\;\;\;\;\;\;\; k \in \mathbb{Z}$
- $a = b + km, \;\;\; k \in \mathbb{Z}$
- $a - b = km, \;\;\; k \in \mathbb{Z}$
- $a$ and $b$ have the same non-negative remainder on division by $m$.
Example 14
(i). $25 \equiv 1 (mod\, 6)$ since $6 \mid ( 25 - 1 )$ i.e. $6 \mid 24$.
(ii). $31 \equiv 1 (mod \,6)$ since $6 \mid ( 31 - 1 )$ i.e. $6 \mid 30$.
(iii). $4 \equiv 24 (mod\, 10)$ since $10 \mid ( 4 - 24 )$ i.e. $10 \mid -20$ .
(iv). $9 \equiv 9 (mod\, 7)$ since $7 \mid ( 9 - 9 )$ i.e. $7 \mid 0$ .
(v). $-12 \equiv 9 (mod\, 3)$ since $3 \mid ( -12 - 9 )$, i.e. $3 \mid -21$ .
(vi). $26 \not\equiv 5 (mod\, 4)$ since $4 \nmid ( 26 - 5 )$ i.e. $4 \nmid 21$.
📹 How to Convert a Negative Integer in Modular Arithmetic - Cryptography - Lesson 4
End of Example 14Example 15
(i). $\{ \dots, -9, -2, 5, 12, 19, \dots \}$ are all congruent modulo $7$ since their remainders on division by $7$ all equal $5$.
(ii). $\{ \dots, -22, -10, 2, 14, 26, \dots \}$ are all congruent modulo $12$ since their remainders on division by $12$ all equal $2$.
End of Example 15Example 16
Determine all the integers between $1$ and $60$ which are congruent to $7$ modulo $12$. In other words, find all integers $x$ where $1 \le x \le 60$ such that $x \equiv 7 (mod\, 12)$ .
Solution
The equation $x \equiv 7 (mod\, 12)$ is an example of a linear congruence equation which differs from the usual linear algebraic equation in that linear congruences can have more than one solution.
$7 + 0 = 7$
$7 + 12 = 19$
$19 + 12 = 31$
$31 + 12 = 43$
$43 + 12 = 55$
Stop here as adding $12$ to $55$ takes us outside the range.
Hence, the solutions are: $x = 7, 19, 31, 43, 55$.
End of Example 16Example 17
Suppose that $x = 23( mod\, 4 )$. Which of the following integers are valid solutions for $x$?
(i). $3$, (ii). $-2$ , (iii). $-5$ , (iv). $23$
Solution
Considering each option in turn.
(i). If $x = 3$ we require that $4 \mid ( 3 - 23 )$ or $4 \mid ( - 20 )$ which is true and so $x = 3$ is a valid solution.
(ii). If $x = -2$ we require that $4 \mid ( -2 - 23 )$ or $4 \mid ( - 25 )$ which is false and so $x = -2$ is not a valid solution.
(iii). If $x = -5$ we require that $4 \mid ( -5 - 23 )$ or $4 \mid ( - 28 )$ which is true and so $x = -5$ is a valid solution.
(iv). If $x = 23$ we require that $4 \mid ( 23 - 23 )$ or $4 \mid 0$ which is true and so $x = 23$ is a valid solution.
End of Example 173.1. Properties of Congruences
Let $a,\, b$ and $m$ be integers with $m > 0$.
(i). $a \equiv a (mod \,m)$.
(ii). If $a \equiv b (mod \,m)$, then $b \equiv a (mod\, m)$ .
(iii). If $a \equiv b (mod\, m)$ and $b \equiv c (mod\, m)$, then $a \equiv c (mod\, m)$.
(iv). If $a \equiv b (mod\, m)$ and $c \equiv d (mod\, m)$, then $a + c \equiv ( b + d )(mod\, m)$ .
(v). If $a \equiv b (mod\, m)$ and $c \equiv d (mod\, m)$, then $ac \equiv bd (mod \,m)$ .
(vi). If $a \equiv b (mod\, m)$ , then $a^k ≡ b^k (mod\, m)$.
The first three properties are respectively; the reflexive, symmetric and transitive properties we encountered in an earlier unit when looking at relations on sets. Congruence modulo $m$ satisfies all three properties and is therefore an equivalence relation: it partitions the integers into $m$ equivalence classes; $0, 1, 2, \dots, m - 1$. Note that in the current context equivalence classes are often referred to as congruence classes.
You should read the sections on equivalence relations and equivalence classes in the unit, “Relations on Sets” from last trimester.
Example 18
Find the equivalence (congruence) classes for congruence modulo 3.
Solution
There are three equivalence classes for congruence modulo 3.
$[ 0 ] = \{ m \in \mathbb{Z} : m \equiv 0 (mod\, 3) \} = \{ \dots, -9, -6, -3, 0, 3, 6, 9, \dots \}$
$[ 1 ] = \{ m \in \mathbb{Z} : m \equiv 1 (mod\, 3) \} = \{ \dots, -8, -5, -2, 1, 4, 7, 10, \dots \}$
$[ 2 ] = \{ m \in \mathbb{Z} : m \equiv 2 (mod\, 3) \} = \{ \dots, -7, -4, -1, 2, 5, 8, 11, \dots \} $
We note that these three classes will account for all the integers as each integer belongs to exactly one of the classes. Furthermore,
$\dots [ -3 ] = [ 0 ] = [ 3 ] = [ 6 ] \dots$
$\dots [ -2 ] = [ 1 ] = [ 4 ] = [ 7 ] \dots$
$\dots [ -1 ] = [ 2 ] = [ 5 ] = [ 8 ] \dots$
End of Example 18Properties (iv) and (v) above state that congruences can be added and multiplied provided the modulus is the same throughout a given expression. We illustrate with an example.
Example 19
Let $a$ and $b$ be integers such that $a \equiv 3 (mod\, 11)$ and $b \equiv 9 (mod\, 11)$.
(i). Determine the integer $u$ such that $u \equiv ( a + b )(mod\, 11)$, where $0 \le u \le 10$ .
(ii). Determine the integer $v$ such that $v \equiv ab(mod\, 11)$ , where $0 \le v \le 10$.
(iii). Determine the integer $w$ such that $w \equiv ( a - b )(mod\, 11)$ , where $0 \le w \le 10$.
Solution
(i). $u \equiv ( a + b )(mod\, 11)$
$\equiv [( 3\, mod\, 11 ) + ( 9 \,mod\, 11 )]( mod\, 11 )$
$\equiv [ 3 + 9 ](mod\, 11)$
$\equiv 12 ( mod \,11)$
$\equiv 1 ( mod \,11)$.
(ii). $v \equiv ab(mod\, 11)$
$\equiv [ ( 3\, mod\,11 ) (9\, mod\, 11 ) ] ( mod\, 11 )$
$\equiv [ 3 \times 9 ](mod\, 11)$
$\equiv 27 ( mod\, 11 )$
$\equiv 5 ( mod\, 11 )$.
(iii). $w \equiv ( a - b )(mod\, 11)$
$\equiv [ ( 3\, mod\, 11 ) - (9\, mod\, 11 ) ] ( mod\, 11 )$
$\equiv [ 3 - 9 ]( mod\, 11 )$
$\equiv -6( mod\, 11 )$
$\equiv 5 ( mod\, 11 )$.
End of Example 19Another form of notation we regularly encounter is, $a( mod\, m ) = r$ which means that $r$ is the remainder when $a$ is divided by $m$. This observation leads us onto our next topic of discussion, that of modular arithmetic. First of all though, by means of an example, we make an important observation regarding the correct use of the congruence, “$\equiv$” and equality “$=$” symbols.
Example 20
The congruence relation $21 \equiv 9( mod \,4 )$ by definition means that $4 \mid ( 21 - 9 )$. It would however be wrong to replace “$\equiv$” with “$=$” and write $21 = 9( mod \,4 )$ . The error here lies in the fact that $9( mod\, 4 ) = 1$ and so the equation $21 = 9( mod\, 4 )$ would say that $21 = 1$ which is clearly incorrect.
End of Example 20Attempt the exercises on congruence modulo $m$ at the link 🔗 Congruence relation
-
4. Modular Arithmetic
Modular arithmetic, or clock arithmetic as it is sometimes known, is a special type of arithmetic involving integers and features in branches of mathematics such as number theory and abstract algebra. Modular arithmetic plays an important role in cryptography where for example, it is used to reduce calculations involving large and very large integers to calculations that involve smaller integers.
In modulo $m$ arithmetic all integers are replaced by their remainders after division by $m$. For example, if 8 is divided by $5$ the remainder is $3$. Here $5$ is called the modulus and we write $8 (mod\, 5) = 3$. We can perform a similar calculation for any number:
$0 (mod\, 5) = 0$
$1 (mod\, 5) = 1$
$2 (mod\, 5) = 2$
$3 (mod\, 5) = 3$
$4 (mod\, 5) = 4$
$5 (mod\, 5) = 0$
$6 (mod\, 5) = 1$
$7 (mod\, 5) = 2$, etc.
Every time we reach a multiple of $5$ we start counting from $0$ again.
The set of integers modulo $5$ is denoted: $\mathbb{Z}_5 = \{0, 1, 2, 3, 4\}$.
In general, the set of integers modulo $m$ is defined as: $\mathbb{Z}_m = \{0, 1, 2, 3, . . ., m-1\}$.
We actually encounter modular arithmetic every day when we tell the time as clocks work modulo $12$ or $24$ for hours and modulo $60$ for minutes and seconds. Hence the term clock arithmetic.
Example 21
On the 24 hour clock 17:00 hours corresponds to 5:00pm on the 12 hour clock. This value is obtained using modulo $12$ arithmetic, i.e. $17( mod\, 12 ) = 5$.
End of Example 214.1. Modular addition and multiplication tables
Modular arithmetic allows standard mathematical calculations such as addition, subtraction and multiplication. Division by certain numbers is also possible but is not considered here.
When the modulus is relatively small we can construct tables for arithmetic operations. These tables are also known as Cayley tables after the British mathematician Arthur Cayley (1821 – 1895). To illustrate the process we will construct addition and multiplication tables for $\mathbb{Z}_6$.
4.1. Addition Tables
- To create the addition table for $\mathbb{Z}_m$:
- Write the numbers from $0$ to $m - 1$ in the borders of the table, i.e. in the top row and leftmost column.
- Add these row and column numbers together to obtain their sum.
- Divide the sum by the modulus ($m$) to obtain the remainder which is the answer.
- Enter the answer at the intersection of the appropriate row and column.
Example 22
- The process is illustrated to generate the bottom row (highlighted) of the addition table for $\mathbb{Z}_6$. To obtain the entries in the bottom row, add 5 to each value that appears as a column header. Write the result modulo 6 in the appropriate cell where the row and column intersect.
- $( 5 + 0 )( mod\, 6 ) \equiv 5 ( mod\, 6 ) = 5$
- $( 5 + 1 )( mod\, 6 ) \equiv 6 ( mod\, 6 ) = 0$
- $( 5 + 2 )( mod\, 6 ) \equiv 7 ( mod\, 6 ) = 1$
- $( 5 + 3 )( mod\, 6 ) \equiv 8 ( mod\, 6 ) = 2$
- $( 5 + 4 )( mod\, 6 ) \equiv 9 ( mod\, 6 ) = 3$
- $( 5 + 5 )( mod\, 6 ) \equiv 10 ( mod\, 6 ) = 4$
The remaining entries are generated in a similar manner to give the table:
$+_6$ 0 1 2 3 4 5 0 0 1 2 3 4 5 1 1 2 3 4 5 0 2 2 3 4 5 0 1 3 3 4 5 0 1 2 4 4 5 0 1 2 3 5 5 0 1 2 3 4 Note that alternative notation for the addition of two integers, $a$ and $b$, modulo $m$ is $a +_mb$ and represents the remainder on division of $a + b$ by $m$. For example, $5 + _6 4 = 3$ .
End of Example 224.1.1. Additive Inverses
- The additive inverse of an integer $a$ is the integer $b$ such that $( a + b )(mod\, m) = 0$.
- We usually denote the inverse of an integer $a$ as $a^{-1}$ although some texts use, $\overline{a}$.
- Every integer in a modular arithmetic system has an additive inverse.
- In the addition table for $\mathbb{Z}_6$ we see that $( 4 + 2 )( mod\, 6 )= 0$ and so the additive inverse of $4$ in $\mathbb{Z}_6$ is $2$, i.e. $4^{-1} = 2$. Conversely, the additive inverse of $2$ in $\mathbb{Z}_6$ is $4$.
4.1.2. Properties of Addition Tables
- Each row (column) includes all the numbers from $\mathbb{Z}_m$.
- A number with an additive inverse will contain a ‘$0$’ in its row at the column corresponding to the additive inverse.
- Addition tables are symmetric with respect to the main diagonal.
- The entries on the minor-diagonal in the table for $\mathbb{Z}_m$ will all equal $m - 1$ . For example, in the above table for $\mathbb{Z}_6$ all the entries on the minor-diagonal equal $5$.
4.2. Multiplication Tables
- To create the multiplication table for $\mathbb{Z}_m$:
- Write the numbers from $0$ to $m - 1$ in the borders of the table, i.e. in the top row and leftmost column.
- Multiply each pair of row/column numbers together to obtain their product.
- Divide the product by the modulus ( $m$ ) to obtain the remainder which is the answer.
- Enter the answer at the intersection of the appropriate row and column.
Example 23
- The process is illustrated to generate the bottom row (highlighted) of the multiplication table for $\mathbb{Z}_6$. To obtain the entries in the bottom row, multiply each value that appears as a column header by $5$ and write the result modulo $6$ in the appropriate cell where row and column intersect.
- $( 5 \times 0 )( mod\, 6 ) \equiv 0 ( mod\, 6 ) = 0$
- $( 5 \times 1 )( mod\, 6 ) \equiv 5 ( mod\, 6 ) = 5$
- $( 5 \times 2 )( mod\, 6 ) \equiv 10 ( mod\, 6 ) = 4$
- $( 5 \times 3 )( mod\, 6 ) \equiv 15 ( mod\, 6 ) = 3$
- $( 5 \times 4 )( mod\, 6 ) \equiv 20 ( mod\, 6 ) = 2$
- $( 5 \times 5 )( mod\, 6 ) \equiv 25 ( mod\, 6 ) = 1$
The remaining entries are generated in a similar manner to give the table:
$\times_6$ 0 1 2 3 4 5 0 0 0 0 0 0 0 1 0 1 2 3 4 5 2 0 2 4 0 2 4 3 0 3 0 3 0 3 4 0 4 2 0 4 2 5 0 5 4 3 2 1 Note that alternative notation for the multiplication of two integers, $a$ and $b$, modulo $m$ is $a \times_m b$ and represents the remainder on division of $a \times b$ by $m$. For example, $5 \times_6 4 = 2$.
End of Example 234.2.1. Multiplicative Inverses
- Let $a, b$ and $m$ be positive integers. The multiplicative inverse of a number $a$ is defined to be the number $b$ such that $ab (mod\, m) = 1$.
- A multiplicative inverse will exist only if $a$ and $b$ are relatively prime.
- The number $0$ does not have a multiplicative inverse. Division by zero is not defined.
- The multiplication table for $\mathbb{Z}_6$ shows that the multiplicative inverse of $5$ in $\mathbb{Z}_6$ is itself because $( 5 \times 5 )(mod\, 6) = 1$. We write $5^{-1} = 5$ .
- The only two numbers with a multiplicative inverse modulo $6$ are $1$ and $5$, i.e. the only two numbers in $\mathbb{Z}_6$ that are relatively prime with $6$.
- Note that $2$ does not have a multiplicative inverse modulo $6$ as there is no number which when multiplied by $2$ yields $1$. In other words there is no solution ( $x$ ) to the equation $2x (mod\, 6) = 1$. Also, $3$ and $4$ have no inverses modulo $6$.
Note: In order for each non-zero element of $\mathbb{Z}_m$ to have a multiplicative inverse we must have that $m$ is a prime number. The previous example showed that as $6$ is not prime not every element in $\mathbb{Z}_6$ has an inverse.
Example 24
Construct a multiplication table for $\mathbb{Z}_5$ and identify which elements have an inverse.
$\times_5$ 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 - As $5$ is a prime number every non-zero element in $\mathbb{Z}_5$ has a multiplicative inverse.
- The inverses are as follows: $1^{-1} = 1,\; 2^{-1} = 3,\; 3^{-1} = 2$ and $4^{-1} = 4$.
End of Example 244.2.2. Properties of Multiplication Tables
- A number with a multiplicative inverse will contain a ‘$1$’ in its row at the column corresponding to the multiplicative inverse.
- Multiplication tables are symmetric with respect to the main diagonal.
- Rows corresponding to numbers relatively prime with $m$ are permutations of the first non-zero row and include all the numbers from $\mathbb{Z}_m$.
We have seen that for small values of $m$ multiplicative inverses, when they exist, can be found by constructing multiplication tables. We could alternatively use trial and error as the next example demonstrates.
Example 25
(i). Find the multiplicative inverse of $4$ mod $11$ if it exists.
(ii). Find the multiplicative inverse of $6$ mod $9$ if it exists.
Solution
(i). The multiplicative inverse exists as 4 and 11 are relatively prime, i.e. gcd $( 4, 11 ) = 1$. We require a number $x$ such that $4x ( mod\, 11 ) = 1$. Substitute each value from $0$ to $10$, starting with $0$, for $x$ to find that the solution is, $x = 3$ as $12( mod\, 11 ) = 1$.
(ii). The multiplicative inverse of $6$ mod $9$ does not exist as $6$ and $9$ are not relatively prime, i.e. gcd $(6, 9) = 3 \neq 1$. Hence, there is no solution to the equation, $6x ( mod\, 9 ) = 1$.
Watch the video at the link below on addition and multiplication tables:
📹 Lecture on Modulo Arithmetic Part 2
End of Example 25 -
Summary
- In this section we have introduced some elementary properties of number theory. You should now be able to:
- Identify properties of prime and composite numbers.
- Determine the prime factorisation of positive integers.
- Use prime factorisation to identify the LCM and GCD of two positive integers.
- Understand the division algorithm.
- Use the Euclidean algorithm to find the GCD of two positive integers.
- Identify relatively prime integers.
- Understand congruence modulo $m$, where $m$ is a positive integer.
- Use modular arithmetic to construct Cayley addition and multiplication tables.