Euclidean Algorithm Basics

  • 9th Grade
Reviewed by Cierra Henderson
Cierra Henderson, MBA |
K-12 Expert
Review Board Member
Cierra is an educational consultant and curriculum developer who has worked with students in K-12 for a variety of subjects including English and Math as well as test prep. She specializes in one-on-one support for students especially those with learning differences. She holds an MBA from the University of Massachusetts Amherst and a certificate in educational consulting from UC Irvine.
 , MBA
By Thames
T
Thames
Community Contributor
Quizzes Created: 8157 | Total Attempts: 9,569,759
| Attempts: 11 | Questions: 12 | Updated: Jan 19, 2026
Please wait...
Question 1 / 13
🏆 Rank #-- ▾
Score 0/100
1) Find GCD(48, 18) using the Euclidean Algorithm.

Explanation

Use Euclid:

48 = 18·2 + 12 → 18 = 12·1 + 6 → 12 = 6·2 + 0.

Once the remainder hits 0, the previous remainder is the GCD → 6.

Submit
Please wait...
About This Quiz
Euclidean Algorithm Basics - Quiz

Ever wondered how to quickly find the greatest common divisor (GCD) of two numbers? The Euclidean Algorithm is the oldest (and still one of the fastest!) ways to do it. In this quiz, you’ll practice step-by-step division, track remainders, and see how the process always leads to the GCD. Take... see morethis quiz to master the basics of this powerful number tool.
see less

2)
You may optionally provide this to label your report, leaderboard, or certificate.
2) Step 1 of GCD(252, 105): 252 ÷ 105 leaves remainder

Explanation

Divide 252 by 105: 105·2 = 210; remainder = 252 − 210 = 42.

Submit
3) Step 2 of GCD(252, 105): 105 ÷ 42 leaves remainder

Explanation

Now divide 105 by the last remainder 42: 42·2 = 84; remainder = 105 − 84 = 21.

Submit
4) The GCD of 252 and 105 is

Explanation

Next step: 42 ÷ 21 = 2 with remainder 0, so the GCD is the last nonzero remainder → 21.

Submit
5) Step 1 of GCD(84, 18): 84 ÷ 18 leaves remainder

Explanation

84 ÷ 18: 18·4 = 72; remainder = 84 − 72 = 12.

Submit
6) Step 2 of GCD(84, 18): 18 ÷ 12 leaves remainder

Explanation

18 ÷ 12: remainder = 6 (since 12·1 = 12; 18 − 12 = 6).

Submit
7) The GCD of 84 and 18 is

Explanation

12 ÷ 6 leaves remainder 0, so the GCD is 6.

Submit
8) Step 2 of GCD(101, 23): 23 ÷ 9 leaves remainder

Explanation

23 ÷ 9: 9·2 = 18; remainder = 5.

Submit
9) Step 3 of GCD(101, 23): 9 ÷ 5 leaves remainder

Explanation

9 ÷ 5: 5·1 = 5; remainder = 4.

Submit
10) Step 4 of GCD(101, 23): 5 ÷ 4 leaves remainder

Explanation

5 ÷ 4: 4·1 = 4; remainder = 1.

Submit
11) Step 1 of GCD(101, 23): 101 ÷ 23 leaves remainder

Explanation

23·4 = 92; remainder = 101 − 92 = 9.

Submit
12) The GCD of 101 and 23 is

Explanation

4 ÷ 1 gives remainder 0, so the GCD is 1 (they’re coprime).

Submit
×
Saved
Thank you for your feedback!
View My Results
Cierra Henderson |MBA |
K-12 Expert
Cierra is an educational consultant and curriculum developer who has worked with students in K-12 for a variety of subjects including English and Math as well as test prep. She specializes in one-on-one support for students especially those with learning differences. She holds an MBA from the University of Massachusetts Amherst and a certificate in educational consulting from UC Irvine.
Cancel
  • All
    All (12)
  • Unanswered
    Unanswered ()
  • Answered
    Answered ()
Find GCD(48, 18) using the Euclidean Algorithm.
Step 1 of GCD(252, 105): 252 ÷ 105 leaves remainder
Step 2 of GCD(252, 105): 105 ÷ 42 leaves remainder
The GCD of 252 and 105 is
Step 1 of GCD(84, 18): 84 ÷ 18 leaves remainder
Step 2 of GCD(84, 18): 18 ÷ 12 leaves remainder
The GCD of 84 and 18 is
Step 2 of GCD(101, 23): 23 ÷ 9 leaves remainder
Step 3 of GCD(101, 23): 9 ÷ 5 leaves remainder
Step 4 of GCD(101, 23): 5 ÷ 4 leaves remainder
Step 1 of GCD(101, 23): 101 ÷ 23 leaves remainder
The GCD of 101 and 23 is
play-Mute sad happy unanswered_answer up-hover down-hover success oval cancel Check box square blue
Alert!