This Java Script calculator uses Euclid's algorithm to find the greatest common divisor of two integers. To operate the calculator, enter the numerator and denominator. Press the Compute button to obtain the solution. The test button loads an example to demonstrate how the calculator works. On invalid entries, a popup window will display an error message.
Return to Contents
The Java Script source code for this program can be viewed by using the View|Source command of your web browser.
You may use or modify this source code in any way you find useful, provided that you agree that the author has no warranty, obligations or liability. You must determine the suitability of this source code for your use.
Return to Contents
Euclid's algorithm determines the greatest common divisor of two integers. It appeared in Euclid's Elements around 300 BC. The algorithm is as follows. Given two natural numbers (integers greater than zero) a and b, calculate t, the remainder after division of a by b. Replace a with b, b with t; repeat until t equals zero.
To be more precise, we can write the operation:
in a different form:a --- = n, remainder t b
a = b*n + t
For example, given a = 2232 and b = 327 :
Then, the greatest common divisor of 2232 and 327 is 3.a b*n t ------------------ 2232 = 327*6 + 270 (i.e., 2232/327 = 6 with remainder 270) 327 = 270*1 + 57 270 = 57*4 + 42 57 = 42*1 + 15 42 = 15*2 + 12 15 = 12*1 + 3 12 = 3*4 + 0
References
Clark University : Euclid's Elements
Return to Contents