OpenCart Templates
Saturday , July 22 2017
Home / Elementary Number Theory / Euclidean Algorithm

Euclidean Algorithm

Euclidean Algorithm: The Euclidean algorithm may be described as follows: Let a and b be two integers whose common divisor is desired. Since gcd(|a|,|b|)= gcd(a, b) there is no harm is assuming that a ≥ b > 0. The first step is to apply the division algorithm to a and b to get

a = q1b + r1 ;           0 ≤ r1 < b

If it happens that r1 = 0 then b\a and gcd(a, b) = a, when r1 ≠ 0, divided by r1 to produce integers q2 and r2 satisfying

b = q2r1 + r2; 0 ≤ r2 < r1

If r2 = 0, then we stop. Otherwise proceed as before to obtain.

r1 = q3r2 + r3 ; 0 ≤ r3 < r2

This division process continuous until some zero remainder appears, say at the     (n + 1) th stage where rn-1 is divided by rn(a zero remainder occurs sooner or later since the decreasing sequence b > r1 > r2 > … ≥ 0 cannot more than b integers.)

The result is the following system of equations

a = q1b + r1; 0< r1 < b

b = q2r1 + r2; 0 < r2 < r1

r1 = q3r2 + r3;  0 < r3 < r2


rn-2 = qnrn-1 + rn; 0 < rn < rn-1

rn-1 = qn+1rn + 0

We argue that rn the last non zero remainder which appears in this manner is equal to gcd(a, b). (Proved)

Lemma: If a = qb + r then gcd(a, b) = gcd(b, r).

Proof: If d = gcd(a, b), then the relations d\a and d\b imply that d\(a – qb) or d\r.

Thus d is a common divisor of b and r. On the other hand, if c is an arbitrary common divisors of b and r, then c\(qb + r), whence c\a. This makes c is a common divisor of a and b, so that c ≤ d. It now follows from the definition of gcd(b, r) that

d = gcd(b, r). (Proved)

Check Also

Application of Euclidian’s algorithm in Diophantine equation

Problem-1: Which of the following Diophantine equations cannot be solved –   a) 6x + ...

Leave a Reply

Your email address will not be published. Required fields are marked *