Greatest common divisors and Euclid’s algorithm

Make the largest equal packets that fit both totals

You have 12 blue counters and 18 orange counters. Each packet must contain counters of just one colour, every packet must contain the same positive whole number of counters, and none may remain. Packet sizes 1, 2, 3 and 6 work for both totals. Size 6 is largest: it gives two blue packets and three orange packets. A size that fits 12 alone, such as 4, is not enough.

The greatest common divisor records that largest shared size. Listing all divisors works for small numbers; remainder steps will find the answer without first factoring either input. The counters motivate positive inputs, but the integer definitions below also cover negative numbers and zero.

Useful preparation is whole-number division with remainders, negative numbers and absolute value, reading equality in both directions, and distributing signed products. The linked published lessons supply those skills. Divisibility, common divisors, integer combinations and the algorithm are defined here; later number-theory lessons are optional.

On a first reading, follow the packet example, the two-way remainder argument and the 48-and-18 algorithm. Then try one signed or zero case. Return to the coefficient invariant, minimal-positive-combination proof and least-common-multiple proof after you can explain why a remainder step preserves every common divisor.

Divisibility means an exact integer multiple

For integers d and n, write d | n when n = dk for some integer k. Read this as d divides n. Thus 3 | 12 because 12 = 3×4, and 3 | −12 because −12 = 3×(−4). But 5 does not divide 12: its quotient is not an integer. Divisibility is a statement, not a division operation.

We allow d = 0 in this definition: 0 | n holds exactly when n = 0. In particular 0 | 0 is true, although the quotient 0/0 is undefined. Every nonzero integer divides 0 because 0 = d×0. A positive divisor means d ≥ 1, so zero itself will never be a candidate packet size.

Changing a sign does not change the positive divisors. For example, d | a exactly when d | −a, since negating the multiplier reverses the sign. The absolute value |a| is a when a ≥ 0 and −a when a < 0. We may therefore find positive common divisors using |a| and |b|.

If d divides a and b, it divides every integer combination ax+by: write a = du and b = dv to get ax+by = d(ux+vy). The coefficients x and y may be negative or zero. This simple closure fact will justify both the remainder argument and the Bézout proof.

State what greatest means, and separate the zero convention

If a and b are not both zero, gcd(a,b) is their greatest positive common divisor. Such a divisor exists: 1 is common, and the positive divisors of any nonzero input n are at most |n|, so the common positive candidates form a nonempty finite set. We always choose the nonnegative gcd, independent of input order or signs.

For a ≠ 0, gcd(a,0) = |a|. Every positive divisor of a also divides 0, and |a| is the largest positive divisor of a. Likewise gcd(0,b) = |b| when b ≠ 0. For (0,0), every positive integer is common; there is no greatest positive common divisor. We define gcd(0,0) = 0 by convention, rather than claiming zero is largest.

For 12 and 18, the complete common positive divisor list is 1,2,3,6, giving gcd 6. For 14 and 25 the only common positive divisor is 1. Listing the first twelve positive divisors of (0,0) illustrates the convention but cannot exhaust that infinite list.

A remainder is smaller than the positive divisor

For a nonnegative integer A and a positive integer B, division gives unique integers q ≥ 0 and r with A = qB+r and 0 ≤ r < B. Choose q as the greatest integer with qB ≤ A; this exists because the possible q values run from 0 to at most A. Then r = A−qB is nonnegative, and r ≥ B would allow one more full group, contradicting the choice of q.

For uniqueness, suppose A = qB+r = q′B+r′ with both remainders in [0,B). Then (q−q′)B = r′−r. The right side has absolute value less than B, so the integer q−q′ must be 0; hence q = q′ and r = r′. This is the division rule used by the algorithm after taking absolute values.

For 48 and 18, 48 = 2×18+12, with 0 ≤ 12 < 18. For 18 and 48, the first division is 18 = 0×48+18: a zero quotient is allowed. There is no remainder step with B = 0; the algorithm stops before trying to divide by zero.

The old and new pairs have exactly the same common divisors

Write A = qB+r with B > 0. If d | A and d | B, then d | r because r = A−qB. Conversely, if d | B and d | r, then d | A because A = qB+r. These are two directions: every old common divisor is retained, and no new one is added.

Consequently gcd(A,B) = gcd(B,r). For 48 = 2×18+12, the common positive divisors of (48,18) and (18,12) are both 1,2,3,6. The remainder may be smaller than the answer’s original inputs without changing the answer.

The rule preserves the whole common-divisor set, not just one divisor you happened to try. Showing that 6 divides both pairs checks that candidate, but would not rule out a larger candidate. The two-way argument proves the gcd equality generally.

Repeat until the second entry is zero

Start with (A,B) = (|a|,|b|), keeping the input order. If B = 0, return A immediately. Otherwise divide A = qB+r and replace (A,B) by (B,r). Repeat. If the first entry is smaller, the first quotient is zero; the next pair reverses their roles automatically.

Every active step has B > 0 and replaces it with r satisfying 0 ≤ r < B. Thus the positive second entries strictly decrease. Starting from a finite integer, they cannot decrease forever: after at most the starting B positive steps, the second entry is zero. This proves termination; the initial first entries need not form a decreasing sequence.

The invariant preserves the gcd at every step. At the terminal pair (G,0), the gcd is G when G > 0, and is 0 under the (0,0) convention. Therefore the returned first entry is the original nonnegative gcd. For inputs not both zero, G is the last nonzero remainder or initial nonzero entry, never the final zero remainder.

For (48,18), the divisions are 48 = 2×18+12, 18 = 1×12+6 and 12 = 2×6+0. The terminal pair is (6,0), so gcd(48,18) = 6. For (17,0), there are no division steps and the result is 17; for (0,0), there are no steps and the result is the chosen convention 0.

Reverse the remainder equations to recover the gcd

In the 48-and-18 example, the last nonzero remainder is 6 = 18−12. The preceding equation gives 12 = 48−2×18. Substituting that whole expression gives 6 = 18−(48−2×18) = −48+3×18. So the coefficients x = −1 and y = 3 satisfy 48x+18y = 6.

Bézout’s identity says that for every pair of integers a,b there exist integers x,y with ax+by = gcd(a,b). Negative coefficients are permitted: they describe subtraction, not a negative gcd. For (−48,18), the same value is (−48)×1+18×3 = 6. Changing an input sign requires changing its coefficient accordingly.

Coefficients need not be unique. For 12 and 18, both 12×(−1)+18×1 = 6 and 12×2+18×(−1) = 6. The algorithm produces one certificate, not the only possible pair. For (0,−18), coefficients (0,−1) give 18. For (0,0), choosing (0,0) gives the convention 0, but provides no positive combination.

Carry a coefficient certificate beside every remainder

To avoid repeated backwards substitution, keep a row (r,x,y) with the invariant r = ax+by. Initialise the rows (|a|,sgn(a),0) and (|b|,0,sgn(b)), where sgn(n) is 1 for n > 0, −1 for n < 0 and 0 for n = 0. Both initial equalities hold, including zero inputs.

If the previous two rows are (r₀,x₀,y₀) and (r₁,x₁,y₁) with r₁ > 0, let q be the division quotient and create (r₀−qr₁, x₀−qx₁, y₀−qy₁). Distributing gives a(x₀−qx₁)+b(y₀−qy₁) = r₀−qr₁, so the new row retains the invariant. Shift the two active rows forward and continue.

When the second active remainder becomes zero, take the first active row. Its remainder is the proven gcd, and its coefficients certify Bézout’s identity. This proves existence for all signed inputs, including the cases that start with a zero. The zero row remains in the table for checking the final division but is not the positive gcd row.

The table for (48,18) starts with (48,1,0) and (18,0,1), then gives (12,1,−2), (6,−1,3) and (0,3,−8). Check each equality using the original inputs. In particular, 48×3+18×(−8) = 0 verifies the terminal row rather than changing the answer to zero.

The gcd is the smallest positive integer combination

Let g = gcd(a,b) > 0. Since g divides a and b, it divides every integer combination ax+by. Any positive such combination is a positive multiple of g, hence at least g. Bézout’s identity supplies a combination equal to g. Therefore g is the least positive value among all integer combinations, not just the combinations displayed in a finite diagram.

The condition g > 0 excludes (0,0): all its combinations are zero, so there is no least positive combination. Coefficients are integers, not arbitrary real numbers; allowing fractional coefficients would change the claim. For 12 and 18, every integer combination is a multiple of 6 and one equals 6.

A prime is an integer greater than 1 whose only positive divisors are 1 and itself; a composite integer greater than 1 has another positive divisor. Integers are coprime, or relatively prime, when their gcd is 1. Equivalently they admit an integer combination ax+by = 1. For 14 and 25, 14×9+25×(−5) = 1 proves coprimality even though neither input is prime. Also (0,1) and (0,−1) are coprime; (0,0) is not.

A useful cancellation rule follows without prime factorisation. If gcd(u,v) = 1 and v | uk, choose integers s,t with us+vt = 1. Multiplying by k gives k = uks+vkt. Both terms on the right are divisible by v, so v | k. Without coprimality the conclusion can fail: 6 divides 4×3 but does not divide 3.

Common multiples answer a different question

A common multiple of a and b is an integer M with a | M and b | M. If a,b are both nonzero, their least common multiple lcm(a,b) is the smallest positive common multiple. For 4 and 6, the positive multiples first meet at 12. This is different from their gcd 2, which divides the inputs rather than being divisible by them.

Signs do not change the multiples. If either input is zero, their only common multiple is 0, because 0 | M forces M = 0. There is no positive common multiple; define lcm(a,0) = lcm(0,b) = 0, including lcm(0,0) = 0. This is another convention, not a least-positive claim.

For nonzero inputs let A = |a|, B = |b| and g = gcd(A,B). Write A = gu and B = gv with u,v positive integers. Any positive common divisor h of u and v would make gh a common divisor of A and B; maximality of g forces h ≤ 1. Thus gcd(u,v) = 1.

The number M = guv is a positive multiple of both A and B. Conversely, a positive common multiple N has N = Ak = guk for a positive integer k. Since B divides N, v divides uk; the coprime cancellation rule gives v | k. Thus M divides N, so N ≥ M. This proves M is the least positive common multiple.

Consequently lcm(a,b) = |ab|/gcd(a,b) when at least one input is nonzero: the nonzero proof gives it directly, and a single zero gives 0 divided by a positive gcd. Do not use the quotient for (0,0), where it would be 0/0. The product identity gcd(a,b)×lcm(a,b) = |ab| holds in every case under the stated conventions.

Check an exact certificate, including its domain

For a claimed gcd G > 0, check that G divides both inputs and find integer x,y with ax+by = G. Every common divisor then divides G, so none can be larger; this certifies the answer. A value that only divides both could be too small. For (0,0), use the explicit convention rather than this positive-certificate argument.

The explorer uses fixed small signed and zero cases. Its core accepts integer inputs of absolute value at most 10,000, rejects unsafe arithmetic before performing it, and keeps every remainder equation and coefficient equality exact. These implementation bounds do not restrict the integer theorems. Divisor tables are complete where stated; a finite list for (0,0) or a finite multiple window is labelled as a sample or prefix.

Before revealing a result, predict the largest shared divisor, terminal gcd, value of the integer combination or first positive shared multiple. Compare a sign change, reversed input order and a zero case. Explain why the answer or convention follows from the definition, not only from the drawn marker.

Worked examples

Try it yourself

1. Are 0 | 0, 0 | 5 and 5 | 0 true? Does any of this define a quotient 0/0?

   Show the answer and reasoning

   True, false and true respectively. The quotient 0/0 remains undefined.

   Divisibility asks whether an integer multiplier exists: 0 = 0×k, 5 cannot equal 0×k, and 0 = 5×0. A division quotient would need a unique value, which 0/0 does not have.

2. Find gcd(−20,30), gcd(−20,0) and gcd(0,0), explaining the zero cases.

   Show the answer and reasoning

   The values are 10, 20 and 0 respectively.

   The common positive divisors of 20 and 30 have maximum 10. Every positive divisor of −20 also divides 0, with maximum |−20| = 20. For (0,0), there is no largest positive common divisor; 0 is the convention.

3. Given 85 = 2×32+21, prove that (85,32) and (32,21) have the same common divisors.

   Show the answer and reasoning

   A common divisor of 85 and 32 divides 21 = 85−2×32; a common divisor of 32 and 21 divides 85 = 2×32+21.

   Both directions retain the whole set. Checking only that one chosen divisor survives would not prove equality of the gcds.

4. Complete Euclid’s algorithm for (85,32). Identify the returned value, not the final zero.

   Show the answer and reasoning

   85 = 2×32+21; 32 = 1×21+11; 21 = 1×11+10; 11 = 1×10+1; 10 = 10×1+0. The gcd is 1.

   The second entries 32,21,11,10,1,0 strictly decrease. Every replacement preserves the common-divisor set, and the terminal pair is (1,0).

5. For inputs (18,48), is the first quotient zero an error? What sequence of pairs follows?

   Show the answer and reasoning

   It is valid. The pairs are (18,48), (48,18), (18,12), (12,6), (6,0), so the gcd is 6.

   18 = 0×48+18 has remainder 18 smaller than divisor 48. Positive second entries strictly decrease even though the first entries initially increase.

6. For (48,18), the active rows are (18,0,1) and (12,1,−2). With q = 1, what next row preserves r = 48x+18y?

   Show the answer and reasoning

   The next row is (6,−1,3).

   Subtract the second row once from the first: remainder 18−12 = 6, x = 0−1 = −1, y = 1−(−2) = 3. Check −48+54 = 6.

7. Convert 48×(−1)+18×3 = 6 to a certificate for (−48,−18).

   Show the answer and reasoning

   Use coefficients (1,−3): (−48)×1+(−18)×(−3) = 6.

   Changing each input sign requires negating its matching coefficient. The gcd remains nonnegative and is still 6.

8. Could integers x,y satisfy 12x+18y = 3? Why does a finite search not suffice?

   Show the answer and reasoning

   No. Every such combination is divisible by 6, but 3 is not.

   The divisibility proof covers every integer coefficient pair, including pairs outside any displayed search. Bézout supplies the least positive combination 6.

9. Does coprime mean that both inputs are prime? Check (14,25), (0,−1) and (0,0).

   Show the answer and reasoning

   No. The first two pairs are coprime; (0,0) is not.

   14×9+25×(−5) = 1 and 0×0+(−1)×(−1) = 1 certify gcd 1. The convention gcd(0,0) = 0 is not 1. Both 14 and 25 are composite.

10. Find lcm(−8,12), lcm(0,12) and lcm(0,0). In which case is |ab|/gcd(a,b) undefined?

    Show the answer and reasoning

    The lcms are 24, 0 and 0. The quotient formula is undefined for (0,0) only.

    gcd(−8,12) = 4 gives |−96|/4 = 24. A single zero has positive gcd and gives 0. Both-zero inputs would give 0/0, so use the separate lcm convention.

11. Someone claims gcd(12,18) = 3 because 3 divides both. What is missing, and what proves the correct value?

    Show the answer and reasoning

    A common divisor could be too small. The correct gcd is 6, certified by divisibility and 12×(−1)+18×1 = 6.

    Every common divisor divides that combination 6. Since 6 itself divides both inputs, it is maximal. No integer combination can equal 3 because every combination is divisible by 6.

12. Why does repeated strict decrease prove termination here? Would a decreasing sequence of positive real numbers be enough?

    Show the answer and reasoning

    The second entries are nonnegative integers. A positive starting integer permits only finitely many smaller positive integers; positive real values could decrease forever.

    The remainder conditions include both 0 ≤ r < B and integrality. For example, 1,1/2,1/4,… stays positive and strictly decreases, so strict decrease alone without the integer domain would not prove termination.

What to carry forward

• For inputs not both zero, the gcd is the greatest positive common divisor; gcd(0,0) = 0 is an explicit convention.
• A remainder step preserves every common divisor in both directions, and its positive integer second entry strictly decreases.
• Extended rows keep r = ax+by, so the gcd row supplies exact signed Bézout coefficients.
• For a positive gcd, it is the least positive integer combination; gcd 1 is coprimality, not a requirement that the inputs be prime.
• The nonnegative gcd–lcm product is |ab|. Zero lcm cases are conventions, and the quotient formula excludes (0,0).