(JavaScript integers have a size limit of 15 digits)
| First number: | ||
| Second number: | ||
| Largest common divisor: |
The algorithm runs as follows: The lesser of the two numbers is identified and the remainder from
division of this into the larger number is calculated. The remainder is now considered the new lesser
number compared to the former lesser number and the operation is repeated. This is continued until
the remainder becomes zero, the divisor now being the largest common divisor.
Taking the numbers 43273 and 181826 for example:
| 181826/43273 | gives remainder 8734 |
| 43273/8734 | gives remainder 8337 |
| 8734/8337 | gives remainder 397 |
| 8337/397 | gives remainder 0 |
Therefore 397 is their largest common divisor, and the fraction 43273/181826 may be reduced
to (43273/397)/(181826/397) = 109/458.
p.s.
Algorithms are on everyone's lips nowadays. Euclid proved this one more than two thousand years ago.