Greatest Common Divisor

• Print

Ifdivides two integersandthenis called a common divisor ofandHence 1 is a common divisor of any two numbersandEvery pair of integersandhas a divisorwhich can be expressed as a linear combinationofandBecause divides and b, d divides every linear combinationof a and b. Moreover, every common divisor ofanddivides this

Proof: AssumeWe use induction onwhereIfthenand we can takewithAssume then that the theorem has been proved forBy symmetry we can assumeIftakeIf apply the theorem toandSincethe induction assumption is applicable and there is a common divisorofandof the formThisalso dividessois a common divisor ofandand we havea linear combination ofandTo complete the proof we need to show that every common divisor dividesbut a common divisor dividesandand hence by linearity dividesIforor both we can apply this result toand

Moreoveris unique and is the greatest common divisor, gcd, ofandhas the following properties where

a)

b)

c)

d)and

Proof

a)impliesandfor somesoThe same argument withandandinterchanged impliesthereforeand

b)implies there existsuch thatthen there exists also such thatthereforeNow interchangewithandwithwith the same reasoning to getHenceand

c)Letand letWritethen(1) and sobecausedivides bothandAlso (1) shows thatand Hence

Proof: Sincewe can writeThereforeButand so