Paper
Part IILinear Block Codes

Integers and Modular Arithmetic

November 15, 202654 min readbeginner

Every code after parity computes with remainders. This chapter builds Euclid's algorithm, Bezout's identity, inverses, Fermat's and Euler's theorems and the Chinese remainder theorem, ending at the first finite field.

The previous chapter, Lab: A First Hardware Checker, closed on a tree of XOR gates that computes one parity bit, and on the remark that every code after parity needs arithmetic that parity hides. An XOR gate adds two bits and throws the carry away, so it already computes a remainder, the remainder on division by 2. This chapter makes that arithmetic explicit and carries it from the modulus 2 to any whole number.

A Hamming code checks several parity sums at once, an ISBN check digit is a weighted sum taken modulo 11, and a Reed–Solomon code solves equations in a finite field. All three rest on the same few facts about whole numbers, which division leaves which remainder, when a multiplication can be undone, and when a list of remainders pins down a single number.

The chapter covers division with remainder and the two conventions programming languages disagree on, Euclid's algorithm and how long it runs, and the extended algorithm that writes the greatest common divisor as a combination of its inputs. Congruences, inverses modulo nn, the theorems of Fermat and Euler and the Chinese remainder theorem follow, and the last section reaches the integers modulo a prime pp, the first finite field, with the integers modulo 2 built from XOR and AND gates.

Every number in the chapter is recomputed by ch13_integers_and_modular_arithmetic.py in the python/ folder of the companion repository ecc-book-lab, and the charts are drawn by ch13_charts.py in the same folder. The GNU Octave twin ch13_integers_and_modular_arithmetic.m prints the same lines, as The Octave Route explains.

01.Division with Remainder

Divide 17 by 5 in whole numbers and the answer is 3 with 2 left over, because 17=3⋅5+217 = 3 \cdot 5 + 2. The quotient 3 counts how many fives fit, and the remainder 2 is what is left, always smaller than 5. Every check digit and every code in this book computes with remainders like this one, so the first task is to pin down exactly what a remainder is, including for negative numbers, where programming languages disagree.

Divide −17-17 by 5. Python rounds the quotient down, toward minus infinity, so -17 // 5 is -4, -17 % 5 is 3, and divmod(-17, 5) returns both, and its documentation states that the remainder takes the sign of the divisor [1]. C rounds the quotient toward zero instead. Its standard requires that / discard the fractional part and that (a/b)*b + a%b equal a [2], so in C -17 / 5 is −3-3 and -17 % 5 is −2-2. Python's own math.fmod(-17, 5) follows C and returns -2.0 [3], and GNU Octave offers both, with mod(-17, 5) equal to 3 and rem(-17, 5) equal to −2-2 [4]. Figure 1 draws the two answers on a number line.

Two number lines from -20 to 20 with the multiples of 5 marked. On the top line, floored division as Python does it, 17 steps down to 15 and leaves remainder 2, and -17 steps down to -20 and leaves remainder 3, shown in green, so -17 = (-4) x 5 + 3. On the bottom line, truncated division as C does it, 17 again leaves 2, but -17 steps toward zero to -15 and leaves remainder -2, shown dashed, so -17 = (-3) x 5 - 2. floored division (Python // and %) -20 -15 -10 -5 0 5 10 15 20 -17 17 r = 2 17 = 3 x 5 + 2 r = 3 -17 = (-4) x 5 + 3 truncated division (C / and %) -20 -15 -10 -5 0 5 10 15 20 -17 17 r = 2 17 = 3 x 5 + 2 r = -2 -17 = (-3) x 5 - 2
Figure 1. Two ways to divide −17 by 5. Floored division always steps down to a multiple of 5 and leaves a remainder from 0 to 4, while truncated division steps toward zero and leaves a remainder with the sign of −17.

Both answers satisfy −17=q⋅5+r-17 = q \cdot 5 + r, since (−4)⋅5+3=−17(-4) \cdot 5 + 3 = -17 and (−3)⋅5−2=−17(-3) \cdot 5 - 2 = -17. They differ only in which multiple of 5 they step to. Floored division always steps down, here to −20-20, and leaves a remainder from 0 to 4. Truncated division steps toward zero, here to −15-15, and leaves a remainder with the sign of the number being divided. A third convention, Euclidean division, insists that the remainder is never negative, whatever the signs of the two numbers [5]. Table 1 sets the three side by side on all four sign patterns of 17 and 5.

Table 1. Floored, truncated and Euclidean division of by , each given as a quotient and remainder

aabbFlooredTruncatedEuclidean
175(3,2)(3, 2)(3,2)(3, 2)(3,2)(3, 2)
−17-175(−4,3)(-4, 3)(−3,−2)(-3, -2)(−4,3)(-4, 3)
17−5-5(−4,−3)(-4, -3)(−3,2)(-3, 2)(−3,2)(-3, 2)
−17-17−5-5(3,−2)(3, -2)(3,−2)(3, -2)(4,3)(4, 3)

Source: reproduced by ch13_integers_and_modular_arithmetic.py.

The three agree whenever both numbers are positive, which is why the difference goes unnoticed until a negative number turns up. Floored and truncated remainders are tied together by one rule. When the truncated remainder is not 0 and its sign differs from the sign of the divisor, the floored remainder is the truncated one plus the divisor, as in −2+5=3-2 + 5 = 3 for −17-17 by 5 and 2+(−5)=−32 + (-5) = -3 for 17 by −5-5. The companion script checks that rule for every aa and every nonzero bb from −30-30 to 30. This book always divides by a positive modulus, and for a positive modulus the floored and Euclidean conventions coincide, so the definition below is both.

With this definition 17 mod 5=217 \bmod 5 = 2 and −17 mod 5=3-17 \bmod 5 = 3. The operation is named mod⁡\operatorname{mod}, and when it is applied to two numbers it is written between them, as in a mod na \bmod n. The definition speaks of the quotient and the remainder, as if there were only one of each, and that needs a proof.

Proof. For existence, take q=⌊a/n⌋q = \lfloor a/n \rfloor, the largest integer not above a/na/n. Then q≤a/n<q+1q \le a/n < q + 1, and multiplying by the positive number nn gives qn≤a<qn+nqn \le a < qn + n. Setting r=a−qnr = a - qn therefore gives 0≤r<n0 \le r < n, which for whole numbers is 0≤r≤n−10 \le r \le n - 1. For uniqueness, suppose a=qn+r=q′n+r′a = qn + r = q'n + r' with both remainders between 0 and n−1n - 1. Subtracting gives (q−q′)n=r′−r(q - q')n = r' - r, so r′−rr' - r is a multiple of nn. But ∣r′−r∣≤n−1|r' - r| \le n - 1, and the only multiple of nn that small is 0, so r′=rr' = r, and then (q−q′)n=0(q - q')n = 0 gives q′=qq' = q. ■\blacksquare

The companion script confirms the theorem directly for every aa from −50-50 to 50 and every nn from 1 to 12, finding exactly one pair each time.

02.The Greatest Common Divisor

The divisors of 1147 are 1, 31, 37 and 1147, and the divisors of 899 are 1, 29, 31 and 899. The two lists share 1 and 31, so the largest number that divides both is 31. Listing divisors works for numbers this small, but it means trying candidates up to the square root of each number, which is hopeless for numbers hundreds of digits long. Euclid's algorithm finds the largest common divisor without factoring anything.

The algorithm rests on one observation, that a single division does not change the greatest common divisor.

Proof. Write a=qb+ra = qb + r with r=a mod br = a \bmod b. A number dd that divides aa and bb also divides r=a−qbr = a - qb, since both terms on the right are multiples of dd. A number dd that divides bb and rr also divides a=qb+ra = qb + r for the same reason. So the pairs (a,b)(a, b) and (b,r)(b, r) have exactly the same common divisors, and therefore the same largest one. ■\blacksquare

Applied again and again, the lemma replaces a pair by a smaller pair with the same greatest common divisor until the second number reaches 0, and gcd⁡(r,0)=r\gcd(r, 0) = r for r≥1r \ge 1, since every integer divides 0. On 1147 and 899 it takes six divisions.

1147=1⋅899+248,899=3⋅248+155,248=1⋅155+93,155=1⋅93+62,93=1⋅62+31,62=2⋅31+0.\begin{aligned} 1147 &= 1 \cdot 899 + 248, \\ 899 &= 3 \cdot 248 + 155, \\ 248 &= 1 \cdot 155 + 93, \\ 155 &= 1 \cdot 93 + 62, \\ 93 &= 1 \cdot 62 + 31, \\ 62 &= 2 \cdot 31 + 0. \end{aligned}
(2)

The last nonzero remainder, 31, is the greatest common divisor, as the lists of divisors said, and indeed 1147=31⋅371147 = 31 \cdot 37 and 899=31⋅29899 = 31 \cdot 29. Figure 2 draws the same computation as geometry. A rectangle 1147 wide and 899 tall loses one square of side 899, the strip left over loses three squares of side 248, and so on, until two squares of side 31 fill the last piece exactly. A square that tiles the last piece also tiles every piece before it, so its side divides both sides of the original rectangle.

Euclid's algorithm on 1147 and 899 drawn as squares cut from a rectangle a = 1147 across, b = 899 down 899 248 248 248 155 93 62 31 31 Squares of one size come from one division. Two green squares of side 31 end it.
Figure 2. Euclid's algorithm on 1147 and 899 as squares cut from a rectangle. The side of the last square, 31, divides every side before it, so it is the greatest common divisor. Data: computed by ch13_charts.py in the companion repository.

Proof. Each new remainder is smaller than the number it was divided by, so r1>r2>r3>⋯≥0r_1 > r_2 > r_3 > \cdots \ge 0. A strictly decreasing sequence of whole numbers cannot go on forever, so some remainder is 0. The lemma gives gcd⁡(ri−1,ri)=gcd⁡(ri,ri+1)\gcd(r_{i-1}, r_i) = \gcd(r_i, r_{i+1}) at every step, so gcd⁡(a,b)=gcd⁡(r0,r1)=gcd⁡(rn,rn+1)=gcd⁡(rn,0)=rn\gcd(a, b) = \gcd(r_0, r_1) = \gcd(r_n, r_{n+1}) = \gcd(r_n, 0) = r_n. ■\blacksquare

For 1147 and 899 the remainders are r2=248r_2 = 248 through r6=31r_6 = 31 and r7=0r_7 = 0, so n=6n = 6. How many divisions can the algorithm need in general? Each remainder is at least 1 smaller than the one before, which guarantees no more than bb divisions, a hopelessly loose bound. A sharper fact holds.

Proof. Note first that ri+1≤rir_{i+1} \le r_i, with equality possible only at the start, when a=ba = b. There are two cases. If ri+1≤ri/2r_{i+1} \le r_i / 2, then ri+2<ri+1≤ri/2r_{i+2} < r_{i+1} \le r_i / 2, because a remainder is smaller than the number divided by. If ri+1>ri/2r_{i+1} > r_i / 2, then ri+1r_{i+1} fits into rir_i exactly once, since twice it exceeds rir_i, so the quotient is 1 and ri+2=ri−ri+1<ri−ri/2=ri/2r_{i+2} = r_i - r_{i+1} < r_i - r_i/2 = r_i / 2. ■\blacksquare

On 1147 and 899 the lemma says 248<1147/2248 < 1147/2, 155<899/2155 < 899/2, 93<248/293 < 248/2, and so on down the list, and the companion script checks every such pair for these inputs and for the Fibonacci pair below.

Proof. Starting from r1=br_1 = b and r2<r1r_2 < r_1, the lemma halves the bound every two indices, so by induction ri≤b/2⌊(i−1)/2⌋r_i \le b / 2^{\lfloor (i-1)/2 \rfloor} for every i≥1i \ge 1. The last nonzero remainder satisfies rn≥1r_n \ge 1, so 2⌊(n−1)/2⌋≤b2^{\lfloor (n-1)/2 \rfloor} \le b, and taking logarithms, ⌊(n−1)/2⌋≤log⁡2b\lfloor (n-1)/2 \rfloor \le \log_2 b. The left side is an integer, so it is at most ⌊log⁡2b⌋\lfloor \log_2 b \rfloor. Since (n−1)/2<⌊(n−1)/2⌋+1(n-1)/2 < \lfloor (n-1)/2 \rfloor + 1, this gives n−1<2⌊log⁡2b⌋+2n - 1 < 2 \lfloor \log_2 b \rfloor + 2, and as nn is an integer, n≤2⌊log⁡2b⌋+2n \le 2 \lfloor \log_2 b \rfloor + 2. ■\blacksquare

For b=899b = 899 the bound allows 20 divisions, and the algorithm took 6. The companion script checks the bound for every aa and bb from 1 to 299. What matters is that the bound grows with the number of binary digits of bb rather than with bb itself, so doubling the length of the inputs at most doubles the bound on the number of divisions. That is what makes Euclid's algorithm practical on numbers far too large to factor.

The slowest inputs are consecutive Fibonacci numbers. The Fibonacci numbers F(k)F(k) start from F(1)=F(2)=1F(1) = F(2) = 1, and each later one is the sum of the two before it, F(k)=F(k−1)+F(k−2)F(k) = F(k-1) + F(k-2), which gives 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 and 144. For k≥4k \ge 4, dividing F(k)F(k) by F(k−1)F(k-1) gives quotient 1 and leaves F(k−2)F(k-2) as the remainder, so the algorithm walks down the sequence one step per division, the slowest descent of any input. Even so, two steps shrink a Fibonacci remainder by about ϕ2≈2.618\phi^2 \approx 2.618, where ϕ=(1+5)/2\phi = (1 + \sqrt{5})/2, rather than by the 2 the halving lemma guarantees, which is why the pair 4181 and 2584 below finishes in 17 divisions against the bound's 24. Lamé used these pairs in 1844 to bound the number of divisions by five times the number of decimal digits of the smaller input [6]. The companion script confirms the extreme case directly. Among all pairs with aa from 2 to 233 and bb below aa, the smallest aa that needs nn divisions is F(n+2)F(n+2), and the only pair with that aa is F(n+2)F(n+2) and F(n+1)F(n+1). Figure 3 plots the remainders of 1147 and 899 beside those of the Fibonacci pair 4181 and 2584.

Remainders of Euclid's algorithm on a log scale against the halving bound 1 10 100 1000 10000 0 2 4 6 8 10 12 14 16 18 index i of the remainder r_i r_i gcd 1 after 17 divisions gcd 31 after 6 divisions 4181, 2584 (Fibonacci) 1147, 899 halving bound, b halved every two steps
Figure 3. Remainders of Euclid's algorithm on 4181 and 2584 and on 1147 and 899, on a log scale, against the halving bound. The Fibonacci pair, with every quotient 1 but the last, needs 17 divisions. Data: computed by ch13_charts.py in the companion repository.

03.Bezout's Identity and the Extended Algorithm

Multiply 1147 by 11 and 899 by 14. The products are 12617 and 12586, and they differ by 31, so 31=11⋅1147−14⋅89931 = 11 \cdot 1147 - 14 \cdot 899. The greatest common divisor is a combination of the two numbers, with integer coefficients, one of them negative. That fact is what will later turn a division modulo nn into a multiplication, and the coefficients 11 and −14-14 come straight out of Euclid's algorithm.

The extended algorithm keeps, beside each remainder rir_i, two integers sis_i and tit_i with ri=sia+tibr_i = s_i a + t_i b. At the start this is trivial, since a=1⋅a+0⋅ba = 1 \cdot a + 0 \cdot b and b=0⋅a+1⋅bb = 0 \cdot a + 1 \cdot b. Each division computes ri+1=ri−1−qirir_{i+1} = r_{i-1} - q_i r_i with quotient qi=⌊ri−1/ri⌋q_i = \lfloor r_{i-1}/r_i \rfloor, and the same combination of the two rows above keeps the coefficients in step.

ri+1=ri−1−qi ri,si+1=si−1−qi si,ti+1=ti−1−qi ti,r0=a, r1=b,s0=1, s1=0,t0=0, t1=1.\begin{aligned} r_{i+1} &= r_{i-1} - q_i\, r_i, & s_{i+1} &= s_{i-1} - q_i\, s_i, & t_{i+1} &= t_{i-1} - q_i\, t_i, \\ r_0 &= a,\ r_1 = b, & s_0 &= 1,\ s_1 = 0, & t_0 &= 0,\ t_1 = 1. \end{aligned}
(5)

If ri−1=si−1a+ti−1br_{i-1} = s_{i-1} a + t_{i-1} b and ri=sia+tibr_i = s_i a + t_i b, then subtracting qiq_i times the second from the first gives ri+1=si+1a+ti+1br_{i+1} = s_{i+1} a + t_{i+1} b, so the identity passes from each pair of rows to the next. Table 2 runs the recurrence on 1147 and 899.

Table 2. The extended Euclidean algorithm on and , where every row satisfies

iirir_iqiq_isis_itit_i
0114710
1899101
224831−1-1
31551−3-34
49314−5-5
5621−7-79
631211−14-14
70−29-2937

Source: reproduced by ch13_integers_and_modular_arithmetic.py.

Row 6 holds the greatest common divisor with its coefficients, 11⋅1147−14⋅899=3111 \cdot 1147 - 14 \cdot 899 = 31. Row 7, where the remainder is 0, says −29⋅1147+37⋅899=0-29 \cdot 1147 + 37 \cdot 899 = 0, and its coefficients are, up to sign, the cofactors 29 and 37 from 899=31⋅29899 = 31 \cdot 29 and 1147=31⋅371147 = 31 \cdot 37. Adding row 7 to row 6 any number of times changes the coefficients without changing the combination, so s=11−29ks = 11 - 29k and t=−14+37kt = -14 + 37k work for every integer kk. The coefficients are not unique, and the algorithm simply returns one pair.

Proof. The set of positive values of sa+tbsa + tb is not empty, since it contains a2+b2a^2 + b^2, the value at s=as = a and t=bt = b. Let g=sa+tbg = sa + tb be its smallest element. Divide aa by gg to get a=qg+ra = qg + r with 0≤r≤g−10 \le r \le g - 1. Then r=a−q(sa+tb)=(1−qs)a+(−qt)br = a - q(sa + tb) = (1 - qs)a + (-qt)b is again a combination of aa and bb, and it is smaller than gg, so it cannot be positive, which leaves r=0r = 0 and g∣ag \mid a. The same argument gives g∣bg \mid b, so gg is a common divisor and g≤gcd⁡(a,b)g \le \gcd(a, b). In the other direction, gcd⁡(a,b)\gcd(a, b) divides aa and bb, so it divides sa+tb=gsa + tb = g, and a positive divisor of gg is at most gg. Hence g=gcd⁡(a,b)g = \gcd(a, b). ■\blacksquare

The companion script tries every ss and tt from −60-60 to 60 on 1147 and 899 and finds the smallest positive combination is 31, and for every aa and bb from 1 to 79 it checks that the extended algorithm writes gcd⁡(a,b)\gcd(a, b) as sa+tbsa + tb. The identity has a consequence used in almost every proof that follows.

Proof. Bezout's identity gives integers ss and tt with sm+tn=1sm + tn = 1. Multiplying by kk gives k=s(mk)+(tk)nk = s(mk) + (tk)n, and nn divides both terms on the right, so n∣kn \mid k. For the second statement, if pp does not divide mm, then gcd⁡(m,p)=1\gcd(m, p) = 1, because the only positive divisors of pp are 1 and pp, and the first statement gives p∣kp \mid k. ■\blacksquare

The prime is essential. The number 6 divides 36=4⋅936 = 4 \cdot 9, yet 4 mod 6=44 \bmod 6 = 4 and 9 mod 6=39 \bmod 6 = 3, so 6 divides neither factor. The companion script checks Euclid's lemma for every prime below 40.

04.Congruences

On a clock, 5 hours after 9 o'clock is 2 o'clock, because 9+5=14=1⋅12+29 + 5 = 14 = 1 \cdot 12 + 2. A clock with 12 marks forgets multiples of 12, and in the same way a clock with 5 marks forgets multiples of 5, so −17-17 and 3 land on the same mark, since both leave remainder 3 and their difference −17−3=−20-17 - 3 = -20 is a multiple of 5. Figure 4 shows both clocks. Two numbers that land on the same mark are called congruent, and arithmetic with them works almost exactly like ordinary arithmetic.

Two clock faces. The left clock has 12 marks, 0 at the top. A green arc starts at 9 and runs forward five steps through 10, 11, 0 and 1 to land on 2, because 9 + 5 = 14 leaves remainder 2 on division by 12. The right clock has 5 marks, 0 to 4. The mark 3 is circled in green, and both 3 and -17 land on it, because -17 - 3 = -20 is a multiple of 5. 0 1 2 3 4 5 6 7 8 9 10 11 +5 steps 9 + 5 = 14 = 1 x 12 + 2 so 9 + 5 lands on 2 modulo 12 0 1 2 3 4 -17 - 3 = -20 = (-4) x 5 so -17 and 3 land on the same mark modulo 5
Figure 4. Congruence as position on a clock. Two numbers are congruent modulo n when they land on the same mark of a clock with n marks.

The notation with three bars is Gauss's, introduced in his Disquisitiones Arithmeticae of 1801 [7]. So 14≡2(mod12)14 \equiv 2 \pmod{12} and −17≡3(mod5)-17 \equiv 3 \pmod{5}. A congruence is a statement about two numbers, while a mod na \bmod n is a number, and the two are tied together as follows.

Proof. Write a=qn+ra = qn + r and b=q′n+r′b = q'n + r' with both remainders from 0 to n−1n - 1. Then a−b=(q−q′)n+(r−r′)a - b = (q - q')n + (r - r'). If r=r′r = r', the difference is a multiple of nn. Conversely, if nn divides a−ba - b, it divides r−r′r - r', and as ∣r−r′∣≤n−1|r - r'| \le n - 1, that forces r−r′=0r - r' = 0. ■\blacksquare

The companion script finds that −17-17 and 3 both leave remainder 3 modulo 5, as the lemma requires. What makes congruences worth having is that they survive addition and multiplication.

Proof. Write a′=a+kna' = a + kn and b′=b+lnb' = b + ln for integers kk and ll. Then a′+b′=a+b+(k+l)na' + b' = a + b + (k + l)n and a′b′=ab+(al+bk+kln)na'b' = ab + (al + bk + kln)n, and in each case the difference from the original is a multiple of nn. ■\blacksquare

The theorem means a computation modulo nn can reduce at every step, and the numbers involved never need to grow past about n2n^2. Take 37⋅52 mod 737 \cdot 52 \bmod 7. Since 37 mod 7=237 \bmod 7 = 2 and 52 mod 7=352 \bmod 7 = 3, the product is congruent to 2⋅3=62 \cdot 3 = 6. Computed the long way, 37⋅52=192437 \cdot 52 = 1924, and 1924−6=19181924 - 6 = 1918 is a multiple of 7, so the remainder is 6 as predicted. The companion script checks the theorem for every modulus up to 12.

Powers benefit most. To find 313 mod 113^{13} \bmod 11, write the exponent in binary, 13=11012=8+4+113 = 1101_2 = 8 + 4 + 1, and square repeatedly, reducing each time. The powers 33, 323^2, 343^4 and 383^8 reduce to 3, 9, 4 and 5 modulo 11, since 81≡481 \equiv 4 and 42=16≡54^2 = 16 \equiv 5. Then 313=38⋅34⋅3≡5⋅4⋅3=60≡5(mod11)3^{13} = 3^8 \cdot 3^4 \cdot 3 \equiv 5 \cdot 4 \cdot 3 = 60 \equiv 5 \pmod{11}. The full power is 313=15943233^{13} = 1594323, which indeed leaves 5. This method, square and multiply, needs a number of steps that grows with the number of binary digits of the exponent, so it handles exponents with hundreds of digits.

Check digits are congruences. Distance, Detection and Correction defined the ISBN-10 check, which requires the ten digits x1,…,x10x_1, \dots, x_{10} of the number to satisfy ∑i=110(11−i) xi≡0(mod11)\sum_{i=1}^{10} (11 - i)\, x_i \equiv 0 \pmod{11}, with weights running from 10 down to 1 and a check value of 10 written X [8]. For 0-13-042672-5, the ISBN of Lin and Costello's textbook [9], the weighted terms are 0, 9, 24, 0, 24, 10, 24, 21, 4 and 5, which sum to 121=11⋅11≡0121 = 11 \cdot 11 \equiv 0. The Luhn formula on card numbers is the same idea modulo 10 [10], and on 3141592653 its terms sum to 40≡0(mod10)40 \equiv 0 \pmod{10}. Detecting an error means seeing a nonzero remainder. Correcting an erasure, as the next section shows, means solving a congruence for the missing digit, and that needs division.

05.Inverses Modulo nn

Modulo 7, 3⋅5=15≡13 \cdot 5 = 15 \equiv 1, so multiplying by 5 undoes multiplying by 3, and 5 behaves like 1/31/3. Every nonzero number modulo 7 has such a partner. The partners of 1, 2, 3, 4, 5 and 6 are 1, 4, 5, 2, 3 and 6. Modulo 6 the picture breaks. Twice anything is even, and every number congruent to 1 modulo 6 is odd, so no xx satisfies 2x≡1(mod6)2x \equiv 1 \pmod{6}. Worse, 2⋅3≡2⋅0(mod6)2 \cdot 3 \equiv 2 \cdot 0 \pmod{6}, since both sides are multiples of 6, yet 3≢03 \not\equiv 0, so a factor of 2 cannot be cancelled from both sides of a congruence modulo 6.

Modulo 6 the only units are 1 and 5, and 5 is its own inverse, since 5⋅5=25≡15 \cdot 5 = 25 \equiv 1. Which numbers are units is decided by the greatest common divisor.

Proof. If gcd⁡(a,n)=1\gcd(a, n) = 1, Bezout's identity gives sa+tn=1sa + tn = 1, and reducing modulo nn gives sa≡1sa \equiv 1, so ss is an inverse. Conversely, if ab≡1ab \equiv 1, then ab−1=knab - 1 = kn for some integer kk, so ab−kn=1ab - kn = 1, and any common divisor of aa and nn divides the left side and hence divides 1. For uniqueness, if ab≡1ab \equiv 1 and ab′≡1ab' \equiv 1, then b≡b(ab′)=(ba)b′≡b′(modn)b \equiv b(ab') = (ba)b' \equiv b' \pmod{n}. ■\blacksquare

The proof is also the method. To invert 29 modulo 37, run the extended algorithm on 37 and 29. Its quotients are 1, 3, 1, 1, 1 and 2, the same as for 1147 and 899, because those numbers are 31⋅3731 \cdot 37 and 31⋅2931 \cdot 29 and every remainder is simply 31 times smaller, 8, 5, 3, 2, 1 and 0. The coefficients are therefore the same too, and 11⋅37−14⋅29=111 \cdot 37 - 14 \cdot 29 = 1. Reducing modulo 37 gives 29⋅(−14)≡129 \cdot (-14) \equiv 1, and −14 mod 37=23-14 \bmod 37 = 23, so the inverse of 29 is 23. As a check, 29⋅23=66729 \cdot 23 = 667 and 18⋅37=66618 \cdot 37 = 666. Python computes the same inverse as pow(29, -1, 37) [11], and the companion script checks the theorem for every modulus up to 40.

Proof. Multiply both sides by c−1c^{-1}, which exists by the theorem, and use the fact that congruence respects multiplication. ■\blacksquare

The failure modulo 6 is exactly the case gcd⁡(2,6)=2\gcd(2, 6) = 2, and the companion script checks cancellation for every modulus up to 30 and every cc coprime to it.

Inverses turn an erasure into a solved equation. Suppose the fifth digit of 0-13-042672-5 is smudged. Its weight is 11−5=611 - 5 = 6, and the other nine terms sum to 97, so the missing digit xx satisfies 97+6x≡0(mod11)97 + 6x \equiv 0 \pmod{11}, that is, 6x≡−97≡2(mod11)6x \equiv -97 \equiv 2 \pmod{11}. The inverse of 6 modulo 11 is 2, since 6⋅2=12≡16 \cdot 2 = 12 \equiv 1, so x≡2⋅2=4x \equiv 2 \cdot 2 = 4, and the smudged digit was 4. Because 11 is prime, every weight from 1 to 10 is a unit modulo 11, so any single erased digit of an ISBN-10 can be recovered this way. That is the reason for the prime modulus, and the same reasoning, with a larger finite field and many unknowns, is how a Reed–Solomon decoder fills in erasures.

06.Fermat's and Euler's Theorems

Table 3 lists the powers of each nonzero number modulo 7. Some rows reach 1 early, 2 and 4 at the third power and 6 at the second, but every row reaches 1 at the sixth power, and after that each row repeats.

Table 3. Powers of the nonzero residues modulo 7, for exponents from 1 to 6

aaa1a^1a2a^2a3a^3a4a^4a5a^5a6a^6
1111111
2241241
3326451
4421421
5546231
6616161

Source: reproduced by ch13_integers_and_modular_arithmetic.py.

The reason is visible in Figure 5. Multiplying the six nonzero residues 1 to 6 by 3 and reducing gives 3, 6, 2, 5, 1 and 4, the same six numbers in a different order. So the product of all six is unchanged, (3⋅1)(3⋅2)⋯(3⋅6)≡1⋅2⋯6(3 \cdot 1)(3 \cdot 2) \cdots (3 \cdot 6) \equiv 1 \cdot 2 \cdots 6, which reads 36⋅6!≡6!(mod7)3^6 \cdot 6! \equiv 6! \pmod{7}. Here 6!=720≡66! = 720 \equiv 6, a unit modulo 7, so it cancels and leaves 36≡13^6 \equiv 1.

Multiplication by 3 sends each nonzero residue modulo 7 to a different one k 3k mod 7 1 1 2 2 3 3 4 4 5 5 6 6 Every residue from 1 to 6 is hit once. The green arrow says 3 times 5 is 1 mod 7.
Figure 5. Multiplication by 3 rearranges the nonzero residues modulo 7. Multiplying all six together on both sides shows that the sixth power of 3 is 1 modulo 7. Data: computed by ch13_charts.py in the companion repository.

Proof. Consider the products a⋅1,a⋅2,…,a⋅(p−1)a \cdot 1, a \cdot 2, \dots, a \cdot (p-1) modulo pp. None is 0, because by Euclid's lemma pp would then divide aa or a number below pp. No two are equal, because ak≡ak′ak \equiv ak' gives k≡k′k \equiv k' by cancellation, as gcd⁡(a,p)=1\gcd(a, p) = 1. So the p−1p - 1 products are the numbers 1 to p−1p - 1 in some order, and multiplying them all together gives ap−1(p−1)!≡(p−1)!(modp)a^{p-1} (p-1)! \equiv (p-1)! \pmod{p}. The factorial is a product of units, hence a unit, and cancelling it leaves ap−1≡1a^{p-1} \equiv 1. ■\blacksquare

Proof. If pp divides aa, both sides are congruent to 0. Otherwise multiply both sides of Equation 7 by aa. ■\blacksquare

The companion script checks both statements for every prime below 60. Fermat's theorem needs a prime modulus. For a general modulus the right exponent counts the units.

The units modulo 12 are 1, 5, 7 and 11, so φ(12)=4\varphi(12) = 4. A prime has every smaller positive number as a unit, so φ(7)=6\varphi(7) = 6. The units modulo 9 are 1, 2, 4, 5, 7 and 8, so φ(9)=6\varphi(9) = 6, and φ(8)=4\varphi(8) = 4. For powers of a prime there is a closed form.

Proof. A number shares a factor greater than 1 with pkp^k exactly when pp divides it, since every divisor of pkp^k above 1 is a power of pp. Among 1 to pkp^k the multiples of pp are p,2p,…,pk−1⋅pp, 2p, \dots, p^{k-1} \cdot p, which is pk−1p^{k-1} numbers. The other pk−pk−1p^k - p^{k-1} numbers are the units. ■\blacksquare

So φ(9)=9−3=6\varphi(9) = 9 - 3 = 6 and φ(8)=8−4=4\varphi(8) = 8 - 4 = 4, matching the counts above, and the companion script checks the formula for every prime power up to 1000.

Proof. Let u1,…,umu_1, \dots, u_m be the units modulo nn, with m=φ(n)m = \varphi(n). Each product auia u_i is again a unit, with inverse ui−1a−1u_i^{-1} a^{-1}, and the products are distinct modulo nn by cancellation. So the products au1,…,auma u_1, \dots, a u_m reduced modulo nn are the units in some order, and multiplying them together gives amu1⋯um≡u1⋯uma^m u_1 \cdots u_m \equiv u_1 \cdots u_m. The product of the units is a unit, and cancelling it leaves am≡1a^m \equiv 1. ■\blacksquare

For a prime pp, φ(p)=p−1\varphi(p) = p - 1 and Euler's theorem is Fermat's. Modulo 9, the theorem says 26≡12^6 \equiv 1, and indeed 26=64=7⋅9+12^6 = 64 = 7 \cdot 9 + 1. Modulo 12, every unit has square 1, as 525^2, 727^2 and 11211^2 all leave 1, so the exponent φ(12)=4\varphi(12) = 4 works but is not always the smallest that does. The companion script checks the theorem for every modulus up to 60.

The theorems make huge exponents small. Since 36≡1(mod7)3^6 \equiv 1 \pmod{7} and 100=6⋅16+4100 = 6 \cdot 16 + 4, the power 3100=(36)16⋅34≡34=81≡4(mod7)3^{100} = (3^6)^{16} \cdot 3^4 \equiv 3^4 = 81 \equiv 4 \pmod{7}. They also give a second way to invert. Modulo a prime pp, for aa not divisible by pp, a⋅ap−2=ap−1≡1a \cdot a^{p-2} = a^{p-1} \equiv 1, so ap−2a^{p-2} is the inverse of aa. Modulo 11 the inverse of 6 is 696^9, and square and multiply, with 66, 626^2, 646^4 and 686^8 reducing to 6, 3, 9 and 4, gives 69=68⋅6≡4⋅6=24≡26^9 = 6^8 \cdot 6 \equiv 4 \cdot 6 = 24 \equiv 2, the same inverse that recovered the smudged ISBN digit. The full power 69=100776966^9 = 10077696 leaves 2 as well. The extended algorithm works for any modulus, while the power needs the totient, which for a prime is known in advance.

07.The Chinese Remainder Theorem

Find a number that leaves remainder 2 on division by 3 and remainder 3 on division by 5. The numbers that leave 3 modulo 5 are 3, 8, 13 and so on, and modulo 3 these leave 0, 2 and 1, so 8 is the answer. Among 0 to 14, 8 is the only one, and in fact each of the 15 possible pairs of remainders, modulo 3 and modulo 5, belongs to exactly one number from 0 to 14, as Figure 6 shows.

The numbers 0 to 14 placed by their remainders modulo 3 and modulo 5 x mod 5 x mod 3 0 1 2 3 4 0 1 2 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Each of the 15 cells holds exactly one x from 0 to 14. Row 2, column 3 holds 8.
Figure 6. The numbers 0 to 14 placed by their remainders modulo 3 and modulo 5. Every cell holds exactly one number, so the pair of remainders identifies the number. Data: computed by ch13_charts.py in the companion repository.

Search works for small moduli. Bezout's identity gives a construction instead. For 3 and 5 it reads 2⋅3−1⋅5=12 \cdot 3 - 1 \cdot 5 = 1. The number −5-5 is then congruent to 1 modulo 3 and to 0 modulo 5, while 6 is congruent to 0 modulo 3 and to 1 modulo 5. Each acts as a switch that is on for one modulus and off for the other, so 2⋅(−5)+3⋅6=−10+18=82 \cdot (-5) + 3 \cdot 6 = -10 + 18 = 8 has remainder 2 modulo 3 and remainder 3 modulo 5.

Proof. Since tn=1−smtn = 1 - sm, the number tntn is congruent to 1 modulo mm, and smsm is congruent to 0 modulo mm, so x≡a⋅1+b⋅0=a(modm)x \equiv a \cdot 1 + b \cdot 0 = a \pmod{m}. The same reasoning with the roles swapped gives x≡b(modn)x \equiv b \pmod{n}. If x′x' is a second solution, then mm and nn both divide x−x′x - x'. Write x−x′=mkx - x' = mk. Then n∣mkn \mid mk with gcd⁡(m,n)=1\gcd(m, n) = 1, so n∣kn \mid k by the corollary on dividing a product, and mn∣x−x′mn \mid x - x'. ■\blacksquare

For a second example take m=4m = 4 and n=9n = 9, with −2⋅4+1⋅9=1-2 \cdot 4 + 1 \cdot 9 = 1, and ask for x≡3(mod4)x \equiv 3 \pmod{4} and x≡5(mod9)x \equiv 5 \pmod{9}. The construction gives x=3⋅1⋅9+5⋅(−2)⋅4=27−40=−13x = 3 \cdot 1 \cdot 9 + 5 \cdot (-2) \cdot 4 = 27 - 40 = -13, and −13 mod 36=23-13 \bmod 36 = 23. Indeed 23=5⋅4+323 = 5 \cdot 4 + 3 and 23=2⋅9+523 = 2 \cdot 9 + 5. The companion script checks that the map from xx to its pair of remainders is one to one for every coprime pair of moduli up to 15, and that m∣xm \mid x and n∣xn \mid x together give mn∣xmn \mid x for coprime mm and nn up to 12 and every xx below 400. The theorem also splits the totient.

Proof. If m=1m = 1 or n=1n = 1 there is nothing to prove, so take both at least 2. By the theorem, sending xx to the pair (x mod m,x mod n)(x \bmod m, x \bmod n) matches the numbers 0 to mn−1mn - 1 one to one with the pairs of remainders. A number xx is coprime to mnmn exactly when it is coprime to both mm and nn. One direction holds because a common divisor of xx and mm also divides mnmn. For the other, Bezout's identity gives sx+tm=1sx + tm = 1 and ux+vn=1ux + vn = 1, so tv mn=(1−sx)(1−ux)=1−x(s+u−sux)tv\,mn = (1 - sx)(1 - ux) = 1 - x(s + u - sux), that is, x(s+u−sux)+tv mn=1x(s + u - sux) + tv\,mn = 1, and gcd⁡(x,mn)=1\gcd(x, mn) = 1. By the lemma that one division keeps the greatest common divisor, gcd⁡(x,m)=gcd⁡(m,x mod m)\gcd(x, m) = \gcd(m, x \bmod m), so xx is coprime to mm exactly when x mod mx \bmod m is a unit modulo mm, and likewise for nn. The units modulo mnmn therefore match the pairs of units, of which there are φ(m)φ(n)\varphi(m)\varphi(n). ■\blacksquare

So φ(12)=φ(4)φ(3)=2⋅2=4\varphi(12) = \varphi(4)\varphi(3) = 2 \cdot 2 = 4 and φ(36)=φ(4)φ(9)=2⋅6=12\varphi(36) = \varphi(4)\varphi(9) = 2 \cdot 6 = 12, and the companion script checks the rule for every coprime pair mm and nn from 1 to 30.

The theorem says that a number is pinned down by its remainders modulo several coprime moduli. Polynomials obey the same law. A polynomial of low degree is pinned down by its values at a few distinct points, and the construction above, with one switch per point, becomes the interpolation formula that Reed–Solomon codes are built on [12]. A later Part develops that parallel in full.

08.The Integers Modulo a Prime

Figure 7 sets the multiplication table modulo 7 beside the one modulo 6. In the table modulo 7, every nonzero row contains a 1 exactly once, which says that every nonzero number has an inverse. In the table modulo 6, only rows 1 and 5 contain a 1, rows 2, 3 and 4 contain none, and the products 2⋅32 \cdot 3, 3⋅23 \cdot 2, 3⋅43 \cdot 4 and 4⋅34 \cdot 3 are all 0 although neither factor is.

Multiplication tables modulo 7 and modulo 6, with inverses and zero divisors marked multiplication mod 7 x 0 0 1 1 2 2 3 3 4 4 5 5 6 6 0 0 0 0 0 0 0 0 1 2 3 4 5 6 0 2 4 6 1 3 5 0 3 6 2 5 1 4 0 4 1 5 2 6 3 0 5 3 1 6 4 2 0 6 5 4 3 2 1 multiplication mod 6 x 0 0 1 1 2 2 3 3 4 4 5 5 0 0 0 0 0 0 0 1 2 3 4 5 0 2 4 0 2 4 0 3 0 3 0 3 0 4 2 0 4 2 0 5 4 3 2 1 product 1: the row and the column are inverses product 0 from two nonzero factors: a zero divisor
Figure 7. Multiplication modulo 7 and modulo 6. Modulo the prime 7 every nonzero row reaches 1, while modulo 6 the rows of 2, 3 and 4 never do, and zero divisors appear. Data: computed by ch13_charts.py in the companion repository.

The rational numbers and the real numbers are fields, and the integers are not, since 2 has no integer inverse. A field is the setting in which every linear equation ax=cax = c with a≠0a \ne 0 has exactly one solution, x=a−1cx = a^{-1} c, and that is the property every decoder in Part II relies on.

Proof. The laws of addition and multiplication hold in Zn\mathbb{Z}_n because they hold for the integers and congruence respects both operations, and the negative of aa is n−an - a, or 0 for a=0a = 0. Only inverses are in question. If n=pn = p is prime, every aa from 1 to p−1p - 1 satisfies gcd⁡(a,p)=1\gcd(a, p) = 1, so it has an inverse by the theorem on when an inverse exists. If nn is not prime, write n=abn = ab with 1<a,b<n1 < a, b < n. Then ab≡0ab \equiv 0 with both factors nonzero. If aa had an inverse cc, then b≡cab≡c⋅0=0(modn)b \equiv c a b \equiv c \cdot 0 = 0 \pmod{n}, which is false, since 0<b<n0 < b < n. So aa has no inverse and Zn\mathbb{Z}_n is not a field. ■\blacksquare

The companion script counts 6 units in Z7\mathbb{Z}_7 and 2 in Z6\mathbb{Z}_6, finds the four zero-divisor products in Z6\mathbb{Z}_6, and checks the theorem for every nn from 2 to 60. Zero divisors also break the rule that a polynomial has no more roots than its degree. In Z6\mathbb{Z}_6 the polynomial 2x2x, of degree 1, has the two roots 0 and 3, since 2⋅3=6≡02 \cdot 3 = 6 \equiv 0. In a field this cannot happen, because ax=0ax = 0 with a≠0a \ne 0 gives x=a−1⋅0=0x = a^{-1} \cdot 0 = 0, and root counting of that kind is what lets a Reed–Solomon decoder locate errors.

The smallest field is Z2\mathbb{Z}_2, with elements 0 and 1. Its addition has 1+1=2≡01 + 1 = 2 \equiv 0, which is XOR, and its multiplication is 1 only for 1⋅11 \cdot 1, which is AND, as Figure 8 shows. Since 1+1=01 + 1 = 0, the negative of 1 is 1 itself, and subtraction in Z2\mathbb{Z}_2 is the same operation as addition. A parity bit is a sum in this field. The four bits 1, 0, 1 and 1 sum to 3≡1(mod2)3 \equiv 1 \pmod{2}, which is their XOR, the value the tree of gates in Lab: A First Hardware Checker computes. The field of two elements is often written GF(2)\mathrm{GF}(2), after Galois.

Arithmetic modulo 2 as two logic gates. At the top, an XOR gate takes bits a and b and gives a + b mod 2, beside the addition table modulo 2: 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1 and 1 + 1 = 0, with the 1 + 1 = 0 cell marked in green because the carry is dropped. At the bottom, an AND gate gives a b mod 2, beside the multiplication table: the product is 1 only when both bits are 1. a b a + b mod 2 XOR gate addition in Z2 + 0 1 0 0 1 1 1 0 a b a b mod 2 AND gate multiplication in Z2 x 0 1 0 0 0 1 0 1 In the green cell 1 + 1 = 2 leaves 0 modulo 2, so the carry is dropped, as in XOR.
Figure 8. The integers modulo 2 in hardware. Addition is the XOR gate and multiplication is the AND gate, so a circuit of these two gates computes in the field of two elements.

Hardware prefers bytes, and here the integers alone fall short. The numbers modulo 256 fill a byte exactly, but 256 is not prime, and 2⋅128=256≡02 \cdot 128 = 256 \equiv 0, so 2 is a zero divisor, and only the 128 odd numbers are units, φ(256)=128\varphi(256) = 128. The next prime, 257, gives a field, but its elements do not fit in 8 bits. The field with 256 elements that storage and communication systems use is built differently, from polynomials whose coefficients lie in Z2\mathbb{Z}_2, and a later chapter constructs it.

09.Looking Ahead

The integers modulo nn carry two operations, and the chapter has leaned on both. Addition modulo 12 is a clock and addition modulo 2 is XOR, the units modulo nn stay units when multiplied together, and the proofs of Fermat's and Euler's theorems multiplied a whole set of residues by one of them and found the same set again.

The next chapter, Groups and Cosets, gives that pattern its name. A group is a set with one operation that can always be undone, and the order of an element is the first power at which it returns to the identity, as 5 does at the ninth power modulo 19 in the worked examples below. Lagrange's theorem says that the size of a subgroup divides the size of the group, and with it that the order of an element does. Cosets, the shifted copies of a subgroup, turn out to be exactly the lists that a syndrome decoder works from.

10.Worked Examples

11.Exercises

References

  1. [1]Python Software Foundation “Expressions.” The Python 3 documentation. Read 2026-11-14. https://docs.python.org/3/reference/expressions.html
  2. [2]ISO/IEC JTC1/SC22/WG14 (2007). “ISO/IEC 9899:TC3, Committee Draft WG14/N1256.” Programming languages, C. Section 6.5.5. Read 2026-11-15. https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf
  3. [3]Python Software Foundation “math: Mathematical functions.” The Python 3 documentation. Read 2026-11-14. https://docs.python.org/3/library/math.html
  4. [4]GNU Octave Project “Utility Functions.” GNU Octave Manual, version 11.3.0. Read 2026-11-14. https://docs.octave.org/latest/Utility-Functions.html
  5. [5]Boute, Raymond T. (1992). “The Euclidean Definition of the Functions div and mod.” ACM Transactions on Programming Languages and Systems, 14(2), pp. 127–144. doi:10.1145/128861.128862
  6. [6]Shallit, Jeffrey (1994). “Origins of the Analysis of the Euclidean Algorithm.” Historia Mathematica, 21(4), pp. 401–419. doi:10.1006/hmat.1994.1031
  7. [7]Gauss, Carl Friedrich (1986). “Disquisitiones Arithmeticae.” Springer. English translation by Arthur A. Clarke of the 1801 original. doi:10.1007/978-1-4939-7560-0
  8. [8]Gallian, Joseph A. (1991). “The Mathematics of Identification Numbers.” The College Mathematics Journal, 22(3), pp. 194–202. doi:10.1080/07468342.1991.11973381
  9. [9]Lin, Shu and Costello, Jr., Daniel J. (2004). “Error Control Coding: Fundamentals and Applications.” 2nd edition. Pearson Prentice Hall.
  10. [10]Luhn, Hans Peter (1960). “Computer for Verifying Numbers.” U.S. Patent 2,950,048. https://patents.google.com/patent/US2950048A/en
  11. [11]Python Software Foundation “Built-in Functions.” The Python 3 documentation. Read 2026-11-14. https://docs.python.org/3/library/functions.html
  12. [12]Reed, Irving S. and Solomon, Gustave (1960). “Polynomial Codes over Certain Finite Fields.” Journal of the Society for Industrial and Applied Mathematics, 8(2), pp. 300–304. doi:10.1137/0108018

— Anirban

Hardware–software at the seam where compilers meet microcode.

FeedbackBook modePaper
error-correction-codinglinear-block-codes