Description: Finding greatest common divisors -
This computes the greatest common divisor of two given integers via the Euclidean Algorithm, showing all the steps. The greatest common divisor is explicitly noted at the bottom. first=7654321 second=56789
7654321-(134)*56789=44595
56789-(1)*(44595)=12194
44595-(3)*(12194)=8013
12194-(1)*(8013)=4181
...............................
..............................
.............................
7-(1)*(6)=1
6-(6)*(1)=0
so the gcd of 7654321 and 56789 is 1.
Reference:
www.math.umn.edu/garrett/crypto/a01/euclid.html
|