Discrete Math › Section G · Additional topics › Topic G.3

GCD, congruences, and modular arithmetic

The greatest common divisor and arithmetic with remainders are the working tools of number theory. One fast, very old algorithm computes the gcd, and the same calculation, run backwards, solves equations in which only remainders matter.

Arithmetic that wraps around

If it is 9 o'clock now, in 50 hours it will be 11 o'clock, because \(9 + 50 = 59\) and \(59 = 4 \cdot 12 + 11\): only the remainder on division by 12 matters. That is modular arithmetic, and it is everywhere in computing, from hash tables and check digits to encryption. To work with it properly we first need the greatest common divisor, which decides when division is possible in modular arithmetic. This topic builds on the divisibility, division algorithm and primes of "Divisibility and primes".

Greatest common divisor

The greatest common divisor \(\gcd(a, b)\) of two integers, not both zero, is the largest integer dividing both. So \(\gcd(864, 210) = 6\). Integers with \(\gcd(a, b) = 1\) are coprime, or relatively prime, such as 8 and 15, even though neither is prime. The least common multiple \(\mathrm{lcm}(a, b)\) is the smallest positive common multiple. For positive integers,

\gcd(a, b) \cdot \mathrm{lcm}(a, b) = ab

so \(\mathrm{lcm}(864, 210)\) is \(\frac{864 \cdot 210}{6} = 30{,}240\). Prime factorisations give the gcd too, but factorising large numbers is slow, so we need a better method.

The Euclidean algorithm

The key fact is \(\gcd(a, b) = \gcd(b, r)\), where \(r\) is the remainder when \(a\) is divided by \(b\). It holds because \(a = bq + r\): any common divisor of \(a\) and \(b\) divides \(r = a - bq\), and any common divisor of \(b\) and \(r\) divides \(a\), so both pairs have exactly the same common divisors. Repeat the replacement \((a, b) \to (b, r)\) until the remainder is 0; the last non-zero remainder is the gcd. The numbers shrink quickly. Lamé's theorem says the number of division steps is at most five times the number of digits of the smaller number, so even two 300-digit numbers need at most 1,500 steps.

Worked example: gcd and Bezout coefficients

Find \(\gcd(864, 210)\) and write it as \(864x + 210y\). 1. \(864 = 4 \cdot 210 + 24\). 2. \(210 = 8 \cdot 24 + 18\). 3. \(24 = 1 \cdot 18 + 6\). 4. \(18 = 3 \cdot 6 + 0\), so the gcd is 6, the last non-zero remainder. 5. Back-substitute, starting from step 3, then replacing 18 using step 2:

6 = 24 - 18 = 24 - (210 - 8 \cdot 24) = 9 \cdot 24 - 210

6. Replace 24 using step 1:

6 = 9(864 - 4 \cdot 210) - 210 = 9 \cdot 864 - 37 \cdot 210

7. Check: \(7776 - 7770 = 6\). So \(x = 9\) and \(y = -37\).

Bezout's identity and Euclid's lemma

Running the Euclidean algorithm backwards, as above, always works, so for any integers \(a\) and \(b\), not both zero, there are integers \(x\) and \(y\) with \(ax + by = \gcd(a, b)\). This is Bezout's identity, and the backwards calculation is the extended Euclidean algorithm. A key consequence is Euclid's lemma: if a prime \(p\) divides \(ab\), then \(p \mid a\) or \(p \mid b\). Proof: if \(p \nmid a\), then \(\gcd(p, a) = 1\), so \(px + ay = 1\) and \(b = pbx + aby\), which \(p\) divides. This lemma supplies the uniqueness half of the fundamental theorem of arithmetic.

Congruences

For a positive integer \(n\), write \(a \equiv b \pmod{n}\), read "\(a\) is congruent to \(b\) modulo \(n\)", when \(n \mid a - b\). Equivalently, \(a\) and \(b\) leave the same remainder on division by \(n\). So \(38 \equiv 3 \pmod 7\), since \(38 - 3 = 35\), and \(-4 \equiv 3 \pmod 7\) as well. Congruence modulo \(n\) is an equivalence relation, in the sense of "Equivalence relations and partitions", and it splits \(\mathbb{Z}\) into \(n\) remainder classes. Modulo 4 these are the integers leaving remainders 0, 1, 2 and 3; every integer lies in exactly one class.

Calculating with congruences

If \(a \equiv b\) and \(c \equiv d \pmod n\), then \(a + c \equiv b + d\), \(a - c \equiv b - d\) and \(ac \equiv bd \pmod n\), so also \(a^k \equiv b^k\). You may reduce at every step and keep the numbers small. Division is different: \(2 \cdot 3 \equiv 2 \cdot 1 \pmod 4\), since 6 and 2 differ by 4, yet \(3 \not\equiv 1 \pmod 4\). Cancelling a factor \(c\) is safe only when \(\gcd(c, n) = 1\). For the last digit of \(7^{2026}\), work mod 10: the powers of 7 run 7, 9, 3, 1 and then repeat. Since \(2026 = 4 \cdot 506 + 2\), \(7^{2026} \equiv 7^2 \equiv 9\), so the last digit is 9.

Worked example: solving a linear congruence

Solve \(5x \equiv 3 \pmod{12}\). 1. Since \(\gcd(5, 12) = 1\), 5 has an inverse modulo 12: a number \(u\) with \(5u \equiv 1\). 2. Find it: \(5 \cdot 5 = 25 = 2 \cdot 12 + 1\), so \(u = 5\). For larger numbers, the extended Euclidean algorithm finds \(u\). 3. Multiply both sides by 5: \(x \equiv 15 \equiv 3 \pmod{12}\). 4. Check: \(5 \cdot 3 = 15 \equiv 3 \pmod{12}\). The solutions are all \(x = 3 + 12t\). In general, \(a\) has an inverse modulo \(n\) exactly when \(\gcd(a, n) = 1\), and then \(ax \equiv b\) has a single solution modulo \(n\).

Linear Diophantine equations

An equation \(ax + by = c\) in which \(x\) and \(y\) must be integers is a linear Diophantine equation. It has solutions exactly when \(\gcd(a, b) \mid c\). If \(g = \gcd(a, b)\) does divide \(c\), scale Bezout's identity by \(\frac{c}{g}\). For \(864x + 210y = 30\), multiply \(9 \cdot 864 - 37 \cdot 210 = 6\) by 5 to get \(x = 45\), \(y = -185\). Every solution is then \(x = 45 + 35t\), \(y = -185 - 144t\), where \(35 = \frac{210}{6}\) and \(144 = \frac{864}{6}\). By contrast, \(864x + 210y = 31\) has no integer solutions, since 6 does not divide 31.

Fermat's little theorem

If \(p\) is prime and \(p \nmid a\), then

a^{p-1} \equiv 1 \pmod p

For example, \(2^{12} = 4096 = 13 \cdot 315 + 1\), so \(2^{12} \equiv 1 \pmod{13}\). The theorem tames huge powers. To find \(3^{100} \bmod 7\), use \(3^6 \equiv 1\): since \(100 = 6 \cdot 16 + 4\), \(3^{100} \equiv 3^4 = 81 \equiv 4 \pmod 7\). It also gives a quick screening test: if \(a^{n-1} \not\equiv 1 \pmod n\) for some \(a\) coprime to \(n\), then \(n\) is certainly composite, although passing the test does not prove \(n\) prime. It also explains why RSA decryption works, as the topic "Cryptography: number theory at work" shows.

Common mistakes to avoid

First, taking the last remainder, 0, as the gcd: the gcd is the last non-zero remainder. Second, slipping signs when back-substituting; always check \(ax + by\) at the end. Third, cancelling a factor that shares a divisor with the modulus. Fourth, looking for an inverse of \(a\) modulo \(n\) when \(\gcd(a, n) > 1\): none exists. Fifth, using Fermat's little theorem with a composite modulus, or with \(p \mid a\). Sixth, solving \(ax + by = c\) without first checking that the gcd divides \(c\).

Key takeaways

\(\gcd(a, b) = \gcd(b, a \bmod b)\), so the Euclidean algorithm finds the gcd quickly, and running it backwards gives Bezout's identity \(ax + by = \gcd(a, b)\). That identity proves Euclid's lemma and decides when \(ax + by = c\) has integer solutions. \(a \equiv b \pmod n\) means \(n \mid a - b\); congruences can be added, subtracted, multiplied and raised to powers, but cancelled only by numbers coprime to \(n\). An inverse modulo \(n\) exists exactly when \(\gcd(a, n) = 1\). Fermat: \(a^{p-1} \equiv 1 \pmod p\).

Flashcards

Flashcard

gcd(a, b)

The largest integer dividing both a and b

gcd(864, 210) = 6.

Test your understanding

Question 1 of 5

What is gcd(252, 198)?

Question 2 of 5

What is the inverse of 7 modulo 10?

Question 3 of 5

What is the remainder when 2⁵⁰ is divided by 7?

Question 4 of 5

Which of these equations has a solution in integers x and y?

Question 5 of 5

Which congruence is true?

← Previous topicNext topic →