← All Learn lessons · Start adaptive practice · Practise on paper

You will learn: Find the greatest common divisor efficiently and explain why the remainder method works.

Before you start: Positive integers, divisibility and division with remainder.

Find the largest shared building block

The greatest common divisor of two positive integers is the largest positive integer dividing both. It is written gcd(a, b). For example, the positive common divisors of 18 and 30 are 1, 2, 3 and 6, so gcd(18, 30) = 6.

When the gcd is 1, the numbers are called coprime. They need not both be prime: 8 and 15 are coprime even though each is composite.

Why a remainder helps

Suppose a = bq + r. Any integer dividing both a and b divides a − bq = r. Conversely, any integer dividing both b and r divides bq + r = a. Thus (a, b) and (b, r) have exactly the same common divisors, so gcd(a, b) = gcd(b, r).

This is the Euclidean algorithm: divide, replace the pair by the divisor and remainder, and repeat. Remainders decrease until one is zero. The last nonzero remainder is the gcd. We use gcd(b, 0) = b for positive b, since b divides 0 and is the largest positive divisor of b.

Worked example 1: gcd(84, 30)

84 = 2 × 30 + 24
30 = 1 × 24 + 6
24 = 4 × 6 + 0

The gcds along the way are gcd(84, 30) = gcd(30, 24) = gcd(24, 6) = 6. As a check, 84/6 = 14 and 30/6 = 5. The argument above, not just this check, proves that no larger common divisor was missed.

Worked example 2: equal square tiles

A rectangle measures 84 cm by 30 cm. It is covered exactly by equal square tiles, with tile edges parallel to the rectangle and no cutting. What is the largest possible integer side length? The side must divide both 84 and 30, so it cannot exceed their gcd, 6 cm. Six-centimetre tiles work: 14 fit along one edge and 5 along the other. The covering uses 14 × 5 = 70 tiles.

An 84 by 30 rectangle covered by 6 by 6 squaresFourteen columns and five rows of equal squares fill the rectangle. Each square has side 6 centimetres.84 cm: 14 squaresEach small square is 6 cm × 6 cm30cm
Fourteen squares along the long side and five along the short side make 70 tiles.

Prime factors give another way to find a gcd: take the smaller exponent of each prime in the two numbers. Here an exponent counts how many times a prime occurs. For instance, 18 = 2 × 3² and 30 = 2 × 3 × 5 share one 2 and one 3, giving gcd 6. Extra copies that occur in only one number cannot belong to a common divisor.

Consecutive integers

If d divides both n and n + 1, it divides their difference, 1. The only positive divisor of 1 is 1. Therefore consecutive positive integers are coprime. This short difference argument often avoids any actual division.

Gcd and common multiple are different

A common divisor is no larger than either positive number; a positive common multiple is at least as large as both. Also, gcd(a, b) = 1 does not mean either number is prime. State the domain and ask whether the problem needs a shared divisor or a shared multiple before calculating.

Practise at your next step

A six-question session chooses from nine questions. Two correct answers in a row without hints move you up a level; an incorrect answer brings a simpler next question where one is available. Hints keep you at the same level. This is a practice suggestion, not an exam score or proof of mastery.

Interactive practice loads here. You can also use the complete question set below.

Write a proof of your own

For a positive integer n, prove that gcd(n, 2n + 1) = 1.

Write your reasoning on paper before comparing. The practice checker does not grade a written proof.

Compare your proof with a full solution

Let d be any positive common divisor of n and 2n + 1. Since d divides n, it divides 2n as well. It therefore divides the difference (2n + 1) − 2n = 1. This forces d = 1. The only positive common divisor is 1, so the gcd is 1.

Check: did you state the assumptions, explain the key step, and reach the requested conclusion?

All nine practice questions, hints and solutions

This complete set works without the interactive practice. Hide each solution until you have made an attempt.

1. What is gcd(12, 18)?

Foundation

  1. 2
  2. 3
  3. 6
  4. 12
Hint

List the positive divisors shared by both numbers.

Answer and explanation

6. The common divisors are 1, 2, 3 and 6. The greatest is 6, so gcd(12, 18) = 6.

2. Which pair is coprime?

Foundation

  1. 8 and 15
  2. 8 and 12
  3. 9 and 15
  4. 10 and 25
Hint

Coprime means that the greatest common divisor is 1.

Answer and explanation

8 and 15. The prime factors of 8 are all 2, while the prime factors of 15 are 3 and 5. They share no prime factor, so their gcd is 1. The other pairs share 4, 3 and 5 respectively.

3. What is gcd(25, 0)?

Foundation

  1. 0
  2. 1
  3. 5
  4. 25
Hint

Every positive integer divides 0. Which is the largest divisor of 25?

Answer and explanation

25. The positive divisors common to 25 and 0 are precisely the positive divisors of 25. The greatest is 25.

4. What is gcd(90, 36)?

Core

  1. 6
  2. 9
  3. 18
  4. 36
Hint

Divide 90 by 36 first.

Answer and explanation

18. 90 = 2 × 36 + 18 and 36 = 2 × 18. The last nonzero remainder is 18, so gcd(90, 36) = 18.

5. What is gcd(35, 36)?

Core

  1. 1
  2. 5
  3. 6
  4. 35
Hint

Any common divisor must divide the difference.

Answer and explanation

1. A common divisor of 35 and 36 divides 36 − 35 = 1. Therefore their only positive common divisor is 1.

6. A 24 cm by 18 cm rectangle is tiled with the largest possible equal square tiles, with integer side length, parallel edges and no cutting. What is each tile’s side length?

Core

  1. 3 cm
  2. 6 cm
  3. 9 cm
  4. 12 cm
Hint

The side length must divide both rectangle dimensions.

Answer and explanation

6 cm. The largest possible side is gcd(24, 18). Since 24 = 18 + 6 and 18 = 3 × 6, the gcd is 6. Tiles of side 6 cm fit in 4 rows by 3 columns.

7. What is gcd(252, 105)?

Stretch

  1. 7
  2. 14
  3. 21
  4. 35
Hint

Follow the remainders: 252 divided by 105, then 105 divided by that remainder.

Answer and explanation

21. 252 = 2 × 105 + 42; 105 = 2 × 42 + 21; 42 = 2 × 21. The last nonzero remainder is 21, which is the gcd.

8. For a positive integer n, what is gcd(n, 3n + 1)?

Stretch

  1. 1
  2. 3
  3. n
  4. It is always larger than 1
Hint

Subtract three copies of n from 3n + 1.

Answer and explanation

1. A positive common divisor of n and 3n + 1 divides (3n + 1) − 3n = 1. It must therefore be 1. This proves the claim for every positive integer n.

9. If gcd(a, b) = 5 for positive integers a and b, what is gcd(3a, 3b)?

Stretch

  1. 3
  2. 5
  3. 8
  4. 15
Hint

Multiplying both numbers by 3 multiplies their gcd by 3. Justify this using prime factors.

Answer and explanation

15. In a prime factorisation, the gcd takes the smaller exponent of each prime. Multiplying both numbers by 3 adds one to both exponents of 3, so it adds one to their smaller exponent and leaves the others unchanged. The gcd is therefore 3 × 5 = 15.

Where to go next

Move on to the mixed proof-practice plan · Explore the wider Olympiad topic map

Teaching examples prepared for this guide, not attributed to a contest paper. Familiar elementary problems may appear in other learning materials. Report an unclear step or an error.