Curriculum · Number Theory · Divisibility & Primes

GCD, LCM & the Euclidean Algorithm

The Euclidean algorithm, Bezout's identity, and gcd·lcm = product.

Objectives

Run the Euclidean algorithm
Apply gcd·lcm = ab
Use Bezout for existence arguments

The full interactive edition of this lesson ships in v1.5. The topic is live everywhere else — the problems below feed your Divisibility & Primes mastery now.

Train the topic

●●○○○How many positive divisors does

36

have?AMC 8 style ●●○○○What is

\gcd(84, 126)

?AMC 8 style ●●●○○What is the smallest positive integer with exactly

6

divisors?AMC 10 style ●●●○○Two positive integers have

\gcd = 6

and

\text{lcm} = 180

. If one of them is

36

, what is the other?AMC 10 style ●●●○○In how many zeros does

25!

end?AMC 10 style