According to the CSET Test Guide for Mathematics Subtest I, candidates must be able to “Apply the Euclidean Algorithm” (Number Theory, SMR 1.2). Euclid, a famous Greek mathematician, described the Euclidean Algorithm in his mathematical work Elements.
This algorithm is used to find the Greatest Common Factor (GCF) of two natural numbers by finding a second pair of smaller numbers that have the same GCF.
Get out some scratch paper and let us take a look at a possible CSET question.
A Possible CSET Question
Use the Euclidean Algorithm to find the GCF of (8702, 3534), then identify which of the following steps was NOT part of the Euclidean Algorithm.
- A) GCF (3534, 1634)
- B) 266 = 38 × 7
- C) GCF (1634, 266)
- D) 1634 = 2 × 19 × 43
- E) 3534 = 1634 × 2 + 266
- F) GCF (266, 38)
Work the problem on your own first, then open the solution below.
Show the notes and solution
Notes and Solution
The correct answer is (D).
The Euclidean Algorithm is a process used to find the Greatest Common Factor (GCF). Please note that the GCF may also be referred to as Greatest Common Divisor (GCD). The Euclidean Algorithm finds a second pair of smaller numbers that have the same GCF. The process is repeated until we are left with the GCF. To demonstrate, consider the following example in which the GCF is already known.
The GCF of (100, 15) is 5.
Notice that if we divide 100 by 15, we get 6 with a remainder of 10, that is, 100 = 15 × 6 + 10. Since 5, the GCF, is a factor of 100 and 15, it must also be a factor of 10 (the remainder of 100 divided by 15); therefore, the GCF of (100, 15) must also be the GCF of (15, 10). For clarity, the larger number will always be listed first when finding the GCF. Now, repeat the algorithm. Notice that 15 divided by 10 is 1 with a remainder of 5 (15 = 10 × 1 + 5); therefore, the GCF of (15, 10) must also be the GCF of (10, 5). Observe that 10 divided by 5 is 2 with no remainder; therefore, 5 is the GCF. Knowing that the GCF of (100, 15) is 5 made no difference in the computations or effectiveness of the Euclidean Algorithm.
Applying the Algorithm to (8702, 3534)
Now, back to the question: apply the Euclidean Algorithm to find the GCF of (8702, 3534).
Step 1) Find the remainder of 8702 ÷ 3534. Since 8702 = 3534 × 2 + 1634, the remainder is 1634. In other words, the GCF of (8702, 3534) is the same as the GCF of (3534, 1634).
Step 2) Repeat the algorithm, this time using (3534, 1634). Find the remainder of 3534 ÷ 1634. Since 3534 = 1634 × 2 + 266, the remainder is 266. That is, the GCF of (8702, 3534) is the same as the GCF of (3534, 1634), which is the same as the GCF of (1634, 266).
Step 3) Repeat the algorithm, this time using (1634, 266). Since 1634 = 266 × 6 + 38, the remainder is 38. The GCF of the original question (8702, 3534) is the same as the GCF of (266, 38).
Step 4) Repeat, this time using (266, 38). Since 266 = 38 × 7 with a remainder of zero (no remainder), the GCF is 38. The GCF of (8702, 3534) is 38.
The GCF can be verified by examining the common prime factors of 8702 and 3534. Since 8702 = 2 × 19 × 229 and 3534 = 2 × 3 × 19 × 31, the common prime factors are 2 and 19, so the GCF is 2 × 19 = 38.
Now Look Back and Answer the Question
Use the Euclidean Algorithm to find the GCF of (8702, 3534), then identify which of the following steps was NOT part of the Euclidean Algorithm.
| Choice | Where it appears |
|---|---|
| A) GCF (3534, 1634) | Used at the end of step one |
| B) 266 = 38 × 7 | Used at the start of step four |
| C) GCF (1634, 266) | Used at the end of step two |
| D) 1634 = 2 × 19 × 43 | True, but not part of the Euclidean Algorithm |
| E) 3534 = 1634 × 2 + 266 | Used at the beginning of step two |
| F) GCF (266, 38) | Used at the end of step three |
For Fun: I Asked ChatGPT
For fun, on September 25, 2025, I posed the following problem to ChatGPT.
“Use the Euclidean Algorithm to find the GCD of 2592 and 320”
Use your scratch paper and work this problem on your own, and then compare your results with ChatGPT’s.
Here is the result from ChatGPT:
The Euclidean Algorithm works by repeatedly applying the formula:
GCD(a,b) = GCD(b, a mod b)
Where a > b. We repeat the process until the remainder is 0.
Start with a = 2592, b = 320
Step 1:
2592 ÷ 320 = 8 remainder 192
2592 = 8 × 320 + 192
GCD(2592, 320) = GCD (320, 192)
Step 2:
320 ÷ 192 = 1 remainder 128
320 = 1 × 192 + 128
GCD(320, 192) = GCD (192, 128)
Step 3:
192 ÷ 128 = 1 remainder 64
192 = 1 × 128 + 64
GCD(192, 128) = GCD (128, 64)
Step 4:
128 ÷ 64 = 2 remainder 0
128 = 2 × 64 + 0
We stop here
Did you find the error?
The actual GCD (2592, 320) = 32.
ChatGPT produced four tidy steps, clean formatting, and a confident final answer — and it was wrong from the very first line. That is what makes studying with AI risky: the work looks correct, so nothing warns you that it isn’t. Passing the CSET means being able to check the work yourself, and that is exactly what these workbooks train you to do — every solution is worked in full, so you learn why each step follows rather than just what the answer is.
Your Next Step: CSET Math Workbooks
I hope you enjoyed this mini-lesson on the Euclidean Algorithm. This question is similar to problem number 33 from our popular book CSETMath—Subtest I (Test Code 211) Practice Exam.
We at CSETMath would like to thank you for your interest in CSETMath workbooks. This question about the Euclidean Algorithm is designed to give you an overview of what you will find in the full version of each CSETMath workbook.
There are three Constructed Response workbooks available:
- CSETMath—Subtest I (Test Code 211) Constructed Response
Number and Quantity; Algebra - CSETMath—Subtest II (Test Code 212) Constructed Response
Geometry; Probability and Statistics - CSETMath—Subtest III (Test Code 213) Constructed Response
Calculus
There are two Practice Exam workbooks available:
- CSETMath—Subtest I (Test Code 211) Practice Exam
Number and Quantity; Algebra - CSETMath—Subtest II (Test Code 212) Practice Exam
Geometry; Probability and Statistics
The Constructed Response workbooks contain 20 constructed response questions. Each Practice Exam workbook contains a complete practice exam composed of 35 multiple-choice questions and three constructed-response questions. All of these workbooks contain detailed solutions designed to prepare you to pass the CSET Mathematics Exam. By completing one of the books, you will familiarize yourself with the Subject Matter Requirements in the depth needed to pass the CSET successfully.
