The gcd(259, 621) = 1 and gcd(108, 156) = 12
Step-by-step explanation:
The Euclidean algorithm solves the problem:
Given integers a, b, find d = gcd(a,b)
These are the steps of the Euclidean algorithm:
Let a = x, b = y.Given x, y use the division algorithm to write
where q is quotient and r is the remainderIf r = 0, stop and output y; this is the gcd of a, b.if r ≠ 0, replace (x, y) by (y,r). Go to step 2.
These are the steps for the division algorithm:
Subtract the divisor from the dividend repeatedly until we get a result that lies between 0 and the divisorThe resulting number is known as the remainder, and the number of times that the divisor is subtracted is called the quotient.
To find the greatest common divisor of 621 and 259 by the Euclidean algorithm you need to:
Divide 621 by 259, applying the division algorithm you get
next you need to write the expression
Divide 259 by 103 to write
Divide 103 by 53 to write
Divide 53 by 50 to write
Divide 50 by 3 to write
Divide 3 by 2 to write
Divide 2 by 1 to write
The greatest common divisor of 621 and 259 is 1
To find the greatest common divisor of 156 and 108 by the Euclidean algorithm you need to:
Divide 156 by 108 to write
Divide 108 by 48 to write
Divide 48 by 12 to write
The greatest common divisor of 156 and 108 is 12