Page 35 - DMTH502_LINEAR_ALGEBRA

Unit 1: Vector Space over Fields

Addition Modulo m Notes

We shall now define a new type of addition known as “addition modulo m” and written as
a + b where a and b are any integers and m is a fixed positive integer.
m
By definition, we have


a + mb = r, 0 r m
where r is the least non-negative remainder when a + b, i.e., the ordinary sum of the a and b, is
divided by m.
For example 5 + 3 = 2, since 5 + 3 = 8 = 1 (6) + 2, i.e., 2 is the least non-negative remainder when
6
5 + 3 is divided by 6.
Similarly, 5 + 2 = 0, 4 + 2 = 0; 3 + 1 = 1, 15 + 7 = 2.
7 3 3 5
Thus to find a + b, we add a and b in the ordinary way and then from the sum, we remove
m
integral multiples of m in such a way that the remainder r is either 0 or a positive integer less
than m.
When a and b are two integers such that a – b is divisible by a fixed positive integer m, then we
write
a = b (mod m)
which is read as “a is concurrent to b modulo m”.

Thus a = b (mod m) if a – b is divisible by m. For example 13 = 3 (mod 5) since 13 – 3 = 10 is divisible
by 5, 5 = 5 (mod 5), 16 = 4 (mod 6); –20 = 4 (mod 6)

Multiplication Modulo p

We shall now define a new type of multiplication known as “multiplication modulo p” and
written as a × b where a and b are any integers and p is a fixed positive integer.
p
a × b = r, 0 r p,
p
where r is the least non-negative remainder when ab, i.e., the ordinary product of a and b, is
divided by p. For example 4 × 2 = 1, since 4 × 2 = 8 = 1(7) + 1.
7
It can be easily shown that if a = b (mod p) then a × C = b × C.
p p
Additive Group of Integers Modulo m

The set G = {0, 1, 2, … m – 1} of first m non-negative integers is a group, the composition being
addition reduced modulo m.
Closure Property: We have by definition of addition modulo m,
a + b = r
m
where r is the least non-negative remainder when the ordinary sum a + b is divided by m.
Obviously 0 r m – 1. Therefore for all a, b G, we have a + b G and thus G is closed with
m
respect to the composition addition modulo m.
Associative Property: Let a, b, c be any arbitrary elements in G.
Then (a + b) + c = (a + b) + c
m m m
b + c = b + c (mod m)
m

LOVELY PROFESSIONAL UNIVERSITY 29