Euclidean Algorithm Calculator

How to Calculate the Greatest Common Factor Using the Euclidean Algorithm

The Euclidean algorithm is an efficient method for computing the greatest common factor (GCF) of two numbers. It's based on the principle that the greatest common factor of two numbers is also the greatest common factor of the smaller number and the remainder of the larger number divided by the smaller number.

Formula

The Euclidean algorithm can be expressed as:

\[ GCF(a,b) = GCF(b, a \bmod b) \]

Where:

• a and b are the two numbers
• a mod b represents the remainder when a is divided by b

Calculation Steps

1. Start with two positive integers, a and b.
2. Divide a by b and find the remainder.
3. If the remainder is 0, b is the GCF.
4. If not, replace a with b and b with the remainder.
5. Repeat steps 2-4 until the remainder is 0.

Example

Let's find the GCF of 48 and 18 using the Euclidean algorithm:

1. \[ 48 = 18 \times 2 + 12 \] Remainder is 12, so continue.
2. \[ 18 = 12 \times 1 + 6 \] Remainder is 6, so continue.
3. \[ 12 = 6 \times 2 + 0 \] Remainder is 0, so stop.

The last non-zero remainder is 6, so the GCF of 48 and 18 is 6.

Visual Representation

This diagram illustrates the steps of the Euclidean algorithm for finding the GCF of 48 and 18.