Difference between revisions of "Euclidean algorithm"
Jump to navigation
Jump to search
(creating page from red link) |
(wikify algorithm) |
||
| Line 2: | Line 2: | ||
==The Algorithm== | ==The Algorithm== | ||
| − | The algorithm is beautiful in its simplicity. For any two numbers, one simply subtracts the smaller number from the larger; if the numbers are equal, or if one number reaches zero, the equal numbers or the remaining number is the GCD. For example, if one starts with 24 and 60, one subtracts the smaller from the larger to get 24 and 36. The process is repeated until at least one number is zero: 24,60 becomes 24,36, which becomes 24,12, which becomes 12,12, so 12 is the GCD of 24 and 60. | + | The [[algorithm]] is beautiful in its simplicity. For any two numbers, one simply subtracts the smaller number from the larger; if the numbers are equal, or if one number reaches zero, the equal numbers or the remaining number is the GCD. For example, if one starts with 24 and 60, one subtracts the smaller from the larger to get 24 and 36. The process is repeated until at least one number is zero: 24,60 becomes 24,36, which becomes 24,12, which becomes 12,12, so 12 is the GCD of 24 and 60. |
==History== | ==History== | ||
''Section in progress.'' | ''Section in progress.'' | ||
Revision as of 06:02, May 18, 2010
The Euclidean algorithm is a method for determining the greatest common divisor of two numbers.
The Algorithm
The algorithm is beautiful in its simplicity. For any two numbers, one simply subtracts the smaller number from the larger; if the numbers are equal, or if one number reaches zero, the equal numbers or the remaining number is the GCD. For example, if one starts with 24 and 60, one subtracts the smaller from the larger to get 24 and 36. The process is repeated until at least one number is zero: 24,60 becomes 24,36, which becomes 24,12, which becomes 12,12, so 12 is the GCD of 24 and 60.
History
Section in progress.