Page 21 - DMTH403_ABSTRACT_ALGEBRA

Abstract Algebra

Notes Therefore, by the principle of induction, P(n) is true for all n in N.
Now, use the principle of induction to prove the following property of numbers that you must
have used time and again.

1.5.2 Divisibility in Z

One of the fundamental ideas of number theory is the divisibility of integers.
Definition: Let a, b " , a % 0. Then, we say that a divides b if there exists an integer c such that
b = ac. We write this as a | b and say that a is a divisor (or factor) of b, or b is divisible by a, or
b is a multiple of a.
If a does not divide b we write a × b.

We give some properties of divisibility of integers in the following exercise. You can prove
them very easily.
We will now give a result, to prove which we use Theorem 5.

Theorem 7 (Division Algorithm): Let a, b  Z, b > 0. Then there exist unique integers q, r such
that a = qb + r, .where 0 5 r < b.
Proof: We will first prove that q and r exist. Then we will show that they are unique. To prove
their existence, we will consider three different situations : a = 0, a > 0, a < 0.
Case 1 (a = 0): Take q = 0, r = 0. Then a = qb + r.
Case 2 (a > 0): Let P(n) be the statement that n = qb + r for some q, r  Z, 0  r < b.

Now let us see if P(l) is true.
If b = l, we can take q = l, r = 0, and thus, 1 = 1.1 + 0.
If b  l, then take q = 0, r = 1, i.e., 1 = 0.b + l.

So, P(1) is true.
Now suppose P(n – 1) is me, i.e., (n – 1) = q b + r for some q , r  Z, 0  r < b. But then r  b – 1,
1
1
1
l
1
l
i.e., r + 1  b. Therefore,
1


 q b (r  1), if (r  1) b
1
1
1
n  
1

 (q  1)b 0,if r   b
1
1
This shows that P(n) is true. Hence, by Theorem 5, P(n) is true, for any n  N. That is, for a > 0, a
= qb + r, q, r  Z, 0  r < b.
Case 3 (a < 0): Here (-a) > 0. Therefore, by Case 2, we can write
(–a) = qb + r’, 0  r’ < b

 ( q)b, if r  0
i.e., a  


 (–q – 1)b + (b - r ), if 0 < r < b
This proves the existence of the integers q, r with the required properties.
Now let q’, r’ be in Z such that a = qb + r and a = q’b + r’, where 0 5 r, r’ < b. Then r – r’ = b(q’ – q).
Thus, b | (r – r’). But | r – r’ | < b. Hence, r – r’ = 0, i.e., r = r’ and q = q’. So we have proved the
uniqueness of q and r.
In the expression, a = qb + r, 0 & r < b, r is called the remainder obtained when a is divided by b.
14 LOVELY PROFESSIONAL UNIVERSITY