Applying the Euclidean Algorithm: Real-World GCD and Schedule Problems

1) Two classrooms are combining their chairs for an assembly. One has 48 chairs, and the other has 72. They want to set up identical rows with no extra chairs left over. What is the greatest number of chairs that can go in each row?

6

8

12

24

We’re splitting into equal rows: use GCD(48, 72).

48 = 2⁴·3, 72 = 2³·3² → GCD = 2³·3 = 24 chairs/row.

Explanation

We’re splitting into equal rows: use GCD(48, 72).

48 = 2⁴·3, 72 = 2³·3² → GCD = 2³·3 = 24 chairs/row.

2) A florist is making centerpieces using 90 roses and 126 tulips. She wants each centerpiece to have the same mix of roses and tulips, with no flowers left over. How many centerpieces can she make?

6

9

18

30

Number of centerpieces = GCD(90, 126).

90 = 2·3²·5, 126 = 2·3²·7 → GCD = 2·3² = 18 centerpieces.

Explanation

Number of centerpieces = GCD(90, 126).

90 = 2·3²·5, 126 = 2·3²·7 → GCD = 2·3² = 18 centerpieces.

3) A coffee shop offers loyalty cards that reset every 28 visits for espresso drinkers and every 36 visits for tea drinkers. If someone buys both types, after how many visits will both cards reset on the same day again?

84

126

252

504

Now we need when they align → LCM(28, 36).

28 = 2²·7, 36 = 2²·3² → LCM = 2²·3²·7 = 252 visits.

Explanation

Now we need when they align → LCM(28, 36).

28 = 2²·7, 36 = 2²·3² → LCM = 2²·3²·7 = 252 visits.

4) A mural is being painted using panels that are 56 inches wide and 72 inches wide. The artist wants to divide the entire wall into identical vertical sections with no panel left over. What is the greatest possible width of each section?

4 inches

8 inches

12 inches

16 inches

Cut into the widest equal sections → GCD(56, 72).

56 = 2³·7, 72 = 2³·3² → GCD = 2³ = 8 inches.

Explanation

Cut into the widest equal sections → GCD(56, 72).

56 = 2³·7, 72 = 2³·3² → GCD = 2³ = 8 inches.

5) Find the GCD(420, 308) using the Euclidean Algorithm. What is the first remainder when 420 is divided by 308?

28

84

98

112

420 ÷ 308 → 308·1 = 308; remainder = 112.

Explanation

420 ÷ 308 → 308·1 = 308; remainder = 112.

6) Continue GCD(420, 308): 308 ÷ 112 leaves remainder

0

28

84

98

112·2 = 224; remainder = 308 − 224 = 84.

Explanation

112·2 = 224; remainder = 308 − 224 = 84.

7) The GCD(420, 308) is

14

28

56

84

112 ÷ 84 → rem 28; 84 ÷ 28 → rem 0 → GCD = 28.

Explanation

112 ÷ 84 → rem 28; 84 ÷ 28 → rem 0 → GCD = 28.

8) A neighborhood association is planting two types of trees: maple trees in groups of 32 and birch trees in groups of 48. They want to arrange them in identical clusters with the same number of each tree. What is the greatest number of clusters they can make?

4

8

12

16

Number of clusters = GCD(32, 48) = 2⁵ and 2⁴·3 → GCD = 2⁴ = 16 clusters.

Explanation

Number of clusters = GCD(32, 48) = 2⁵ and 2⁴·3 → GCD = 2⁴ = 16 clusters.

9) A shipment has 120 bottles of juice and 96 bottles of water. If they want to pack them into identical crates with the same number of each type and no bottles left over, how many crates should they prepare?

8

12

24

16

Crates = GCD(120, 96).

120 = 2³·3·5, 96 = 2⁵·3 → GCD = 2³·3 = 24 crates.

Explanation

Crates = GCD(120, 96).

120 = 2³·3·5, 96 = 2⁵·3 → GCD = 2³·3 = 24 crates.

10) Two ferry boats leave the harbor at the same time. One returns every 40 minutes, the other every 56 minutes. After how many minutes will they next arrive back together?

140

200

280

320

When cycles align → LCM(40, 56).

40 = 2³·5, 56 = 2³·7 → LCM = 2³·5·7 = 280 minutes.

Explanation

When cycles align → LCM(40, 56).

40 = 2³·5, 56 = 2³·7 → LCM = 2³·5·7 = 280 minutes.

11) A theater has 132 balcony seats and 180 floor seats. The manager wants to divide the seats into identical sections with the same number of each type. How many sections can she make?

6

12

18

24

Sections = GCD(132, 180).

132 = 2²·3·11, 180 = 2²·3²·5 → GCD = 2²·3 = 12 sections.

Explanation

Sections = GCD(132, 180).

132 = 2²·3·11, 180 = 2²·3²·5 → GCD = 2²·3 = 12 sections.