What is the Euclidean Algorithm?
The Euclidean Algorithm is a method that is commonly used to find the Greatest Common Divisor of two whole numbers.
If you search the internet for a description of this method, you will most likely find one that involves several steps, each one involving a division to produce a quotient and remainder. Specifically, this method can be described as follows:
Step 1: Suppose you have two positive integers and you want to find the Greatest Common Divisor of both of them. Then, let the larger one be the Dividend, let the smaller one be the Divisor, and then divide the Dividend by the Divisor to give you a Quotient and a Remainder.
Step 2: For this step, let the new Dividend be the Divisor from Step 1, and let the new Divisor be the Remainder from Step 1. Now, divide the new Dividend by the new Divisor to get a new Quotient and a new Remainder.
Step 3: For this step, let the new Dividend be the Divisor from Step 2, and let the new Divisor be the Remainder from Step 2. Now, divide the new Dividend by the new Divisor to get a new Quotient and a new Remainder.
Step 4: For this step, let the new Dividend be the Divisor from Step 3, and let the new Divisor be the Remainder from Step 3. Now, divide the new Dividend by the new Divisor to get a new Quotient and a new Remainder.
Continue these steps, until you get to the last step in which your Remainder is 0. Then, the Divisor you used in this last step will be your Greatest Common Divisor.
For example, here are the steps you would use to find the Greatest Common Divisor of 32 and 84.
84 ÷ 32 = 2 with remainder 20
32 ÷ 20 = 1 with remainder 12
20 ÷ 12 = 1 with remainder 8
12 ÷ 8 = 1 with remainder 4
8 ÷ 4 = 2 with remainder 0
Therefore, the Greatest Common Divisor of 32 and 84 is 4.
There is an alternate form of the Euclidean Algorithm that works equally well but uses only subtractions instead of divisions. A flow chart explaining this algorithm appears on the top right of the Wikipedia page for Algorithm. Specifically, this method can be described as follows:
Step 1: Suppose you have two positive integers and you want to find the Greatest Common Divisor of both of them. Then, let the larger one be the Minuend, let the smaller one be the Subtrahend, and then subtract the Subtrahend from the Minuend to get the Difference.
Step 2: Discard the Minuend from Step 1, and of the two remaining smaller numbers (the Subtrahend and Difference) let the larger one be the new Minuend and the smaller one be the new Subtrahend. Subtract the Subtrahend from the Minuend to get the Difference.
Step 3: Discard the Minuend from Step 2, and of the two remaining smaller numbers (the Subtrahend and Difference) let the larger one be the new Minuend and the smaller one be the new Subtrahend. Subtract the Subtrahend from the Minuend to get the Difference.
Step 4: Discard the Minuend from Step 3, and of the two remaining smaller numbers (the Subtrahend and Difference) let the larger one be the new Minuend and the smaller one be the new Subtrahend. Subtract the Subtrahend from the Minuend to get the Difference.
Continue these steps, until you get to the last step in which your Difference is 0. Then, the Subtrahend you used in this last step will be your Greatest Common Divisor.
For example, here are the steps you would use to find the Greatest Common Divisor of 32 and 84.
84 - 32 = 52
52 - 32 = 20
32 - 20 = 12
20 - 12 = 8
12 - 8 = 4
8 - 4 = 4
4 - 4 = 0
Therefore, the Greatest Common Divisor of 32 and 84 is 4.
It is this alternate form of the Euclidean Algorithm that is actually used by the Turing Machine EUC described by Sir Roger Penrose in his book The Emperor's New Mind (Oxford University Press, 1989), and which is also included as a sample Turing Machine in both of the Excel files that you can download from the Home page of this website.
It is also this alternate form of the Euclidean Algorithm that first appeared in Euclid's Elements around 300 BC, although the method itself may have been used by mathematicians for thousands of years before that.
Step 2: For this step, let the new Dividend be the Divisor from Step 1, and let the new Divisor be the Remainder from Step 1. Now, divide the new Dividend by the new Divisor to get a new Quotient and a new Remainder.
Step 3: For this step, let the new Dividend be the Divisor from Step 2, and let the new Divisor be the Remainder from Step 2. Now, divide the new Dividend by the new Divisor to get a new Quotient and a new Remainder.
Step 4: For this step, let the new Dividend be the Divisor from Step 3, and let the new Divisor be the Remainder from Step 3. Now, divide the new Dividend by the new Divisor to get a new Quotient and a new Remainder.
Continue these steps, until you get to the last step in which your Remainder is 0. Then, the Divisor you used in this last step will be your Greatest Common Divisor.
32 ÷ 20 = 1 with remainder 12
20 ÷ 12 = 1 with remainder 8
12 ÷ 8 = 1 with remainder 4
8 ÷ 4 = 2 with remainder 0
Therefore, the Greatest Common Divisor of 32 and 84 is 4.
Step 2: Discard the Minuend from Step 1, and of the two remaining smaller numbers (the Subtrahend and Difference) let the larger one be the new Minuend and the smaller one be the new Subtrahend. Subtract the Subtrahend from the Minuend to get the Difference.
Step 3: Discard the Minuend from Step 2, and of the two remaining smaller numbers (the Subtrahend and Difference) let the larger one be the new Minuend and the smaller one be the new Subtrahend. Subtract the Subtrahend from the Minuend to get the Difference.
Step 4: Discard the Minuend from Step 3, and of the two remaining smaller numbers (the Subtrahend and Difference) let the larger one be the new Minuend and the smaller one be the new Subtrahend. Subtract the Subtrahend from the Minuend to get the Difference.
Continue these steps, until you get to the last step in which your Difference is 0. Then, the Subtrahend you used in this last step will be your Greatest Common Divisor.
52 - 32 = 20
32 - 20 = 12
20 - 12 = 8
12 - 8 = 4
8 - 4 = 4
4 - 4 = 0
Therefore, the Greatest Common Divisor of 32 and 84 is 4.
Version 1.0 -- April 23, 2017