Euclidean algorithm - Revision history

Taj: adding category to uncategorized page

2011-09-14T23:50:25Z

adding category to uncategorized page

FrankC: /* The Algorithm */ why it works...

2010-05-18T13:03:25Z

The Algorithm: why it works...

Aschlafly: wikify algorithm

2010-05-18T06:02:54Z

wikify algorithm

JacobB: creating page from red link

2010-05-18T04:51:37Z

creating page from red link

New page

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.''

← Older revision		Revision as of 23:50, September 14, 2011
Line 6:		Line 6:
	==History==		==History==
	''Section in progress.''		''Section in progress.''
		+
		+
		+	[[Category:Mathematics]]

@@ Line 2: / Line 2: @@
 ==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. It just uses a basic property of [[natural number]]s: if a number divides two integers, it divides their difference, too. So, 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.''