# Find the Greatest Common Factor of Two Numbers

Using Euclid's algorithm to find the greatest common factor and reduce a fraction to it's lowest terms.

### Euclidean Algorithm

Numerator n
Denominator n

#### Results:

 Greatest Common Factor # Reduced Fraction n d Simplefied n d
Starting number #
Small number #
step 1 #
step 2 #
step 3 #
step 4 #
step 5 #
step 6 #
step 7 #
step 8 #
step 9 #
step 10 #
step 11 #
step 12 #
step 13 #
step 14 #
step 15 #
step 16 #
step 17 #
step 18 #
step 19 #
step 20 #
step 21 #
step 22 #
step 23 #
step 24 #
step 25 #
step 26 #

#### Calculation

1. enter the numerator
2. enter the denominator

#### Results

1. greatest common factor of the two numbers
2. reduced fraction
3. the reduced fraction and simplified if the the reduced fraction is an improper fraction
4. the steps are the left over amounts for the steps
5. undefined steps are steps not used.

### Example One

Finding the greatest common factor of 91 and 315.

Start out with dividing the larger number by the smaller number to find out how many times the smaller number fits into the larger number.

315 / 91 = 3 -- 91 fits 3 times without going over

step one 315 = 91 * 3 + leftover of 42 ( 91 * 3 = 273 --- 315 - 273 = 42)

for step two the divider of step one (91) is divided by the leftover in step one (42).
91 / 42 = 2 -- 42 fits 2 times without going over
step two 91 = 42 * 2 + leftover of 7 ( 42 * 2 = 84 ----91 - 84 = 7)

for step three the divider of step two ( 42 ) is divided by the leftover of step two (7)

42/ 7 = 6 -- 7 fits fits 6 times without going over
step three 42 = 7 * 6 + leftover of 0

When there is no leftover you have found the greatest common factor of the two numbers. The leftover in the previous step is, 7 is the greatest common factor of 91 and 315.

Divide both the numerator and denominator by 7 and your fraction will be reduced to its lowest term

91/315 = 13/45

### Example Two

Find the greatest common factor of 455 and 8220

step one 8220 = 445 * 18 + 210
step two 445 = 210 * 2 + 25
step three 210 = 25 * 8 + 10
step four 25 = 10 * 2 + 5
step five 10 = 5 * 2 + 0

5 is the greatest common factor of 455 and 8220