Euclidean Algorithm Basics

  • 9th Grade
Reviewed by Editorial Team
The ProProfs editorial team is comprised of experienced subject matter experts. They've collectively created over 10,000 quizzes and lessons, serving over 100 million users. Our team includes in-house content moderators and subject matter experts, as well as a global network of rigorously trained contributors. All adhere to our comprehensive editorial guidelines, ensuring the delivery of high-quality content.
Learn about Our Editorial Process
| By Thames
T
Thames
Community Contributor
Quizzes Created: 7387 | Total Attempts: 9,527,791
| Attempts: 11 | Questions: 12 | Updated: Nov 7, 2025
Please wait...
Question 1 / 12
0 %
0/100
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
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
Alert!

Advertisement