Factors and multiples: Euclid's algorithm

Practice 5 items →

Euclid's algorithm — gcd(a, b) = gcd(b, a mod b) — finds a GCF faster than prime trees for large pairs. Students run it to completion (not one remainder too early), then get the LCM from the product identity, and solve cycle and partition stories without swapping HCF and LCM.

Specification · for a parent or teacher

Part no.: euclid-gcd
Course: Advanced Math 7 · Unit 1
Realm: Numbers
Difficulty: 3 of 4 — Grade 6–7 core. Multi-step, first symbolic work.
Qty: 5 items

Part no. is the node's id; the realm is the kind of math; qty is how many practice items it carries.

Students can

prime factorization and index notation; HCF/GCF and LCM; cycle and partition stories; Euclid’s algorithm.

Ready when

$\gcd(252, 198)$ by Euclid, then LCM via $\mathrm{lcm}(a,b)=\frac{ab}{\gcd(a,b)}$ .

Formulas

Euclid

\gcd(a,b) = \gcd(b,\ a \bmod b)

LCM from GCD

\operatorname{lcm}(a,b) = \frac{ab}{\gcd(a,b)}

Watch for

stopping Euclid one remainder too early; HCF and LCM swapped in a story.

Before · requires

Whole numbers: primes, GCF, and LCMgcf-lcm-grade6 · Math 6
Division (2-digit divisors)two-digit-division · Math 5

After · used by

— none

Print this set Open on map