1 Answer | Add Yours
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