Euclidean Algorithm Basics

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: 7049 | Total Attempts: 9,519,298
| Questions: 12
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)
We’ll put your name on your report, certificate, and leaderboard.
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 1 of GCD(101, 23): 101 ÷ 23 leaves remainder

Explanation

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

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

Explanation

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

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

Explanation

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

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

Explanation

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

Submit
12) The GCD of 101 and 23 is

Explanation

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

Submit
View My Results

Quiz Review Timeline (Updated): Oct 12, 2025 +

Our quizzes are rigorously reviewed, monitored and continuously updated by our expert board to maintain accuracy, relevance, and timeliness.

  • Current Version
  • Oct 12, 2025
    Quiz Edited by
    ProProfs Editorial Team
  • Oct 03, 2025
    Quiz Created by
    Thames
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 1 of GCD(101, 23): 101 ÷ 23 leaves remainder
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
The GCD of 101 and 23 is
Alert!

Back to Top Back to top
Advertisement