Short division
Best for several medium-sized numbers. Repeatedly divide a whole row or a useful subset by a shared prime.
Tracks GCD and LCM in one ladder.
Use Short Division and the Euclidean Algorithm
用短除法和辗转相除法求最大公约数与最小公倍数
Remove shared prime factors in a short-division ladder, learn the different stopping rules for GCD and LCM, and use repeated remainders to find a two-number GCD efficiently.
Short division removes shared factors. Euclid replaces a pair by a smaller remainder pair.
Answers autosave in this browser.
Mission 1
Not completeChoose the method that matches the numbers
The chapter names several ways to find common factors and common multiples. The best method depends on what information is already visible.
Euclidean algorithm
Best for two numbers when factorization would be slow. Replace the larger number by the remainder.
When a division has remainder zero, its divisor is the GCD.
Prime exponents
Best when the standard prime factorizations are already known or easy to build.
Use minimum exponents for GCD and maximum exponents for LCM.
Choose the method recommended by the descriptions above
Other methods can also work. This checkpoint asks which method uses the supplied information most directly.
Need a hint? Start here
Choose a method based on the information already visible.
Check why it works
Euclid avoids factoring a pair; short division organizes several numbers; aligned exponents can be read directly. Euclidean algorithm; short division; prime exponents. These recommendations do not mean the other methods are mathematically invalid.
Mission 2
Not completeUse the worked example short-division ladder to find the GCD
For a GCD ladder, every selected divider must divide all current entries. The worked example divides 36, 108, and 126 by 2, then by 3, then by 3 again.
Worked example 2 — GCD route
Why the ladder may stop
After the three divisions, the bottom row is:
2, 6, 7
The numbers 2 and 6 still share a factor, but no factor greater than 1 divides all three.
For a multi-number GCD, the bottom row only needs overall GCD 1. It does not need to be pairwise coprime.
Revealed divider product1
Bottom-row GCD—
original GCD—
Checkpoint
Reveal all three divisions before checking this mission.
Need a hint? Start here
A GCD divider must divide every current entry. Multiply only the chosen dividers.
Check why it works
2×3×3=18; the final row 2,6,7 has overall GCD 1. Divider product 18; bottom-row GCD 1; original GCD 18.
Mission 3
Not completeContinue the same ladder far enough to find the LCM
For this LCM ladder, continue after the common-to-all steps. Choose a prime that divides at least two current entries. Divide every entry divisible by that prime, and copy every other entry unchanged.
Predict a copied entry: In the new row 6, 10, 15, choose divider 2. Which original entry must be copied unchanged?
Worked example 2 — LCM route
What changes in the extra step?
The extra divider is 2:
2, 6, 7 → 1, 3, 7
The 7 is not divisible by 2, so it is copied down. The final entries 1, 3, and 7 are pairwise coprime.
LCM = all selected dividers × all final entries.
Selected-divider product1
Final-row product—
original LCM—
Checkpoint
Reveal all four divisions and answer the copied-entry prediction before checking.
Need a hint? Start here
For the LCM, copy unchanged entries and multiply the final row as well.
Check why it works
Prediction: copy 15 in row 6,10,15. In the worked example extra step, divide 2 and 6 by 2 and copy 7. Extra divider 2; copied entry 7; LCM (2×3×3×2)×1×3×7=756.
Mission 4
Not completeUse the correct stopping rule
“Overall GCD 1” means no number greater than 1 divides every entry. “Pairwise coprime” means each pair of entries has GCD 1. These are different conditions. A GCD ladder uses the first; an LCM ladder uses the second.
Stop-rule laboratory
Checkpoint
Need a hint? Start here
Overall GCD 1 does not mean that every pair has GCD 1.
Check why it works
Row 2,6,7 has overall GCD 1, but 2 and 6 share 2. GCD ladder may stop: yes; this LCM ladder may stop: no. Pairwise GCDs for 6,10,15 are 2,3,5.
Mission 5
Not completeComplete Guided Practice 2
The worked example asks for the GCD and LCM of 403, 527, and 713. One common division gives three pairwise-coprime quotients (the numbers left in the next row). These are not division remainders.
Factor structure
403 = 13 × 31
527 = 17 × 31
713 = 23 × 31
The worked example’s short-division step is:
31 │ 403 527 713
13 17 23
13 17 23
The final entries 13, 17, and 23 are pairwise coprime.
Run the guided-practice audit
Multiply 31 by the final entries for the LCM:
31 × 13 × 17 × 23 = ?
GCD—
Final-row product—
LCM—
Pairwise GCDs—
Checkpoint
Run the guided-practice multiplication before checking.
Need a hint? Start here
Look for the same factor in all three numbers before multiplying the final row.
Check why it works
31 divides all three original numbers, giving quotients 13,17,23. GCD 31; LCM 31×13×17×23=157573.
Mission 6
Not completeFollow the Euclidean algorithm one remainder at a time
The Euclidean algorithm repeats one step: divide, keep the remainder, then use the previous divisor and that remainder as the next pair. Follow the worked chain below.
Complete chain for paper review: 527 = 1 × 403 + 124; 403 = 3 × 124 + 31; 124 = 4 × 31 + 0. The final divisor is 31.
Find gcd(527,403)
The invariant behind Euclid
527 = 1 × 403 + 124
A number divides both 527 and 403 exactly when it divides both 403 and 124. Replacing the larger number by the remainder does not change the GCD.
When the remainder becomes 0, the divisor in that final division is the GCD. In this chain it is also the last nonzero remainder. If the very first division has remainder 0, use its divisor; there was no earlier nonzero remainder.
gcd(527,403) = ?
Checkpoint
Reveal all three divisions before checking.
Need a hint? Start here
Subtract a multiple of the smaller number. Common divisors are preserved.
Check why it works
527=1×403+124; 403=3×124+31; 124=4×31+0. Quotients 1,3,4; final divisor and GCD 31.
Mission 7
Not completeUse a general short-division laboratory
The laboratory generates a canonical ladder. For GCD, it repeatedly uses the smallest prime dividing every current entry. For LCM, it uses the smallest prime dividing at least two entries and copies the rest.
Short-division generator
Laboratory checkpoint
Answer for the fixed numbers 72, 90, 120, even if you explore another preset.
Need a hint? Start here
Check whether a divider acts on all entries or only on a subset.
Check why it works
GCD dividers multiply to 6. The LCM ladder must remove every remaining shared prime before multiplying the final row. GCD 6; LCM 360.
Mission 8
Not completeUse a general Euclidean laboratory
For two positive whole numbers, repeated remainder divisions usually reach the GCD faster than listing all factors.
Euclidean algorithm generator
Extend Euclid to more than two numbers
gcd(403,527,713) = gcd(gcd(403,527),713) = gcd(31,713) = 31
Fold the numbers into the calculation one at a time.
Laboratory checkpoint
Answer for the fixed pair 713 and 527. Count every division equation, including the final one with remainder zero. The generator puts the larger input first.
Need a hint? Start here
The next pair is the previous divisor and the remainder. Stop at remainder zero.
Check why it works
713=1×527+186; 527=2×186+155; 186=1×155+31; 155=5×31+0. Four division rows; final divisor and GCD 31.
Mission 9
Not completeIndependent workshop
Correct all eight questions to complete the workshop.
1. In a GCD short-division step, the divider must divide …
2. In an LCM step, an entry not divisible by the selected prime is …
3. gcd(36,108,126)
4. lcm(36,108,126)
5. gcd(403,527,713)
6. lcm(403,527,713)
7. gcd(72,90,120)
8. lcm(72,90,120)
— / 8
Need a hint? Start here
Choose the method before calculating. Revisit the local hint for that method, then verify every condition in the question.
Check why it works
The LCM includes both the selected-divider product and final-row product. All current entries; copied unchanged; 18; 756; 31; 157573; 6; 360.
Mission 10
Not completeObjective exit ticket
Complete all ten missions, including 5 out of 5 on this ticket, to earn the certificate.
1. Product of the dividers in a complete GCD ladder for 36,108,126
2. lcm(36,108,126)
3. gcd(2,6,7)
4. GCD of the fresh pair 1071 and 462
5. lcm(403,527,713)
— / 5
÷R
Short-Division & Euclidean Algorithm Navigator
This certifies that the student can build GCD and LCM short-division ladders, apply the correct stopping rule, copy unchanged entries, and find a two-number GCD through repeated remainders.
Lesson 19.2 • Chapter 19
Optional reflection — not automatically graded
Need a hint? Start here
Choose the method before calculating. Revisit the local hint for that method, then verify every condition in the question.
Check why it works
1071=2×462+147; 462=3×147+21; 147=7×21+0. Answers: 18; 756; 1; 21; 157573.
Teaching notes
The chapter introduction names the Euclidean algorithm, but these pages do not provide a worked Euclidean example; the remainder chains and general Euclidean laboratory on this page are added instructional scaffolding.The page also preserves the original’s distinction between the GCD stopping rule (overall GCD 1) and the LCM stopping rule (pairwise coprime final entries).