Solve any maths problem

Equations, derivatives, integrals, matrices, triangles, primes, statistics, or a word problem the tutor breaks into parts.

Number-Theory · Gcd-And-Lcm

Gcd(21, 34)

21,\ 34

Step by step

  1. \gcd(21, 34)

    Use Euclid's algorithm: replace the larger number by its remainder on division by the smaller, until the remainder is 0.

  2. 34 = 1 \times 21 + 13

    Divide 34 by 21: quotient 1, remainder 13.

  3. 21 = 1 \times 13 + 8

    Divide 21 by 13: quotient 1, remainder 8.

  4. 13 = 1 \times 8 + 5

    Divide 13 by 8: quotient 1, remainder 5.

  5. 8 = 1 \times 5 + 3

    Divide 8 by 5: quotient 1, remainder 3.

  6. 5 = 1 \times 3 + 2

    Divide 5 by 3: quotient 1, remainder 2.

  7. 3 = 1 \times 2 + 1

    Divide 3 by 2: quotient 1, remainder 1.

  8. 2 = 2 \times 1 + 0

    Divide 2 by 1: quotient 2, remainder 0.

  9. \gcd(21, 34) = 1

    The last non-zero remainder is 1.

Reveal the answer
\gcd(21, 34) = 1