Skip to main content
MathidiaMathematics Academy
Number theory and cryptography
Lesson 47 of 75
Easy practice

Euclidean algorithms

Objective. Find gcds and modular inverses.

  1. 1. Learn
  2. 2. Worked example
  3. 3. Practice
  4. 4. Feedback
  5. 5. Continue

Learn: the key idea

Euclidean algorithms compute the greatest common divisor of two integers by repeated division with remainder, replacing the pair (a,b) with (b, a mod b) until the remainder is zero. The extended Euclidean algorithm tracks coefficients through this process to express gcd(a,b) as an integer combination xa + yb, which directly yields modular inverses when gcd(a,n) = 1. For example, applying the algorithm to 252 and 105 gives 252 = 2×105 + 42, 105 = 2×42 + 21, 42 = 2×21 + 0, so gcd(252,105) = 21.

Worked example

Use the Euclidean algorithm to find gcd(84, 30).

84 … 30
Illustrated card showing 84 … 30
  1. 184 = 2×30 + 24
  2. 230 = 1×24 + 6
  3. 324 = 4×6 + 0
  4. 4Last nonzero remainder: gcd = 6

Answer: 6

Concept mastery

Based on your past attempts at this lesson — the question types to practise again come first.

Complete a practice set to see your concept breakdown here.

Practice

Practice happens on its own screen, one question at a time. Answers stay hidden until you submit yours, and you can stop and pick up at the same question later.

Start practising

Common mistake. Students stop the Euclidean algorithm too early, reporting the last nonzero divisor used rather than the actual remainder that first reaches zero's divisor; always continue until the remainder is exactly zero before reading off the gcd.

Your progress

Tick each step as you finish it. Your exact reading position is saved automatically, so Continue drops you back on the same line.

0 of 5 steps complete

Your place saves automatically as you read.

My dashboard