Euclidean algorithmEuclidean Algorithm Prove Let (a,b) ∈ Z 1. If a≠0≠b then (a,b) ≠ 0 2. (a,b) = 1 & a ∈ {1,-1}

1 Answer | Add Yours

giorgiana1976's profile pic

giorgiana1976 | College Teacher | (Level 3) Valedictorian

Posted on

If (a,b) = 1, therefore a and b are relatively prime because they not have common positive factors.

If 1 is the greatest common divisor of a and b, then:

a = 1*x

b = 1*y

where x and y are positive integers.

According to Euclidean algorithm, we'll get:

ax + by = 1

Generally, we can write the iterative process of finding the greatest common divisor of a and b as:

a = q0*b + r0

b = q1*r0 + r1

.........................

The ultimate remainder that has no zero value is the common divisor of a and b.

So, if the greatest common divisor of a and b is 1, then 1 is the last nonzero reminder resulted from Euclidean algorithm.

Note that the ultimate nonzero reminder has to be positive.

We’ve answered 318,917 questions. We can answer yours, too.

Ask a question