Academic managers online nowFree quote in 3 minutes. Assignments from $19.Submit assignment →
LegitAssignmentHelp.comSubmit assignment
Free, no account, nothing storedThe arithmetic runs in your browser. Nothing you type is sent to us.All 100 calculators →

Mathematics · pattern A, Numeric fields

Greatest common factor by Euclid's algorithm.

Enter two numbers for their greatest common factor, with each division step of Euclid's algorithm written out and the LCM alongside.

Inputs

The formula used

replace (a, b) with (b, a mod b) until b is zero

Euclid's algorithm is over two thousand years old and still the fastest general method. It needs only division with remainder.

GCF

21

For 252 and 105: GCF 21, LCM 1260.

Prime factors of 252
2 × 2 × 3 × 3 × 7
Prime factors of 105
3 × 5 × 7
GCF
21
LCM
1260
Coprime?
no

Worked steps

  1. 1252 = 2 × 105 + 42

    Euclid’s algorithm: replace the pair with (divisor, remainder)

  2. 2105 = 2 × 42 + 21

    Euclid’s algorithm: replace the pair with (divisor, remainder)

  3. 342 = 2 × 21 + 0

    Euclid’s algorithm: replace the pair with (divisor, remainder)

  4. 4GCF = 21

    the last non-zero remainder is the greatest common factor

The oldest algorithm still in daily use.

Each step replaces the pair with the divisor and the remainder, and the process terminates in a number of steps proportional to the digit count. Nothing faster is known for general integers, which is why it appears in every computer algebra system and in RSA key generation.

Questions about gcf

What does coprime mean?
That the GCF is 1. The numbers need not be prime themselves — 8 and 15 are coprime.
Why is the GCF useful?
Simplifying fractions to lowest terms, and factorising expressions by extracting the common factor.
Does it work for more than two numbers?
Yes, pairwise: GCF(a, b, c) = GCF(GCF(a, b), c).

More in Mathematics

23 tools in this topic, all free and all running in your browser.

All Mathematics tools

A calculator handles the arithmetic. It cannot teach you the method.

If the number is not the part you are stuck on, that is what the service is for — a specialist who explains the working, not just the answer.

Submit an assignmentSee what it costs

Arithmetic runs in double-precision floating point, so results beyond about fifteen significant figures are not exact. Where a question wants an exact fraction or surd, keep the exact form rather than a decimal.