1st Course for high Diploma, Number Theory Lecture 2: Theory on the greatest Common Divisor and the Linear Combinations

Theorem 1.3.2 Given integers a and b, not both of which are zero, there exist integers x and y such that gcd(a, b) = ax + by.

Proof. Consider the set S of all positive linear combinations of a and b:
S = {au + bv | au + bv > 0; u, v integers}.

Notice first that S is not empty. For example, if a ? 0, then the integer |a|= au+ b ? 0 lies in S, where we choose u = 1 or u = - 1 according as a is positive or negative. By the Well-Ordering Principle, S must contain a smallest element d. Thus, from the definition of S, there exist integers x and y for which d = ax + by. So it can claim that d = gcd(a, b).

Using the Division Algorithm, one can obtain the integers q and r such that a = qd + r , where 0 ? r < d. Then r can be written in the form
r = a ? qd = a ? q(ax + by)
= a(1 ? qx) + b(?qy).

If r were positive, then this representation would imply that r is a member of S, contradicting the fact that d is the least integer in S (recall that r < d). Therefore, r=0, and so a= qd, or equivalently d|a. By similar reasoning, d | b, so d is a common divisor of a and b.

Now if c is an arbitrary positive common divisor of the integers a and b, then part (g) of Theorem (1.3.1) allows us to conclude that c | (ax + by); that is, c | d. By part (f) of the same theorem, c = | c |? | d |= d, so that d is greater than every positive common divisor of a and b. One can see that d = gcd(a, b). ?

Based on the proof of Theorem (1.3.2), the greatest common divisor of a and b may be described as the smallest positive integer of the form ax + by. Consider the case in which a = 6 and b = 15. Here, the set S becomes
S = {6(?2) + 15 · 1, 6(?1) + 15 · 1, 6 · 1 + 15 · 0,.. .}
= {3, 9, 6,.. .}
So, it observes that the 3 is the smallest integer in S, whence 3= gcd(6, 15).