Computational number theory begins with a deceptively simple question: how can exact statements about integers become procedures that are fast, checkable and reusable?

The Euclidean algorithm is one of the clearest answers. It finds greatest common divisors without factoring the inputs first. Its extended form does something even more useful: it writes the gcd as an integer combination of the original numbers. From that one mechanism come modular inverses, linear congruences, Diophantine equations and much of the arithmetic machinery used by later algorithms.

This guide develops the method from first principles, proves why it works, follows the data carried by the algorithm, and shows how to verify every important output. It is Guide 1 in the Bukit Timah Tutor Computational Number Theory series. Use the BTT Mathematics Hub for the wider Mathematics route.

Integer problem → invariant → algorithm → certificate → verification.

1. The gcd is a structural object

For integers a and b, not both zero, the greatest common divisor gcd(a,b) is the positive integer d such that d divides both a and b, and every common divisor of a and b divides d.

For example, gcd(84,30)=6. Factoring gives 84=2²·3·7 and 30=2·3·5, so the common prime factors produce 6. That approach works, but it quietly assumes factorisation is easy. For large integers, factorisation can be much harder than gcd computation.

The Euclidean algorithm avoids factorisation through one invariant:

gcd(a,b)=gcd(b,a mod b).

If a=qb+r, then a and b have exactly the same common divisors as b and r. Any common divisor of a and b divides a−qb=r. Conversely, any common divisor of b and r divides qb+r=a. The visible pair changes, but the gcd does not.

2. Euclid’s algorithm

while b ≠ 0:
    (a, b) ← (b, a mod b)
return |a|

Every nonzero remainder is smaller than the divisor that produced it. The positive remainders therefore form a strictly decreasing sequence, so the process must terminate.

Worked example: gcd(1071,462)

1071 = 2(462) + 147
462  = 3(147) + 21
147  = 7(21)  + 0

Therefore gcd(1071,462)=21.

The algorithm did not need the prime factorisations 1071=3²·7·17 and 462=2·3·7·11. It found the gcd directly through repeated remainder reduction.

3. Why the Euclidean algorithm is efficient

The algorithm is fast because the remainders shrink. Consecutive Fibonacci numbers produce the slowest quotient pattern, yet even then the number of divisions grows only on the order of the number of digits of the inputs.

This introduces a central computational distinction. An integer n may be huge numerically, but its binary input length is only about log₂n bits. Complexity should therefore be measured against bit length rather than against the magnitude n itself.

Gcd computation is polynomial-time in the input bit lengths. This remains practical even in settings where complete integer factorisation would be far more expensive.

4. Bézout identity

The extended Euclidean algorithm finds not only d=gcd(a,b), but also integers x and y satisfying

ax+by=d.

This is Bézout’s identity. The coefficients are generally not unique, but one valid pair is enough to certify the relation.

Back-substitution for 1071 and 462

21 = 462 − 3(147)
147 = 1071 − 2(462)

21 = 462 − 3[1071 − 2(462)]
   = 7(462) − 3(1071).

21=(−3)(1071)+7(462).

That identity can be checked immediately and serves as a certificate for the gcd computation.

5. Carrying Bézout coefficients forward

Instead of storing the division chain and back-substituting afterward, an implementation can update the coefficients at the same time as the remainders.

old_r = a,   r = b
old_s = 1,   s = 0
old_t = 0,   t = 1

while r ≠ 0:
    q = old_r div r
    (old_r, r) = (r, old_r − q r)
    (old_s, s) = (s, old_s − q s)
    (old_t, t) = (t, old_t − q t)

return (old_r, old_s, old_t)

At every stage, the current remainders remain integer combinations of the original inputs. At termination, old_r is the gcd and

a·old_s+b·old_t=old_r.

6. Modular arithmetic

We write a≡b (mod n) when n divides a−b. Equivalently, a and b have the same remainder modulo n.

Congruence respects addition and multiplication, so residues can replace large integers while preserving modular calculations. Division is more delicate because not every nonzero residue has a multiplicative inverse.

7. When does a modular inverse exist?

An integer a has an inverse modulo n if there is an integer x satisfying

ax≡1 (mod n).

Such an inverse exists exactly when gcd(a,n)=1.

If gcd(a,n)=1, Bézout gives ax+ny=1, and reducing modulo n leaves ax≡1. Conversely, if ax≡1 (mod n), then ax−ny=1 for some integer y; any common divisor of a and n must divide 1, so the gcd is 1.

Invertible modulo n ⇔ coprime to n.

8. Worked modular inverse: 17⁻¹ mod 43

43 = 2(17) + 9
17 = 1(9) + 8
9 = 1(8) + 1

Back-substitute:

1 = 9 − 8
  = 2(9) − 17
  = 2(43 − 2·17) − 17
  = 2·43 − 5·17.

Therefore 17⁻¹≡−5≡38 (mod 43). Check: 17·38=646=15·43+1.

9. Solving linear congruences

Consider ax≡b (mod n). Let d=gcd(a,n). A solution exists if and only if d divides b.

If d∤b, every integer of the form ax−ny is divisible by d while b is not, so the congruence is impossible. If d|b, divide by d to obtain

a' x ≡ b' (mod n')
where a'=a/d, b'=b/d, n'=n/d.

Now gcd(a’,n’)=1, so a’ has an inverse modulo n’.

Example: 14x≡8 (mod 30)

gcd(14,30)=2 and 2 divides 8. Divide by 2:

7x ≡ 4 (mod 15).

The inverse of 7 modulo 15 is 13, so x≡13·4≡52≡7 (mod 15). Modulo 30 this gives two solutions, x≡7 and x≡22.

10. Linear Diophantine equations

The integer equation ax+by=c has a solution if and only if gcd(a,b) divides c.

If d=gcd(a,b) and ax₀+by₀=d, then multiplying by c/d gives one solution. All solutions are

x = x₁ + (b/d)t
y = y₁ − (a/d)t
for t ∈ ℤ.

This connects directly to congruences because ax≡b (mod n) means ax−ny=b for some integer y.

11. Example: solve 35x+22y=1

35 = 1(22)+13
22 = 1(13)+9
13 = 1(9)+4
9  = 2(4)+1

Back-substitution gives

1 = 8·22 − 5·35.

So x=−5,y=8 is one solution. All solutions are x=−5+22t and y=8−35t. As a modular consequence, 35⁻¹≡17 (mod 22).

12. Cancellation in modular arithmetic

From ac≡bc (mod n), cancellation of c is valid when c is invertible modulo n, equivalently when gcd(c,n)=1.

For example, 2·1≡2·4 (mod 6), because 2≡8 (mod 6). But 1 is not congruent to 4 modulo 6. The factor 2 cannot be cancelled because gcd(2,6)=2.

Before dividing modulo n, prove the divisor has an inverse.

13. Certificates and independent checking

Claimed gcd d: verify d divides both inputs and check a Bézout equation ax+by=d.
Claimed inverse x: compute ax mod n and confirm the remainder is 1.
Claimed impossible congruence: compute d=gcd(a,n) and verify d does not divide b.
Claimed Diophantine solution: substitute directly.

The difference between finding and checking will recur throughout computational number theory. Some objects are difficult to discover but easy to verify once a certificate is supplied.

14. Signs, zero and normalisation

gcd(a,0)=|a| for a≠0.
gcd(0,b)=|b| for b≠0.
gcd(a,b)=gcd(|a|,|b|).
Moduli are normally taken positive.
A negative Bézout coefficient can be reduced modulo n to obtain the least nonnegative inverse representative.

Software conventions for gcd(0,0) vary, so an implementation should state its behaviour explicitly rather than relying on an unstated convention.

15. A table method

For longer calculations, store rows (r,s,t) satisfying r=sa+tb. Begin with

r      s      t
----------------
a      1      0
b      0      1

Whenever the remainder step replaces an old row by old−q·current, apply the same update to s and t. The linear-combination invariant survives automatically.

16. Common mistakes

Assuming every nonzero residue is invertible. The test is gcd(a,n)=1.
Dividing a congruence without adjusting the modulus. When a common gcd d is removed, the modulus becomes n/d.
Rejecting a negative inverse. It is valid; reduce modulo n if a nonnegative representative is desired.
Using the quotient instead of the remainder in Euclid’s update. The invariant is then lost.
Checking only the final gcd. The Bézout identity is an inexpensive stronger check.

17. Practice set

Compute gcd(252,198) using Euclid’s algorithm.
Find integers x,y such that 252x+198y=gcd(252,198).
Determine whether 21 has an inverse modulo 55. If it does, find it.
Solve 12x≡18 (mod 30).
Determine whether 15x≡7 (mod 35) has a solution.
Find the inverse of 37 modulo 101.
Solve 37x≡12 (mod 101).
Find one integer solution to 84x+33y=3.
State all solutions to 84x+33y=3.
Explain why cancellation by 6 is invalid modulo 15.
Compute gcd(987654,123456).
Show that any common divisor of a and b divides every integer combination ax+by.

18. Answers and worked checks

1. 252=1·198+54; 198=3·54+36; 54=1·36+18; 36=2·18. Hence gcd=18.

2. 18=4·252−5·198, so x=4,y=−5.

3. gcd(21,55)=1 and 21·21−55·8=1, so 21⁻¹≡21 (mod 55).

4. gcd(12,30)=6 and 6|18. Reduce to 2x≡3 (mod 5), so x≡4 (mod 5). Modulo 30 the six solutions are 4,9,14,19,24,29.

5. gcd(15,35)=5 but 5∤7, so there is no solution.

6. Extended Euclid gives 1=11·101−30·37, so 37⁻¹≡−30≡71 (mod 101). Check: 37·71=2627=26·101+1.

7. x≡12·71=852≡44 (mod 101). Check: 37·44=1628≡12.

8. 3=2·84−5·33, so one solution is x=2,y=−5.

9. All solutions are x=2+11t and y=−5−28t for t∈ℤ.

10. gcd(6,15)=3≠1, so 6 has no multiplicative inverse modulo 15 and cannot generally be cancelled.

11. 987654=8·123456+6 and 123456 is divisible by 6, so gcd=6.

12. If d|a and d|b, write a=dm and b=dn. Then ax+by=d(mx+ny), so d divides every integer combination.

19. What Euclid teaches about algorithmic number theory

Invariant: preserve the gcd while shrinking the visible problem.
Reduction: replace a large pair by a smaller equivalent pair.
Termination: prove that the decreasing positive remainder sequence must stop.
Certificate: use Bézout coefficients to validate the result.
Reuse: turn one mechanism into inverses, congruence solvers and Diophantine solvers.
Complexity: measure the cost against input length, not raw integer magnitude.

The next guide applies the same discipline to enormous powers and systems of congruences.

20. Continue the Computational Number Theory series

Guide 1: Euclidean Algorithm, Bézout Identity and Modular Inverses
Guide 2: Fast Modular Exponentiation and the Chinese Remainder Theorem
Guide 3: Prime Sieves, Probable Primes and Primality Testing
Guide 4: Integer Factorisation, Pollard Methods and Computational Limits

Return to the Singapore Mathematics Hub for the wider BTT Mathematics library.

Small Group Tutorials

Computational Number Theory 1: Euclidean Algorithm, Bézout Identity and Modular Inverses