Arithmetic Operations
Module n
CONTINUATION. . .
Modulo 𝑛
• Two integers 𝑎 and 𝑏 are said to be congruent modulo 𝒏, where 𝑛 is a natural
𝑎−𝑏
number, if is an integer. In this case, we write 𝑎 ≡ 𝑏 mod 𝑛. The number 𝑛 is
𝑛
called the modules. The statement 𝑎 ≡ 𝑏 mod 𝑛 is called a congruence.
Example: Determine whether the congruence is true.
𝟐𝟗 ≡ 𝟖 mod 3
29−8 21
Find: = = 7. Because 7 is an integer, 29 ≡ 8 mod 3 is a true congruence.
3 3
29 ≡ 8 mod 3
Since both 29 and 8 have remainder 2 when divided by 2
There are many other numbers congruent to 8 modulo 3, but of all
these, only one is a whole number less than the modulus.
This number is the result when 𝑒𝑣𝑎𝑙𝑢𝑎𝑡𝑖𝑛𝑔 a modulo expression, and
in this case we use an equal sign. Because 2 ≡ 8 mod 3 and 2 is less
than the modulus, we can write 8 mod 3 = 2. In general, 𝑚 mod 𝑛
becomes the remainder when 𝑚 divided by 𝑛.
Arithmetic modulo 𝑛 (where 𝑛 is a natural number) requires us to
evaluate a modular expression after using the standard rules of
arithmetic.
Thus we perform arithmetic operation and then divide by the modulus.
The answer is the remainder.
The result of an arithmetic operation mod 𝑛 is always a whole number
less than 𝑛.
Addition modulo n
• Evaluate 23 + 38 mod 12
Solution:
Add 23 + 38 to produce 61. To evaluate 61 mod 12, divide 61 by the
modulus , 12. The answer is the remainder.
23 + 38 mod 12 = 1 The answer is 1
Practice:
Evaluate: (51 + 72) mod 3
In modular arithmetic, adding the modulus to a number does not change the equivalent value of the number.
For instance,
13 ≡ 6 𝑚𝑜𝑑 7
20 ≡ 6 𝑚𝑜𝑑 7 *add 7 to 13
27 ≡ 6 𝑚𝑜𝑑 7 *add 7 to 20
10 ≡ 1 𝑚𝑜𝑑 3
13 ≡ 1 𝑚𝑜𝑑 3 *add 3 to 10
16 ≡ 1 𝑚𝑜𝑑 3 *add 3 to 13
• To understand why the value does not change, consider 7 ≡ 0 mod 7 and 3 ≡ 0 mod 3. That is,
in mod 7 arithmetic, 7 is equivalent to 0; in mod 3 arithmetic, 3 is equivalent to 0.
• Just adding 0 to a number does not change the value of the number in regular arithmetic, in
modular arithmetic adding the modules to a number does not change the value of the number.
• This Property of modular arithmetic sometimes used in subtraction.
It is possible to use negative number module 𝑛.
Example:
−2−5 7
−2 ≡ 5 mod 7 because = − = −1, an integer.
7 7
−15−𝑥
Suppose we want to find 𝑥 so that −15 ≡ mod 6. Using the definition of modulo 𝑛, we need to find 𝑥 so that is an
6
integer. To do this, re write the expression and then try various values of 𝑥 from 0 to the modules until the value of the expression is
an integer.
−15−𝑥 −(15+𝑥)
=
6 6
−(15+0) 15
Where 𝑥 = 0, =− , not an integer
6 6
−(15+1) 16 8
Where 𝑥 = 1, =− = − , not an integer
6 6 3
−(15+2) 17
Where 𝑥 = 2, =− , not an integer
6 6
−(15+3) 18
Where 𝑥 = 3, =− = −3, an integer −15 ≡ 3 mod 6
6 6
Calculating times
Disregarding A.M or P.M. If it is 5 o’clock now, what time was it 57 hours ago?
Solution
The time can be determined by calculating (5 − 57) mod 12. Because 5 − 57 = −52 is a negative
number, find a whole number 𝑥 less than the modulus 12, so that −52 ≡ 𝑥 mod 12.
−52−𝑥 − 52+𝑥
This means to find 𝑥 so that = is an integer.
12 12
Evaluating the expression for whole number values 𝑥 less than 12,
− 52+8 60
If 𝑥 = 8, = − = −5, an integer. Thus 5 − 57 , mod 12 = 8. Therefore, if it is 5 o-’clock
12 12
now, 57 hours ago it was 8 o’clock.
Multiplication Modulo n
Evaluate: 5 ∙ 23 mod 11
Solution
Find the product 5 ∙ 23 and then divide by the modulus, 11.
The answer is the remainder
SOLVING CONGRUENCE
• Solving congruence equation means finding all whole number values of the variable for which the
congruence is true.
Example: solve 3𝑥 + 5 ≡ 3 mod 4, we search for whole number values of 𝑥 for which the congruence is true.
3 0 + 5 ≢ 3 mod 4
3 1 + 5 ≢ 3 mod 4
3 2 + 5 ≡ 3 mod 4 2 is a solution
3 4 + 5 ≢ 3 mod 4
3 5 + 5 ≢ 3 mod 4
3 6 + 5 ≡ 3 mod 4 6 is a solution