Page 22 - DMTH403_ABSTRACT_ALGEBRA

Unit 1: Generating Sets

Definition: Let a, b  Z. c  Z is called a common divisor of a and b if c | a and c | b. For example, Notes
2 is a common divisor of 2 and 4. You know that 1 and –1 are common divisors of a and b, for any
a, b  Z. Thus, a pair of integers do have more than one common divisor. This fact leads us to the
following definition.
Definition: An integer d is said to be a greatest common divisor (g.c.d. in short) of two non-zero
integers a and b if

(i) d | a and d | b, and
(ii) if c | a and c | b, then c | d.
Note that if d and d’ are two g.c.d s of a and b, then (ii) says that d | d’ and d’ | d. Thus, d = d’.
But then only one of them is positive. This unique positive g.c.d. is denoted by (a, b).
We will now show that (a, b) exists for any non-zero integers a and b. You will also see how
useful the well-ordering principle is.

Theorem 8: Any two non-zero integers a and b have a g.c.d., and (a, b) = ma+nb, for some m,
n  Z.
Proof: Let S = {xa + yb | x, y  Z, (xa + yb) > 0).

Since a + b > 0, a + b  S, i.e., S  0. But then, by the well-ordering principle, S has a least
2
2
2
2
element, say d = ma + nb for some m, n  Z. We show that d = (a, b).
Now d  S. Therefore, d > 0. So, by this division algorithm we can write
a = qd + r, 0  r < d. Thus,
r = a – qd = a – q(ma + nb) = (1 – qm)a + (–qn)b.
Now, if r  0, then r  S, which contradicts the minimality of d in S. Thus, r = 0, i.e., a = qd, i.e.,
d | a. We can similarly show that d | b. Thus, d is a common divisor of a and b.
Now, let c be an integer such that c | a and c | b.
Then a = a c, b = b c for some a , b  Z.
1
1
1
1
But then d = ma + nb = ma c + nb c = (ma + nb )c. Thus, c | d, So we have shown that d is a g.c.d.
1
1
l
1
In fact, it is the unique positive g.c.d. (a,b).
For example, the g.c.d. of 2 and 10 is 2 = 1.2 + 0.10, and the g.c.d, of 2 and 3 is 1 = (–1)2 + l(3).
Pairs of integers whose g.c.d. is 1 have a special name.
Definition: If (a,b) = 1, then the two integers a and b are said to be relatively prime (or coprime)
to each other.
Using Theorem 8, we can say that a and b are coprime to each other iff there, exist m, n  Z such
that 1 = ma + nb.
The next theorem shows us a nice property of relatively prime numbers.
Theorem 9: If a,b  Z; such that (a, b) = 1 and b | ac, then b | d.
Proof: We know that 3 m, n  Z such that 1 = ma + nb. Then c = c.1 = c(ma+nb) = mac + nbc.

Now, b | ac and b | bk.  b | (mac + nbc). Thus, b | c.
Let us now discuss prime factorisation.
Definition: A natural number p ( 1) is called a prime if its only divisors are 1 and p. If a natural
number n (% 1) is not a prime, then it is called a composite number.

LOVELY PROFESSIONAL UNIVERSITY 15