Euclidean Algorithm

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

Theorem 4
If gcd (a,b) = d,then .

Proof – Since gcd(a,b) is equal to d,then from theorem 3,exist x and y such that d = ax + by. Divide both sides by d to obtain 1=(a/d)x+(b/d)y. Because d is the common divisor of a and b,then it is sure that a/d and b/d is integers. Thus,

Euclidean Algorithm

The Euclidean algorithm, also called Euclid's algorithm, is an algorithm for finding the greatest common divisor of two numbers a and b . The algorithm can also be defined for more general rings than just the integers. There are even principal rings which are not Euclidean but where the equivalent of the Euclidean algorithm can be defined. The algorithm for rational numbers was given in Book VII of Euclid's Elements. The algorithm for reals appeared in Book X, making it the earliest example of an integer relation algorithm (Ferguson et al. 1999).

Example 1 - Find the gcd of 754 and 56

765 - (13) * (56) = 37
56 - (1) * (37) = 19
37 - (1) * (19) = 18
19 - (1) * (18) = 1
18 - (18) * (1) = 0

So gcd of 765 and 56 is 1

Example 2 - Find the gcd of 342 and 76

342 - (4) * (76) = 38
76 - (2) * (38) = 0

So gcd of 342 and 76 is 38

Myspace Graphics