Calculator

Result 0

Here is a sheet that goes further in depth on methods, and how the Algorithm works.

Euclidean Algorithm Sheet from rit.edu

Ways to find GCF

  • Inspection - Solving a problem by looking at it and using logic, patterns, or quick mental math to see the answer, rather than a complex formula or step-by-step algorithm.
  • Factorization
    • List the factors for the first number. Ex:42:1,2,3,6,7,14,21,42
    • List the factors for the second number. Ex:28:1,2,4,7,14,28
    • Choose the largest number they share, 14.
  • Euclidean Algorithm
    1. Start with two numbers, a (larger) and b (smaller).
    2. Divide a by b to get a quotient and a remainder r.
    3. Write it as a=bq+r.
    4. If the remainder r is 0, then b is the GCF.
    5. If r is not 0, replace a with b, and replace b with r.
    6. Repeat steps 2-5 until the remainder is zero.
    7. The GCF is the the last non-zero remainder.