Scribd
Upload
2 views1 page

Euclids Algorithm 1

The document describes the Euclidean algorithm for computing the greatest common divisor (gcd) of two positive integers a and b. It includes lemmas proving the termination and correctness of the algorithm, demonstrating that the gcd remains invariant throughout the iterations. The algorithm concludes by returning the gcd when the two numbers become equal.

Uploaded by

qyltums
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
2 views1 page

Euclids Algorithm 1

The document describes the Euclidean algorithm for computing the greatest common divisor (gcd) of two positive integers a and b. It includes lemmas proving the termination and correctness of the algorithm, demonstrating that the gcd remains invariant throughout the iterations. The algorithm concludes by returning the gcd when the two numbers become equal.

Uploaded by

qyltums
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 1

Algorithm EUCLID

Input: a, b ∈ Z+
Output: gcd(a, b)
while a = b do
​

if a > b then
a=a−b
else
b=b−a
end if
end while
return a

lemma 1. termination of EUCLID

Let a , b represent the program variables a, b at the i-th iteration. Then,


i i

ai+1 = a − b
i ⟺ a > b . Thus, a
i i i> 0. b > 0 by a similar argument. Since the series
i+1 i+1

a + b is monotonically decreasing, the program is finitely bounded by (a, b) = (1, 1) ■


i i

lemma 2

for a > b ∈ Z, let a − b = d, c = gcd(a, b). Then


c ∣ a, c ∣ b ⟹ and c(x − yk) = r ⟹ c ∣ r. Suppose
∃x, y ∈ Z, a = cx, b = cy, gcd(x, y) = 1

that gcd(y, x − yk) = d > 1. Then ∃(m, n), dm = y, dn = x − yk yields dn = x − dmk ⟹ d ∣ x


, which is contradictory. Thus, gcd(a, b) = gcd(a − b, b) ■

theorem 2. correctness of EUCLID

Let a , b represent the program variables a, b at the i-th iteration, with (a , b ) = (a, b). Claim
i i 0 0

that at iteration i, gcd(a , b ) = gcd(a, b). The base case is trivially true. Now, suppose that the
i i

claim holds for i = n. For i = n + 1,

(an − bn, bn), an > bn


(an+1, bn+1) = {
(an, bn − an), an < bn

Without loss of generality, by lemma 2, gcd(a , b ) = gcd(a − b , b ). Thus, the loop


n+1 n+1 n n n

invariant holds for initialization and maintenance. When the loop inevitably terminates (
lemma 1) at iteration z, gcd(a , b ) = gcd(a, b) and a = b . Trivially, gcd(a , a ) = a , and so the
z z z z z z z

program correctly returns gcd(a, b).

You might also like