We have 12 red tokens and 18 blue tokens. We want identical bags: every bag must contain the same number of red tokens and the same number of blue tokens. We cannot cut a token or leave one out. How many bags can we make?
You only need whole-number multiplication and division. We will explain factors, multiples and prime numbers when they become useful. Here we use positive whole numbers: 1, 2, 3, and so on; zero is not one of our inputs.
Revisit division and remaindersTry 5 bags in the picture. Give every bag two red tokens: that uses 5×2=10, leaving 12−10=2. Three blue tokens per bag use 5×3=15, leaving 18−15=3. The bags match, but some tokens are left out, so this choice does not solve our problem.
Change the number of bags. A red circle is one red token; a blue square is one blue token. Every outlined box is one bag. Look at the separate leftover tray, not only at whether the bags match. You can also change how many tokens we start with.
With 6 bags, each bag gets 12÷6=2 red tokens and 18÷6=3 blue tokens, with nothing left. When a positive whole number divides another exactly, we call it a divisor, or a factor, of that number. Thus 6 is a divisor of 12 and also of 18: it is a common divisor.
Each bag: 2 red, 3 blue
This choice leaves tokens out. There are 2 red and 3 blue tokens outside the bags. Giving those only to some bags would make the bags different.
Could we make even more identical bags? We can check every possible bag count. It cannot exceed the smaller token total, because every bag needs at least one token of each colour. The marked numbers below divide both current totals exactly. Select one to check it in the bags.
Outlined numbers divide both totals; the selected number is filled.
Common divisors: 1, 2, 3, 6
The greatest of these is 6. It gives the largest possible number of identical bags. We call it the greatest common divisor, abbreviated GCD. The notation gcd(12,18)=6 records the two starting numbers and their answer.
Now we have a different question. Bus A leaves every 4 minutes and bus B every 6 minutes. Both leave at time zero. A leaves at 0, 4, 8, 12, … minutes, while B leaves at 0, 6, 12, … minutes. We want the first later time when both leave together.
The two rows use the same time scale. A filled circle is an A departure; a diamond is a B departure. Move the clock or step through time. A vertical gold line joins departures that happen together. The mark at zero is our starting event, so it is not the later meeting we are looking for.
At zero, both buses have just left. We are looking for a meeting after this one.
With the current intervals, the first later meeting is 12 minutes: 12=3×4=2×6. We write lcm(4,6)=12. This display ends at the second positive meeting, 24 minutes.
A positive multiple of 4 is what we get by multiplying 4 by 1, 2, 3, and so on: 4, 8, 12, …. A meeting time must be a multiple of both intervals, so it is a common multiple. We want the smallest positive one: the least common multiple, or LCM. For 4 and 6, it is 12.
Recall the bags: a common divisor fits inside both totals. Here a common multiple contains a whole number of both intervals. The direction of the question has changed. A divisor of 12 cannot be larger than 12; a positive multiple of 12 cannot be smaller than 12.
Checking every candidate works for 12 and 18, but would take many checks for large numbers. We need a way to make the numbers smaller without changing their common divisors. Consider two strips of lengths 48 and 18. Length here means a count of equal unit pieces, not a new physical unit.
Two copies of the 18-strip fit into the 48-strip. They use 2×18=36 units, leaving 48−36=12. This leftover is the remainder. Why can we replace the pair 48, 18 by 18, 12? We must check both directions, or we might accidentally lose or add an answer.
Suppose a size divides 48 and 18 exactly. The 48-strip and each 18-piece can all be cut into that size. Removing two complete 18-pieces removes only complete groups, so the remaining 12 is also made of complete groups. Every common divisor of 48 and 18 therefore divides 18 and 12.
Conversely, suppose a size divides 18 and 12 exactly. Putting two 18-pieces and one 12-piece back together gives 48=2×18+12. Everything is still made of complete groups, so that size also divides 48. No new common divisor has appeared either. The two pairs have exactly the same common divisors, including the greatest one.
This reasoning works whenever we divide a larger number by a smaller one. Remove as many whole copies of the smaller number as fit. The leftover and the smaller number keep exactly the same common divisors. Repeat with that smaller pair. The nonzero remainder is always smaller than the previous divisor, so these positive whole numbers cannot keep shrinking forever.
Use Next step to cut one strip at a time. Each blue block is one whole copy of the current divisor; the gold piece is the remainder. The divisions already completed stay below the picture. If a block would be too small to read, its count remains in the equation.
The strip has not been cut yet. Use Next step to remove whole copies of the smaller strip and inspect what remains.
This repeated division is called the Euclidean algorithm. An algorithm is a set of steps we can carry out in order. Its important feature here is not its name: it reduces the work while keeping the answer, and we have checked why each replacement is valid.
We have a fast way to find the GCD. To see GCD and LCM together, it helps to look inside a multiplication. For example, 12=3×4, and 4=2×2. Replacing the 4 by 2×2 gives 12=3×2×2. We changed the writing, not the product.
Can we split the 2 again into whole-number factors both greater than 1? No: its only positive divisors are 1 and 2. A whole number greater than 1 with exactly those two divisors is a prime number. The same is true of 3, 5 and 7. A number greater than 1 that can split further, such as 4=2×2, is composite.
Each fork replaces one number with two factors whose product equals it. The bottom row keeps all the pieces currently in use. Choose a number and a first split, then reveal the forks one at a time. The ringed end numbers are prime; an unfinished composite can still split.
The product is still 36. Reveal a fork to replace one composite end number with its two factors. Nothing is added to the multiplication without replacing what was there.
Why does splitting finish? A split such as 36=4×9 replaces 36 with smaller positive whole numbers, each still greater than 1. Along any branch the numbers get smaller, so a branch cannot continue forever. A number left at the end must be prime, because a composite number still has a permitted split. Thus every whole number greater than 1 has a prime factorization.
For a shorter record, 2×2×2 is written 23. The small raised 3 counts three copies of the factor 2; it does not mean 2×3. The diagrams below keep the individual copies visible even when we use this shorter notation.
You may have split 36 as 4×9 or as 6×6. Both routes end with two 2s and two 3s. But a few trees do not prove that every possible route gives the same prime factors. We need a reason before relying on the lists to calculate GCD and LCM.
We will use the division method we just explained. It has one more useful consequence: the GCD can be written using whole-number multiples of the two starting numbers, added or subtracted. Here “whole-number multiples” allows a minus sign: −5 means subtract one copy of 5. Watch how the remainder 1 from the numbers 5 and 3 is rebuilt.
Reveal each line and keep the previous ones. A highlighted replacement uses an earlier equality; we do not guess new numbers. After the numerical example, the next steps explain why the same reasoning applies generally.
Now choose a prime number, call it p, and two positive whole numbers, call them u and v. We want to know: if p divides u×v, must it divide u or v? If it already divides u, the answer is yes. Consider the remaining case: it does not divide u.
The only positive divisors of the prime p are 1 and p. Since p does not divide u, their only common divisor is 1. The remainder argument above therefore lets us write 1 as an integer multiple of p plus an integer multiple of u. Call those two multipliers s and t; they may be negative.
Multiply the whole equality by v. On the right, the first term is a multiple of p. The second is also a multiple of p, because we started by assuming that p divides uv. Adding or subtracting complete multiples of p still leaves a multiple of p. The left side, v, must therefore be divisible by p.
We have proved the needed rule: a prime dividing a product must divide at least one factor. For more than two factors, group all but the first into one product and repeat the same argument. It is essential that the divisor is prime: 6 divides 2×3, but 6 divides neither 2 nor 3.
Suppose two prime-factor lists make the same number. Take one prime from the first list. It divides the full product, so the rule above says it divides one prime in the second list. A prime has no divisor greater than 1 except itself, so these two primes must match. Cancel that matching pair and repeat on what remains. One list cannot have primes left after the other is empty: their product would exceed 1. Therefore the lists contain the same primes with the same number of copies; only their order can differ.
This also explains divisibility. If a number d divides a number a, then a=d×k for a positive whole number k. Split d and k into primes: together they give the prime list of a, so every prime copy needed by d is available in a. Conversely, if those copies are available, the leftover copies multiply to a whole number k, giving a=d×k. No leftover copies means k=1. We can now use prime counts without guessing.
Return to 12 and 18. Their lists are 12=2×2×3 and 18=2×3×3. The two 2s in 12 are two separate factors, not one factor named 4. The diagram places copies of the same prime in one column so we can compare how many each number has.
A common divisor can use only prime copies available in both numbers. There are two 2s in 12 but only one in 18, so a common divisor can use at most one 2. There is one 3 in 12 but two in 18, so it can use at most one 3. Taking both available copies gives 2×3=6. Any common divisor can use no more of any prime, so it divides this product and cannot be larger. That proves we have the greatest common divisor.
A common multiple must contain enough prime copies for both numbers to divide it. To contain 12, it needs two 2s. To contain 18, it needs two 3s. The copies can serve both requirements, so we need two of each, not three of each: 2×2×3×3=36. Every common multiple needs at least these copies; this product divides every common multiple and is itself a common multiple. It is therefore the least positive one.
Choose GCD or LCM, then advance one prime column at a time. Each numbered chip is one factor. The result row records how many copies we keep. Changing either starting number or the mode resets the calculation so an old answer cannot remain attached to new inputs.
We have not selected a prime column yet. The product starts at 1, so multiplying by the first chosen factor will give that factor.
In short notation, the number of copies of a prime is its exponent. For GCD choose the smaller exponent for each prime; for LCM choose the larger exponent. A missing prime has exponent zero. The pictures and the divisibility argument explain why these rules work; the words “smaller” and “larger” alone are not the explanation.
Three useful checks: 1 and any positive whole number have GCD 1 and LCM equal to that number. Two equal numbers have that same number as both answers. If two numbers share no prime factor, their GCD is 1; such numbers are called coprime. Neither number has to be prime: 8 and 9 are coprime, and their LCM is 8×9=72.
Before calculating, decide whether a number must divide both starting totals or contain whole copies of both. Write a reason for the choice. Open each worked answer when you are ready; it includes the calculation as well as the result.
You have 20 red and 30 blue tokens. What is the largest number of identical bags with no token left over? How many of each colour go in one bag?
The bag count must divide 20 and 30, so we want their GCD. 20=2×2×5 and 30=2×3×5. Both lists contain one 2 and one 5, giving 2×5=10 bags. Each has 20÷10=2 red and 30÷10=3 blue tokens. A larger bag count cannot divide both totals.
Two bells ring together now. One rings every 6 minutes and the other every 8 minutes. When do they next ring together? Why is zero not the answer?
The wait must contain a whole number of 6-minute intervals and 8-minute intervals, so we need a common multiple. 6=2×3 and 8=2×2×2. Supplying three 2s and one 3 gives the least positive one: 2×2×2×3=24 minutes. Check: 24=4×6=3×8. Zero records the current ringing; “next” asks for a positive wait.
Find the GCD of 84 and 30 using remainders. At each replacement, say why the common divisors stay the same.
Calculate 84=2×30+24, then 30=1×24+6, then 24=4×6+0. Thus the GCD is 6. Any divisor of the old pair divides the remainder after complete groups are removed. Conversely, any divisor of the smaller number and the remainder divides their recombined total. This two-way argument preserves exactly the common divisors at every replacement.
Someone takes all prime factors from 12 and 18 and multiplies them, obtaining 216. It is a common multiple. Why is it not the least one?
The combined lists contain three 2s and three 3s. But both original lists already fit into two 2s and two 3s: 36=12×3=18×2. The extra 2 and 3 are unnecessary. LCM supplies the larger count needed for each prime, rather than adding the two counts. This gives 36, not 216.
This lesson is part of our full 88-course interactive library. Sign in or create a free account to interact with the 3D simulation and save your progress.