Pearson
Higher Nationals in Computing
Unit 14: Mathematics
Chapter 02 : Modular Arithmetic
Contents
2 Modular Arithmetic ......................................................................................................... 3
2.1 Modulo Operator ..................................................................................................... 3
2.2 Visualize modulus with clocks ................................................................................. 3
2.3 Modulo in programming languages and calculators ............................................... 5
2.4 Identify multiplicative inverses in modular arithmetic............................................ 5
References to the Recommended Resources.......................................................................... 7
Unit 14 : Maths for Computing
2
2 Modular Arithmetic
2.1 Modulo Operator
When we divide two integers, we will have an equation that looks like the following:
A/B = Q Remainder R
• A is the dividend
• B is the divisor
• Q is the quotient
• R is the remainder
Sometimes, we are only interested in what the remainder is when we divide A by B
.For these cases there is an operator called the modulo operator (abbreviated as
mod).
Using the same A, B, Q, and R as above, we would have: A mod B = R
We would say this as A modulo B is equal to R. Where B is referred to as the
modulus.
For example:
13/5 = 2 remainder 3
13 mod 5 = 3
2.2 Visualize modulus with clocks
Observe what happens when we increment numbers by one and then divide them by
3.
• 0/3 = 0 remainder 0
• 1/3 = 0 remainder 1
• 2/3 = 0 remainder 2
• 3/3 = 0 remainder 0
• 4/3 = 1 remainder 1
• 5/3 = 1 remainder 2
• 6/3 = 2 remainder 0
The remainders start at 0 and increases by 1 each time, until the number reaches one less
than the number we are dividing by. After that, the sequence repeats.
By noticing this, we can visualize the modulo operator by using circles.
Unit 14 – Mathematics for Computing 3
We write 0 at the top of a circle and continuing clockwise writing integers 1, 2 ... up to one
less than the modulus.
For example, a clock with the 12 replaced by a 0 would be the circle for a modulus of 12.
To find the result of A mod B we can follow these steps:
• Construct this clock for size B
• Start at 0 and move around the clock A steps
• Wherever we land is our solution.
(If the number is positive, we step clockwise, if it's negative, we step counter-clockwise.)
Example :
i. 8 mod 4=?
With a modulus of 4 we make a clock with numbers 0, 1, 2, 3.
We start at 0 and go through 8 numbers in a clockwise sequence 1, 2, 3, 0, 1, 2, 3, 0.
We ended up at 0 so 8 mod 4=0.
ii. 7 mod 2=?
With a modulus of 2 we make a clock with numbers 0, 1.
We start at 0 and go through 7 numbers in a clockwise sequence 1, 0, 1, 0, 1, 0, 1.
Unit 14 – Mathematics for Computing 4
We ended up at 1 so 7 mod 2=1.
iii. −5 mod 3=?
With a modulus of 3 we make a clock with numbers 0, 1, 2.
We start at 0 and go through 5 numbers in counter-clockwise sequence (5 is negative)
2, 1, 0, 2, 1.
We ended up at 1 so −5 mod 3=1.
2.3 Modulo in programming languages and calculators
Many programming languages, and calculators, have a mod operator, typically
represented with the % symbol. If you calculate the result of a negative number, some
languages will give you a negative result.
e.g. -5 % 3 = -2.
2.4 Identify multiplicative inverses in modular arithmetic
What is an inverse?
Recall that a number multiplied by its inverse equals 1. From basic arithmetic we know that:
• The inverse of a number A is 1/A since A * 1/A = 1
e.g. the inverse of 5 is 1/5
• All real numbers other than 0 have an inverse
• Multiplying a number by the inverse of A is equivalent to dividing by A
e.g. 10/5 is the same as 10* 1/5
What is a modular inverse?
In modular arithmetic we do not have a division operation. However, we do have modular
inverses.
• The modular inverse of A (mod C) is A^-1
• (A * A^-1) ≡ 1 (mod C) or equivalently (A * A^-1) mod C = 1
• Only the numbers coprime to C (numbers that share no prime factors
with C) have a modular inverse (mod C)
Unit 14 – Mathematics for Computing 5
How to find modular inverse
A naive method of finding a modular inverse for A (mod C) is:
step 1. Calculate A * B mod C for B values 0 through C-1
step 2. The modular inverse of A mod C is the B value that makes A * B mod C = 1
Note that the term B mod C can only have an integer value 0 through C-1, so
testing larger values for B is redundant.
Example : Let A=3 and C=7. Find modular inverse of 3 mod 7.
Step 1 : Calculate A*B mod for B values through C-1.
i.e. Calculate 3*B mod for B values through 6-1.
• 3* 0 = 0 ≡ 0 (mod 7)
• 3* 1 = 3 ≡ 3 (mod 7)
• 3* 2 = 6 ≡ 6 (mod 7)
• 3 = 9 ≡ 2 (mod 7)
• 4 = 12 ≡ 5 (mod 7)
• 3 * 5 = 15 ≡ 1 (mod 7) <-- FOUND INVERSE! (Step 2) .
Modular inverse of 3 mod 7 is 5.
• 3 * 6 = 18 ≡ 4 (mod 7)
Unit 14 – Mathematics for Computing 6
References to the Recommended Resources
Textbooks
Stroud, K. A. (2009) Foundation Mathematics. Basingstoke: Palgrave Macmillan.
Journals
Journal of Computational Mathematics. Global Science Press.
Links
This unit links to the following related units:
Unit 18: Discrete Maths
Unit 33: Applied Analytical Models
Unit 14 – Mathematics for Computing 7