// NUMBER THEORY · INTERMEDIATE

GCD & Euclidean Algorithm

Discover the ancient algorithm that finds the greatest common divisor in seconds, and unlock the Extended GCD for cryptography and Diophantine equations.

Start Visualizing Play Euclidean Racer
Intermediate·18 min·Mathematics · Number Theory
Reviewed by CodeTikki Academic Team

Prerequisites: Basic division · Remainders · Prime numbers (optional)

// VISUALIZER

Watch remainders shrink the problem

The Euclidean algorithm is based on one powerful fact: GCD(a, b) = GCD(b, a mod b). Change a and b, press play, and see how each remainder becomes the new problem.

step 112
step 26
step 30
step 40

Press PLAY to watch the Euclidean algorithm step by step.

Current a

48

Current b

18

Remainder

?

Steps

0 / 4

// MINI GAME

Euclidean Racer

Beat the clock! Predict the remainder at each step of the Euclidean algorithm. Correct answers build your streak and score.

Loading race track...

// FLOWCHART

Algorithm flow

// FLOWCHART · Euclidean Algorithm
GCD(a, b)
NoYesStartRead a, bb == 0?r = a mod ba = b; b = rOutput aEnd

Press PLAY to trace the algorithm through the flowchart.

0 / 9

// PSEUDOCODE

Trace the code

// PSEUDOCODE · Euclidean Algorithm
Iterative version with input a = 48, b = 18
a = 48, b = 18
1function gcd(a, b):
2 while b != 0:
3 r = a mod b
4 a = b
5 b = r
6 return a

Press PLAY to step through the algorithm line by line.

0 / 15

// TUTORIAL QUIZZES

Test your mastery

Progress from the basics of GCD to the Extended Euclidean Algorithm. Each quiz has 10 questions and awards XP.

// PRACTICE & ASSESS

Test your understanding

Now that you've learned the concept, put it into practice. Solve coding problems and take quizzes to reinforce what you've learned.

💻

Coding Problems

The Common Divisor: Find GCD of Two NumbersL1The Simplifier: Reduce a Fraction to Lowest TermsL2The Inverse Hunter: Modular Multiplicative InverseL5The Diophantine Apprentice: Solve ax + by = cL6The Coprime Detective: Check if Two Numbers are CoprimeL3

// REFERENCES

Sources & further reading

  1. [1]
    Euclid's Elements, Book VIIEuclid of Alexandria — Propositions 1–2 describe the algorithm
  2. [2]
    Introduction to Algorithms (CLRS)T. H. Cormen et al. — Number-theoretic algorithms and GCD
  3. [3]
    The Art of Computer Programming, Vol. 2Donald Knuth — Seminumerical Algorithms, Section 4.5.2
  4. [4]
    A Course in Number Theory and CryptographyNeal Koblitz — GCD and modular inverses

// READY?

Master the next number-theory skill

Now that you understand GCD, explore the Sieve of Eratosthenes, Prime Factorization, or the Chinese Remainder Theorem.

Sieve of Eratosthenes Prime Factorization