Mathematics in the modern world

(Finals week 2)

Modular Arithmetic
In Mathematics, a modular arithmetic is a system of arithmetic for integers, where numbers “wrap round”
upon reaching a certain value, which is modulus.

This is a type of number system where numbers are represented by the remainder after division by the
modulo number.

Modulo
We define Z n as the set of integers from {0 ,1 , .. . , n−1 } modulo n, i.e.

Z n={0 , 1 , .. . , n−1 }

Note that Z n has exactly n positive integers. In particular, we define Z n with the following set of the
positive integers:
Z3 ={0 , 1 ,2 }, modulo 3
Z5 ={0 , 1 ,2 , 3 , 4 }, modulo 5
Z7 ={0 , 1 ,2 , 3 , 4 ,5 , 6 }, modulo 7
In Z n , modulo is simply the remainder r when an integer a ∈ Z is divided by n, i.e.

a
has r <n
n

Illustrations: Find the remainder of the integers (a) 9; (b) 29; in Z3 , Z 4 , Z 5 , Z 7 .

a) a = 9 b) a = 29
In Z3 , r=0 In Z3 , r = 2
In Z 4, r=1 In Z 4, r = 1
In Z5 , r=4 In Z5 , r = 4
In Z7 , r=2 In Z7 , r = 1

Example 1. Perform the following in Z3 , Z 5 , Z 7:

a. 3+5 b. 3 •5
c. 4 +6 d. 6 •2

Z3 Z5 Z7

A) 3+5 2 3 1

B) 3 ∙5 0 0 1

C) 4 +6 1 0 3
 D) 4 ∙6 0 4 3

Constructing tables of Z n

1. In Z3 ={0 , 1 ,2 }
Z3 is closed under the binary operations of addition and multiplication of integers modulo 3.

+ 0 1 2 • 0 1 2
0 0 1 2 0 0 0 0
1 1 2 0 1 0 1 2
2 2 0 1 2 0 2 1

Table 1 Table 2

Illustrations:
a) In Z3 , find the following based on the table 1:
-1 = additive inverse of 1 = 2
-2 = additive inverse of 2 = 1

b) In Z3 , find the following based on the table 2:

1 −1
=2 = multiplicative inverse of 2 = 2
2

2. In Z5 ={0 , 1 ,2 , 3 , 4 }
Z5 is closed under the binary operations of addition and multiplication of integers modulo 5 as
indicated in the following tables.

+ 0 1 2 3 4 • 0 1 2 3 4
0 0 1 2 3 4 0 0 0 0 0 0
1 1 2 3 4 0 1 0 1 2 3 4
2 2 3 4 0 1 2 0 2 4 1 3
3 3 4 0 1 2 3 0 3 1 4 2
4 4 0 1 2 3 4 0 4 3 2 1

Table 3 Table 4

Illustrations:
a) In Z5 , find the following based on the table 3:
-1 = additive inverse of 1, or negative of 1 = _____4___
-2 = additive inverse of 2, or negative of 2 = ____3____
-3 = additive inverse of 3, or negative of 3 = ____2____
-4 = additive inverse of 4, or negative of 4 = ____1____

b) In Z5 , find the following based on the table 4:

1 −1
=2 = multiplicative inverse of 2 = ___3__
2
 1 −1
=3 = multiplicative inverse of 3 = ___2__
3

1
=4−1 = multiplicative inverse of 4 = __4___
4
Example 2. In Z3 , find the following:

1
a) 2−3=¿ 2 d) −3+ =¿ 2
2
−−1
b) −2−1=¿ 0 (
e) 2
2 ) =1
−1 −1
c) =¿ -1(2) = -2 = 1 f) =1
2 2

Example 3. In Z5 , find the following:

1 1 2
a) + =2+3=0 d) =1
3 2 3
1 −2 3
b) −3+ =¿ 1 e) − =4
4 3 4
−1 3 −1
c) + =¿ 0
3 4
f) −2 ( )
3
=4

Congruences
Definition: If m is a positive integer and m |a−b , then we say that a is congruent to b modulo m and in
symbol, a ≡ b(mod m). For instance 13 ≡5(mod 4) since 4|13−5 .

The following are equivalent to each other and may be used interchangeably.
a) a ≡ b(mod m)
b) m |a−b
c) a=b+ mk , for some integer k .

Theorem 1. Every integer is congruent modulo to exactly one of the integers 0 , 1 ,2 , . .. , m−1.
Example
38 ≡2(mod 3), r =2< 3
38 ≡2( mod 4), r =2< 4
38 ≡3( mod 5), r =3<5

Theorem 2. The integers a and b leave the same remainder on division by m iff a ≡ b ( mod m ) .

Congruence is a generalized form of equality. Many properties of equality are being carried over to
congruences. In the next theorem, like equality between two numbers, we see that congruence satisfy the
three properties of an equivalence relation.
i ¿ Reflexive: a ≡ a ( mod m )
ii ¿ Symmetric: If a ≡ b ( mod m ) , then b ≡ a(mod m)
 iii ¿ Transitive: If a ≡ b(mod m) and b ≡ c ( mod m ) , then a ≡ c (mod m).

Theorem 3. Congruence of integers modulo m is an equivalence relation.

Theorem 4. If a i ≡ bi (mod m) for I = 1, 2, . . . , n, then

n n
i¿ ∑ ai ≡ ∑ bi ( mod m)
i=1 i=1

n n
ii ¿ ∏ ai ≡ ∏ b i (mod m)
i=1 i=1

Example: If 1 ≡−2 ( mod 3 ) , and 2 ≡−1(mod 3), then

1+2 ≡−2+ (−1 )( mod 3 )
1 ( 2 ) ≡−2 (−1 ) mod 3 ¿

Corollary 1. Given a, b, c∈ Z , then a ≡ b ( mod m ) , iff

a+ b ≡b+ c ( mod m )

Corollary 2. If a ≡ b(mod m) and c ≡d (mod m), then

i¿ ac ≡bc (mod m) for any integer c
Example: 3 ≡−1 ( mod 4 ) , then 3 ( 2 ) ≡−1 ( 2 ) (mod 4)

ii ¿ ax +cy ≡bx +dy (mod m)

iii ¿ a k ≡ bk (mod m) for any integer k
Example: 3 ≡−1 ( mod 4 ) , then 32 ≡(−1)2 (mod 4)

iv ¿ a−c ≡b−d (mod m)

Example: 1 ≡4 (mod 3), −2 ≡1(mod 3), then 1−(−2 ) ≡ 4−1(mod 3)

Example 1. Find the least residue modulo 7 of 37 • 45+6 •158

Solution

37 ≡2 ( mod 7 ) , 45 ≡ 3 ( mod 7 ) , 6 ≡−1 ( mod 7 ) ,

15 ≡1 ( mod 7 ) , 158 ≡18 ( mod 7 ) ≡1(mod 7)

37 • 45+6 •158 ≡ ( 2 ) ∙ (3 )+ (−1 )( 1 ) (mod 7)

≡6−1 ( mod 7 )

37 • 45+6 •158 ≡5( mod 7)

Example 2. Find the unit digit of a) 278 b) 3103

Solution:
a) 23 ≡−2(mod 10) b) 32 ≡−1(mod 10)
5 51
( 23 ) ≡ (−2 )5 ( mod10) ( 32 ) ≡(−1)51 (mod 10)

215 ≡−2(mod 10) 3102 ≡−1(mod 10)

5
( 215 ) ≡(−2)5 ( mod 10 ) ( 3102 ) ∙3 ≡(−1)( 3)( mod 10)

275 ∙ 23 ≡ (−2 ) (−2 )( mod 10 ) 3103 ≡−3 (mod 10)

278 ≡ 4 (mod 10) 3103 ≡ 7(mod 10)

Example 3. Find the remainder when 4 220 is divided by 65.

Solution:
4 3 ≡−1(mod 65)
73
( 43 ) ≡ (−1 )73 ( mod 65 )

4 219 ≡−1(mod 65)

( 4219 ) 4 ≡ (−1 )( 4 ) (mod 65)

4 220 ≡ 61 ( mod 65 )