GCD and LCM Question Generator
Two numbers, their highest common factor and their lowest common multiple. The identity worth carrying away is that the two multiply to the product of the original numbers — so finding one gives the other for free. Euclid's algorithm is written out line by line, because it finds the factor without ever needing the prime factorisations, which is why it stays fast on numbers far too large to factorise.
What this generator does
Draws two numbers and computes both quantities, showing Euclid's algorithm as the division steps that produce the factor. Prime factorisations of both numbers are given alongside, so the two methods can be compared.
How to use this tool
- Choose how large the numbers may be.
- Find the highest common factor, by Euclid's algorithm or by factorising.
- Use the product identity to get the lowest common multiple.
- Reveal the answer and the working.
Understanding the controls
- Largest number
- From 10 up to 999. Larger numbers make factorising slow and Euclid's algorithm look better, which is rather the point.
- Seed
- Reproduces the same pair of numbers exactly.
- Show the answer
- Reveals both results and every division step of Euclid's algorithm.
Common use cases
- Homework on highest common factor and lowest common multiple
- Practice at Euclid's algorithm rather than factor trees
- Showing why gcd times lcm equals the product
- Questions where both answers can be checked against each other
- Setting the same numbers for a class from a seed
How this generator works
Euclid's algorithm repeatedly replaces the larger number with the remainder until nothing is left, and the last non-zero remainder is the answer. The lowest common multiple follows from the product identity. The check verifies that identity, that the factor divides both numbers, that the multiple is divisible by both, and that both factorisations multiply back.
Randomness and fairness
The two numbers are random; both answers are arithmetic. Seeded questions reproduce and are therefore explicitly not cryptographically secure. Unseeded, the browser's cryptographically secure generator draws them.
For how randomness is produced across the whole site, see how Generate Random works.
Limitations and good to know
- Two numbers per question. The factor and multiple of three or more at once are not generated.
- Numbers stop at 999, which keeps the factorisation display short.
- No fraction simplification, though that is the most common use of a highest common factor.
- Answers are revealed for comparison; neither number is marked against what you worked out.
- Questions are not saved between visits.
Privacy and your data
Both numbers and every step are computed in your browser. Nothing you generate is transmitted or stored.
Related generators
- Prime Factorisation Question GeneratorPrime-factorisation questions built to order, answered in index form, with the factors checked to be prime.
- Continued Fraction GeneratorExpands any fraction into its continued fraction and lists the convergents, each proved to be the best approximation for its denominator.
- Coprime Number GeneratorPairs sharing no factor beyond one, with a non-coprime counterexample and Euler's totient counted directly.
- Modular Arithmetic Question GeneratorRemainders, modular powers by repeated squaring, and inverses that only exist when the values are coprime.
- Factor GeneratorA random number shown with its complete list of factors.