Euclid's Algorithm Calculator

Enter values
Last update: 2024-06-18
0/0
Result:
21
Formula
G C D ( a , b ) = { G C D ( b , a mod ( b ) ) , if b 0 , if b = 0 }
Solution steps
1.
Calculate the modulo using the Modulo Calculator
1.
Calculate the modulo
mod(1071,462)
mod(1071,462)
= 147
2.
1071 = 2 * 462 + 147
= Remainder 147
3.
147 > 0. Repeat calculation
1.
Calculate the modulo
mod(462,147)
mod(462,147)
= 21
4.
462 = 3 * 147 + 21
= Remainder 21
5.
21 > 0. Repeat calculation
1.
Calculate the modulo
mod(147,21)
mod(147,21)
= 0
6.
147 = 7 * 21 + 0
= Remainder 0
7.
Mod = 0
= 21
Rating: 0
Votes: 0