If a and b are integers , not both zero,and d be a positive integer. Then d=gcd(a,b) if and only if d satisfies

 

If a and b are integers , not both zero,and d be a positive integer. Then d=gcd(a,b) if and only if d satisfies

(1)       d|a and d|b.

(2)       if c|a and c|b, then c|d.

Proof:-

Suppose d=gcd(a,b), then d≥0 and d satisfied or can be expressed as ,

d=ax+by……………………eq(1)

Now if c is any other common factor of a and b then their exist p and q€Z such that ,

a=cp and b=cq

by putting the value of a and b in eq(1)

that is ,

d=(cp)x)+(cq)y

d=c(px+qy)

in other words c divides d.