WOLFRAM|DEMONSTRATIONS PROJECT

Euclidean Algorithm Steps

​
p, q
gcd(10946,6765)1
10946
==
1
×
6765
+
4181
6765
==
1
×
4181
+
2584
4181
==
1
×
2584
+
1597
2584
==
1
×
1597
+
987
1597
==
1
×
987
+
610
987
==
1
×
610
+
377
610
==
1
×
377
+
233
377
==
1
×
233
+
144
233
==
1
×
144
+
89
144
==
1
×
89
+
55
89
==
1
×
55
+
34
55
==
1
×
34
+
21
34
==
1
×
21
+
13
21
==
1
×
13
+
8
13
==
1
×
8
+
5
8
==
1
×
5
+
3
5
==
1
×
3
+
2
3
==
1
×
2
+
1
The steps in the Euclidean algorithm, which calculates the greatest common divisor of two positive integers. The red bars indicate the fraction of the remainder to the divisor.