Greatest Common Divisor:

Let a and b be two positive integers, at least one of which is nonzero and their greatest common divisor (GCD) is a positive integer d such that;

• d|a and d|b
• If c |a and c|b then d>=c that is if c is the common divisor of a and b then c|d.

Notation :

The greatest common divisor of a and b is denoted by (a,b) or gcd(a,b).

Example:

• For any integer a which is not equals to zero so (a, a)=a
• If a|b then (a,b)=a
• (-8,36)=4
• (15,35)=5

Theorem:

Let a and b can be any two integers at least one of which is non zero. The (a,b) exists and is unique.

Proof:

1-Existence:

Observe that (a,b)=(|a|,|b|)thus we can suppose that a and b are both posistive. We also suppose a>=b (the case a<=b is symmetric). By divisor algorithm:

• a = bq1+r1           , 0<=r<=b

if r1=0 then b|a and (a,b)=b;

and we are done in this case.

Suppose r1 is not equal to zero. Once again by divisor algorithm applied to b and r1.

• b =r1q2+r2           , 0<=r2<r1

if r2=0 then r1|b and form (1)

a= r1q2q1+r1

a= r1(q1q2+1)

so r1|a

r1|a, r2|b

let s|a , s|b by definition

s|r1=(a-bq1) this is from equation 1.

So r1= (a,b)

Suppose r2 is not equal to zero. We repeat the process. The process must terminate in finite number of steps, say n. thus we shall arrive at zero remainder after that nth step and have a sequence of integers r2 such that b> r1> r2> … > =0

r (n-2)=r(n-1)q(r) +r(n)       for all n>=3

and r(n-1)=q(n+1) r(n)

this last expression gives r(n)|r(n-1), therefore r(n)|r(n-2) … r(n)|b and r(n)|a. if S were a common divisor of a and b then S|a and S|b which shows S|r1 by (1) given above.

S|r2

…

So on till S|r(n).

Hence r(n)=(a,b) showing g.c.d of a and b exists.

Uniqueness:

If d1 and d2 are two g.c.ds of a and b then by definition d1>=d2 and d2>=d1 so d1=d2.

Hence proved.

Corollary:

Let a and b be any two integers then exists integers x and y such that (a,b)=ax+by.

WELL ORDERING PRINCIPLE: (WOP):

Every nonempty subset S of nonnegative integer contain a least (or smallest) element, in other words, S contains integers n such that n<=x for all x in S.

Theorem:

Let a and b be any integers at least one of them is nonzero. Then there exist integers x and y such that (a,b)=ax+by.

Proof:

Let d=(a,b) and S be a set defined as S={ au+bv such that au+bv >0, uv integers}

Since at least one of a or b is non zero therefore either |a| or |b| is in S. so that s is not equal to empty set. By WOP (well ordering property) S has a least element say d= au*+bv*

By definition:

D<=|a|,|b|

By division algorithm as applied to |d| and d.

|a|=dq+r                                       , 0<=r<d

r =|a|-dq

r= |a|-q(au*+bv*)                  b>=0

and is the of form au+bv. Hence by choice of d,r = 0

|a|=dq

d |a

similarly d|b id c|a and c|b so c|au*+bv* (using theorem) greatest common divisor is

hence d=(a,b)= au*+bv*.

Corollary:

If a and b are given integers not both zero, then the set T={ ax+by, such that x,y are integers} consists of multiple of g=g.c.d (a,b).

(this theorem always hold)

Proof:

Since g|a and g|b so g|ax+by for all integers x,y belongs to Z where Z is set of integers. Then every member of T is a multiple of g. if g= ax*+by* for suitable integers x* and y* so that any multiple ng of g is of the form ng = n(ax*+by*)

So

ng = n(ax*+by*)

ng = a(nx*)+b(ny*)

ng is a linear combination of a and b and definition lies in T.

Theorem:

Let a,b and c be non –zero integers, then (ac, bc)=|c|(a,b)

Proof:

Let d=(ac,bc) and d*=|c|(a,b)

As,

d = acx+bcy

for some integer x and y , hemce d= |c| / |c| (acx+bcy)

d +c/ |c| (a. |c|. x + b. |c| . y )

now,

d*= |c|(a,b)          (1)

and since (a,b)|a and (a,b)|b, we find that d* is a common divisor of a. |c| and b. |c| and therefore d*|d

next , since d*|(|c|)= (a,b) from (1)

d*|(|c|)= (a,b) =au+bv

for some integers u and v. this applies that d*= a. |c|.u+b.|c|.v

d*= c/c (a.|c|.u+b.|c|.v)

d*=|c|/c (acu+bcv)

but d is the greatest common divisor of ac and bc and hence d|d*. since d*|d and d|d*, we conclude that |d|=|d*| (using a|b, b|a so |a|=|b|)

since both d and d* are positive

hence d=d* so (ac,bc)=|c|(a,b).

Corollary:

If d=(a,b) then  (a|d , b|d)=1

Proof:

Since d=(a,b) , a|d and b|d are both integers. Also:

d =(a,b)

d = d|d (a,b)

d = (da|d, db|d)

d= d(a|d, b|d)

so (a|d, b|d)= d|d

hence ( a|d, b|d) = 1

hence proved.

Example:

2= ( 2, 8)

2= 2(1, 4)

2|2=(1,4)

1=(1,4)

Read Also: History of pen | types of pen.