Using GCD to Plan Equal Events
A city youth commission wants to hold events for 33 students from Allenville High and 18 students from Kinley High. The same combination must attend each event, with no students left out or attending multiple events. What is the greatest number of events possible?
Already Got the Answer?
Setup: The number of events must divide both 33 and 18 exactly, so we want gcd(33, 18).
Result:gcd(33, 18) = 3 events, each with 11 Allenville students and 6 Kinley students.
One-line check:3 × 11 = 33 and 3 × 6 = 18, so no one is left over.
If you answered 11, 6, or 17, you found the size of an event, not the number of events. See the pitfalls below.
What You Will Learn
- How to translate "equal groups, nobody left out" into the language of divisibility. The problem never says "GCD", so this translation is the real skill.
- Why the number of groups must be a common factor of both totals, and why the greatest such number is the GCD.
- Three ways to compute a GCD: listing factors, prime factorization, and the Euclidean algorithm.
- How to tell the number of groups from the size of each group, which is the most common slip on this problem type.
- How GCD word problems differ from LCM word problems, and how to choose between them quickly.
Reading the Problem Like a Mathematician
Look closely at the phrase "the same combination must attend each event, with no students left out or attending multiple events." It contains three separate rules:
- Same combination at every event. Every event has the same number of Allenville students and the same number of Kinley students.
- No one left out. All 33 + 18 = 51 students must be placed in some event.
- No one attends twice. Each student belongs to exactly one event.
Together these rules say that each school's students are being partitioned into the same number of equal piles. If there are e events, then 33 students split into e equal piles and 18 students split into e equal piles. Equal piles with no remainder means e divides 33 and e divides 18.
Key translation: "Same groups, nothing left over, as many groups as possible" means greatest common divisor.
Solution: Method 1 — Listing Factors and Comparing
This is the most direct approach, and it makes the logic visible. Write down every possible number of events for each school, then find where the lists overlap.
Step 1 — Set up the divisibility condition
Let e be the number of events. Each Allenville student goes to exactly one event, and each event gets the same number of them, so 33 ÷ e must be a whole number. The same reasoning applies to Kinley, so 18 ÷ e must also be a whole number.
Step 2 — List the factors of each number
Factors come in pairs that multiply to the number:
Factors of 18: 1, 2, 3, 6, 9, 18
Step 3 — Find the common factors
Only values that appear in both lists can be a valid number of events:
Here is every candidate tested directly, so you can see why the others fail:
| Events (e) | 33 ÷ e | 18 ÷ e | Valid? |
|---|---|---|---|
| 1 | 33 | 18 | Yes |
| 2 | 16.5 | 9 | No (33 does not split) |
| 3 | 11 | 6 | Yes, and the greatest |
| 6 | 5.5 | 3 | No (33 does not split) |
| 9 | 3.67… | 2 | No (33 does not split) |
| 11 | 3 | 1.63… | No (18 does not split) |
| 18 | 1.83… | 1 | No (33 does not split) |
| 33 | 1 | 0.54… | No (18 does not split) |
Notice that every failure comes from one school splitting nicely while the other does not. Both schools have to cooperate at the same time.
Step 4 — Choose the greatest valid value
The greatest common factor is 3, so the greatest number of events is 3.
Step 5 — Describe what each event looks like
Kinley per event: 18 ÷ 3 = 6
Total per event: 11 + 6 = 17
Three events, each with 11 Allenville students and 6 Kinley students, for 17 students per event.
Solution: Method 2 — Prime Factorization
Listing factors works well for small numbers, but it becomes tedious for numbers like 504 and 756. Prime factorization scales much better, because the GCD can be read directly from the prime building blocks.
Step 1 — Break each number into primes
18 = 2 × 3 × 3 = 2 × 3²
Step 2 — Keep the primes the two numbers share
For each prime that appears in both factorizations, take the smaller exponent. The prime 3 appears as 3¹ in 33 and 3² in 18, so we keep 3¹. The prime 11 appears only in 33 and the prime 2 appears only in 18, so neither contributes.
Step 3 — Interpret the result
The "leftover" primes tell you what each event looks like. After removing the shared 3 from each number, 33 leaves 11 and 18 leaves 2 × 3 = 6. Those are the Allenville and Kinley counts per event. The 11 and the 6 share no prime factors, which is exactly why 3 events cannot be improved on.
Why this works: A number of events is valid only if every prime power in it is "available" in both 33 and 18. Taking the smaller exponent of each shared prime builds the largest such number.
Solution: Method 3 — The Euclidean Algorithm
This 2,300-year-old procedure needs no factoring at all. It is how computers find GCDs, and it is the method to reach for when the numbers are large.
Step 1 — Divide the larger by the smaller and keep the remainder
18 = 1 × 15 + 3
15 = 5 × 3 + 0
Step 2 — Read off the last nonzero remainder
At each line, the old divisor becomes the new dividend and the remainder becomes the new divisor. The process stops when the remainder hits 0. The last nonzero remainder is 3, so gcd(33, 18) = 3.
The logic is that any number dividing both 33 and 18 must also divide their difference 33 − 18 = 15. The pair (33, 18) therefore has exactly the same common divisors as the smaller pair (18, 15), and then (15, 3). Each step shrinks the problem without changing the answer.
The Answer
The greatest number of events is 3, since gcd(33, 18) = 3. Each event has 11 Allenville students and 6 Kinley students (17 students per event).
Verification
A check for this kind of problem has two halves. We confirm that 3 events work, and we confirm that no larger number of events does.
3 events work:
3 × 11 = 33 Allenville students, all placed. 3 × 6 = 18 Kinley students, all placed. Total: 3 × 17 = 51 = 33 + 18. The same combination (11 + 6) attends every event, no one is left out, and no one is repeated.
More than 3 events cannot work:
Any larger valid number would have to divide 33, which leaves only 11 or 33. But 18 ÷ 11 and 18 ÷ 33 are not whole numbers. So 3 is the maximum.
All three methods (listing, primes, Euclid) independently produced 3, which is also reassuring.
Sanity Check
A GCD answer has a built-in plausibility test: it can never be larger than the smaller of the two numbers. Here that means at most 18 events. The answer of 3 is comfortably inside that range.
Why is it so much smaller than 18? Because 33 is only 3 × 11, and 11 is a prime that 18 does not contain. The number 33 has very few factors, so it limits the options drastically. In general, the GCD is controlled by the "least flexible" number.
| Scenario | Numbers | GCD (max events) |
|---|---|---|
| Our problem | 33 and 18 | 3 |
| Second group is a multiple of the first | 36 and 18 | 18 |
| Nothing in common | 33 and 20 | 1 (one big event) |
| Identical groups | 18 and 18 | 18 |
The boundary cases show the range of behavior. A GCD of 1 is a perfectly legitimate answer, and it means the only way to satisfy the rules is a single event with everyone in it.
What Trips People Up
Students correctly compute 33 ÷ 3 = 11 and then report that as the final answer. But 11 is the number of Allenville students in each event, not the number of events. The question asks "how many events?", so the answer is 3. Before you box an answer, reread the final sentence of the problem and check that your number has the right meaning.
Both GCD and LCM involve "common" things, so they get mixed up. The LCM of 33 and 18 is 198, which is far more than the 51 students available. Splitting existing groups into equal parts is a GCD situation. Waiting for repeating cycles to line up is an LCM situation. A quick test is that if your answer exceeds the number of people you have, something is wrong.
The smaller number is only an upper bound. With 18 events, each gets 1 Kinley student, but 33 ÷ 18 = 1.83… Allenville students. You cannot send 1.83 students to an event. The number of events must work for both schools at once.
Both 6 and 11 look attractive: 6 divides 18 and 11 divides 33. Each fails on the other school (33 ÷ 6 = 5.5 and 18 ÷ 11 ≈ 1.6). Always test a candidate against both totals before accepting it.
If You See These Words...
This problem never mentions "greatest common divisor", so its disguise is typical of the whole family. The following phrasings are all signals:
- "The same number/combination in each group"
- "No one/nothing left over" or "with none left out"
- "Greatest/largest/maximum number of groups (or the largest possible size)"
- "Cut into the largest equal squares" or "identical gift bags/teams/tables"
A look-alike with different surface details: A florist has 24 roses and 36 tulips and wants to make identical bouquets using every flower. What is the greatest number of bouquets? It is the same structure: gcd(24, 36) = 12 bouquets, each with 2 roses and 3 tulips.
Contrast: If the wording is "when will they next be together" or "smallest number that both divide", that is LCM territory, which is a different tool.
The Pattern Behind This
The structure here generalizes cleanly. Suppose two groups have sizes m and n, and you need identical sets with nobody left out.
Greatest number of sets = g = gcd(m, n)
Each set contains = m ÷ g and n ÷ g
For us, g = 3 and each event has 33 ÷ 3 = 11 and 18 ÷ 3 = 6.
Connection to fractions. The per-event numbers 11 : 6 are the ratio 33 : 18 reduced to lowest terms. Dividing by the GCD is exactly what you do when simplifying the fraction 33/18 = 11/6. Each event is a miniature copy of the whole group, shrunk by a factor of 3. This is why the per-event counts, 11 and 6, share no common factor: if they did, you could have made even more events.
Extra fact worth knowing: every common divisor of two numbers divides their GCD. That is why the valid event counts here, 1 and 3, are exactly the divisors of 3.
Limits of the formula: It assumes everyone must be placed. If leftovers are allowed, the GCD is no longer the answer (see What-If #4 below). With three or more groups, the formula still works, since gcd(a, b, c) = gcd(gcd(a, b), c).
Beyond the Textbook
- Tiling and cutting: The largest square tile that exactly covers a 33 cm × 18 cm panel has side
gcd(33, 18) = 3cm. Carpenters and flooring installers use this idea constantly. - Kit and packaging design: A warehouse with 120 pencils and 80 erasers can make at most
gcd(120, 80) = 40identical supply kits with no leftovers. - Gears and music: The reduced ratio of two gears' tooth counts, found by dividing by the GCD, tells you how often the same teeth meet. Rhythm patterns in music are analyzed the same way.
- Cryptography: The Euclidean algorithm from Method 3, in extended form, underlies the key computations in RSA encryption.
A Brief History
The Euclidean algorithm appears in Book VII of Euclid's Elements (around 300 BCE), which makes it one of the oldest procedures still in everyday use. Euclid framed it geometrically, as repeatedly measuring the longer of two line segments with the shorter until a common unit of measure is found. That is the same "largest equal piece" idea as our events. The problem type persists in classrooms because it is a perfect small example of how a real-world constraint (fairness, no leftovers) turns into a precise arithmetic condition.
Where This Leads
Once the GCD feels natural, two extensions follow. The first is three or more groups, where you take the GCD of all the totals (What-If #2 below). The second is relaxing "no one left out", which turns the problem into an optimization with remainders and constraints. In later courses this connects to linear Diophantine equations and to the Chinese remainder theorem.
A challenge to carry forward: for which pairs of numbers is the GCD equal to 1, and why does that mean the only allowed schedule is one single event?
Try These Variations
Work each one on paper before opening the solution. They are arranged from a straightforward change to a genuine twist.
The commission now has 45 students from Lincoln High and 30 students from Park High. The same combination must attend each event, with no students left out or attending multiple events. What is the greatest number of events, and how many students from each school are at each event?
The number of events must divide both 45 and 30, so we need gcd(45, 30).
45 = 3² × 5 and 30 = 2 × 3 × 5.
The shared primes are 3 (smaller exponent 1) and 5 (exponent 1), so gcd = 3 × 5 = 15.
Lincoln: 45 ÷ 15 = 3. Park: 30 ÷ 15 = 2. Each event has 5 students.
15 × 3 = 45 and 15 × 2 = 30, so no one is left out. The per-event counts 3 and 2 share no factor, so no larger number of events is possible. Answer: 15 events, each with 3 Lincoln students and 2 Park students.
Rivera High adds 27 students to the original 33 from Allenville and 18 from Kinley. The same combination from all three schools must attend each event, with no students left out or attending multiple events. What is the greatest number of events now?
The number of events must now divide all three totals: 33, 18, and 27.
gcd(33, 18, 27) = gcd(gcd(33, 18), 27). We already know gcd(33, 18) = 3.
gcd(3, 27) = 3, since 27 = 3 × 9.
Allenville: 33 ÷ 3 = 11. Kinley: 18 ÷ 3 = 6. Rivera: 27 ÷ 3 = 9. That is 11 + 6 + 9 = 26 students per event.
3 × 26 = 78 = 33 + 18 + 27. Adding a third school can never raise the GCD, and here it stayed at 3 because 27 happened to be a multiple of 3. Answer: 3 events.
Allenville High sends 36 students. Kinley High sends some number of students between 40 and 50. The commission finds that the greatest number of identical events it can hold, with no one left out, is exactly 12. How many students does Kinley send?
Let Kinley's count be k. The statement says gcd(36, k) = 12.
Since 12 divides the GCD's both inputs, k must be a multiple of 12. The multiples of 12 near the range are 36, 48, and 60.
Only 48 lies between 40 and 50.
36 = 2² × 3² and 48 = 2⁴ × 3. The shared part is 2² × 3 = 12. Being a multiple of 12 is necessary but not sufficient, which is why k = 36 would give a GCD of 36 instead.
12 events give 36 ÷ 12 = 3 Allenville and 48 ÷ 12 = 4 Kinley students per event. The counts 3 and 4 share no factor, so 12 is the maximum. Answer: Kinley sends 48 students.
Return to 33 Allenville and 18 Kinley students. Now students may be left out, but every event must have the same combination, no student attends twice, and every event must include at least 4 Allenville students and at least 3 Kinley students. What is the greatest number of events, and how many students are left out if as many students as possible are used?
With leftovers allowed, the number of events no longer needs to divide the totals. We need e × a ≤ 33 and e × k ≤ 18, where a ≥ 4 and k ≥ 3 are the per-event counts.
Allenville limits events to e ≤ 33 ÷ 4 = 8.25, so at most 8. Kinley limits events to e ≤ 18 ÷ 3 = 6. Both must hold, so e ≤ 6.
Take k = 3, which uses all 18 Kinley students (6 × 3 = 18). For Allenville, the largest valid a satisfies 6a ≤ 33, so a = 5 (6 × 5 = 30). Since 5 ≥ 4, the rule is satisfied.
Seven events would need at least 7 × 3 = 21 Kinley students, but only 18 exist.
Used: 6 × (5 + 3) = 48 students. Left out: 51 − 48 = 3, all from Allenville (33 − 30 = 3). Answer: 6 events, each with 5 Allenville and 3 Kinley students, with 3 Allenville students left out. Once leftovers are permitted, the answer doubles from 3 to 6, so the "no one left out" rule is exactly what makes the GCD the right tool.
Frequently Asked Questions
2026-08-04