+9491 https://en.wikipedia.org/wiki/Euclidean_algorithm
Examples:
The greatest common divisor of 6 and 9
= gcd(6, 9) ←The difference between 6 and 9 is 3, so replace the larger number, 9, with 3.
= gcd(6, 3) ←The difference between 6 and 3 is 3, so replace the larger number, 6, with 3.
= gcd(3, 3) ←Now the two numbers are the same. So we stop.
= 3
The greatest common divisor of 8 and 12
= gcd(8, 12)
= gcd(8, 4)
= gcd(4, 4)
= 4
The greatest common divisor of 24 and 81
= gcd(24, 81)
= gcd(24, 57)
= gcd(24, 33)
= gcd(24, 9)
= gcd(15, 9)
= gcd(6, 9)
= gcd(6, 3)
= gcd(3, 3)
= 3
To calculate the greatest common divisor of 3 different numbers, we can use this prinicple:
gcd(a, b, c) = gcd( a, gcd(b, c) )
So we apply the Euclidean algorithm twice. Let's see if this works!
gcd(9118, 12173, 33182) = gcd( 9118, gcd(12173, 33182) )
First, use the Euclidean algorithm to find the inner piece.
= gcd(12173, 33182)
= gcd(12173, 21009)
= gcd(12173, 8836)
= gcd(3337, 8836)
= gcd(3337, 5499)
= gcd(3337, 2162)
= gcd(1175, 2162)
= gcd(1175, 987)
= gcd(188, 987)
= gcd(188, 799)
= gcd(188, 611)
= gcd(188, 423)
= gcd(188, 235)
= gcd(188, 47)
= gcd(141, 47)
= gcd(94, 47)
= gcd(47, 47)
= 47
Next, use the Euclidean algorithm to find the outer piece.
gcd( 9118, gcd(12173, 33182) )
= gcd(9118, 47)
= gcd(9071, 47)
= gcd(9024, 47)
.
. *Note that 9118 - 47*193 = 47 so we would have to subtract 47 a total of 193 times.*
.
= gcd(141, 47)
= gcd(94, 47)
= gcd(47, 47)
= 47
This agrees with Melody's answer!!
