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 n, the theorems of Fermat and Euler and the Chinese remainder theorem follow, and the last section reaches the integers modulo a prime p, the first finite field, with the integers modulo 2 built from XOR and AND gates.
Divide 17 by 5 in whole numbers and the answer is 3 with 2 left over, because 17=3⋅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 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 and -17 % 5 is −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[4]. Figure 1 draws the two answers on a number line.
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, since (−4)⋅5+3=−17 and (−3)⋅5−2=−17. They differ only in which multiple of 5 they step to. Floored division always steps down, here to −20, and leaves a remainder from 0 to 4. Truncated division steps toward zero, here to −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 ±17 by ±5, each given as a quotient and remainder (q,r)
a
b
Floored
Truncated
Euclidean
17
5
(3,2)
(3,2)
(3,2)
−17
5
(−4,3)
(−3,−2)
(−4,3)
17
−5
(−4,−3)
(−3,2)
(−3,2)
−17
−5
(3,−2)
(3,−2)
(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 for −17 by 5 and 2+(−5)=−3 for 17 by −5. The companion script checks that rule for every a and every nonzero b from −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 17mod5=2 and −17mod5=3. The operation is named mod, and when it is applied to two numbers it is written between them, as in amodn. 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⌋, the largest integer not above a/n. Then q≤a/n<q+1, and multiplying by the positive number n gives qn≤a<qn+n. Setting r=a−qn therefore gives 0≤r<n, which for whole numbers is 0≤r≤n−1. For uniqueness, suppose a=qn+r=q′n+r′ with both remainders between 0 and n−1. Subtracting gives (q−q′)n=r′−r, so r′−r is a multiple of n. But ∣r′−r∣≤n−1, and the only multiple of n that small is 0, so r′=r, and then (q−q′)n=0 gives q′=q. ■
The companion script confirms the theorem directly for every a from −50 to 50 and every n from 1 to 12, finding exactly one pair each time.
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+r with r=amodb. A number d that divides a and b also divides r=a−qb, since both terms on the right are multiples of d. A number d that divides b and r also divides a=qb+r for the same reason. So the pairs (a,b) and (b,r) have exactly the same common divisors, and therefore the same largest one. ■
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 for r≥1, since every integer divides 0. On 1147 and 899 it takes six divisions.
The last nonzero remainder, 31, is the greatest common divisor, as the lists of divisors said, and indeed 1147=31⋅37 and 899=31⋅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.
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>⋯≥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) at every step, so gcd(a,b)=gcd(r0,r1)=gcd(rn,rn+1)=gcd(rn,0)=rn. ■
For 1147 and 899 the remainders are r2=248 through r6=31 and r7=0, so n=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 b divisions, a hopelessly loose bound. A sharper fact holds.
Proof. Note first that ri+1≤ri, with equality possible only at the start, when a=b. There are two cases. If ri+1≤ri/2, then ri+2<ri+1≤ri/2, because a remainder is smaller than the number divided by. If ri+1>ri/2, then ri+1 fits into ri exactly once, since twice it exceeds ri, so the quotient is 1 and ri+2=ri−ri+1<ri−ri/2=ri/2. ■
On 1147 and 899 the lemma says 248<1147/2, 155<899/2, 93<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=b and r2<r1, the lemma halves the bound every two indices, so by induction ri≤b/2⌊(i−1)/2⌋ for every i≥1. The last nonzero remainder satisfies rn≥1, so 2⌊(n−1)/2⌋≤b, and taking logarithms, ⌊(n−1)/2⌋≤log2b. The left side is an integer, so it is at most ⌊log2b⌋. Since (n−1)/2<⌊(n−1)/2⌋+1, this gives n−1<2⌊log2b⌋+2, and as n is an integer, n≤2⌊log2b⌋+2. ■
For b=899 the bound allows 20 divisions, and the algorithm took 6. The companion script checks the bound for every a and b from 1 to 299. What matters is that the bound grows with the number of binary digits of b rather than with b 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) start from F(1)=F(2)=1, and each later one is the sum of the two before it, 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≥4, dividing F(k) by F(k−1) gives quotient 1 and leaves 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, where ϕ=(1+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 a from 2 to 233 and b below a, the smallest a that needs n divisions is F(n+2), and the only pair with that a is F(n+2) and F(n+1). Figure 3 plots the remainders of 1147 and 899 beside those of the Fibonacci pair 4181 and 2584.
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.
Multiply 1147 by 11 and 899 by 14. The products are 12617 and 12586, and they differ by 31, so 31=11⋅1147−14⋅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 n into a multiplication, and the coefficients 11 and −14 come straight out of Euclid's algorithm.
The extended algorithm keeps, beside each remainder ri, two integers si and ti with ri=sia+tib. At the start this is trivial, since a=1⋅a+0⋅b and b=0⋅a+1⋅b. Each division computes ri+1=ri−1−qiri with quotient qi=⌊ri−1/ri⌋, and the same combination of the two rows above keeps the coefficients in step.
If ri−1=si−1a+ti−1b and ri=sia+tib, then subtracting qi times the second from the first gives ri+1=si+1a+ti+1b, 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 a=1147 and b=899, where every row satisfies ri=1147si+899ti
i
ri
qi
si
ti
0
1147
1
0
1
899
1
0
1
2
248
3
1
−1
3
155
1
−3
4
4
93
1
4
−5
5
62
1
−7
9
6
31
2
11
−14
7
0
−29
37
Source: reproduced by ch13_integers_and_modular_arithmetic.py.
Row 6 holds the greatest common divisor with its coefficients, 11⋅1147−14⋅899=31. Row 7, where the remainder is 0, says −29⋅1147+37⋅899=0, and its coefficients are, up to sign, the cofactors 29 and 37 from 899=31⋅29 and 1147=31⋅37. Adding row 7 to row 6 any number of times changes the coefficients without changing the combination, so s=11−29k and t=−14+37k work for every integer k. The coefficients are not unique, and the algorithm simply returns one pair.
Proof. The set of positive values of sa+tb is not empty, since it contains a2+b2, the value at s=a and t=b. Let g=sa+tb be its smallest element. Divide a by g to get a=qg+r with 0≤r≤g−1. Then r=a−q(sa+tb)=(1−qs)a+(−qt)b is again a combination of a and b, and it is smaller than g, so it cannot be positive, which leaves r=0 and g∣a. The same argument gives g∣b, so g is a common divisor and g≤gcd(a,b). In the other direction, gcd(a,b) divides a and b, so it divides sa+tb=g, and a positive divisor of g is at most g. Hence g=gcd(a,b). ■
The companion script tries every s and t from −60 to 60 on 1147 and 899 and finds the smallest positive combination is 31, and for every a and b from 1 to 79 it checks that the extended algorithm writes gcd(a,b) as sa+tb. The identity has a consequence used in almost every proof that follows.
Proof. Bezout's identity gives integers s and t with sm+tn=1. Multiplying by k gives k=s(mk)+(tk)n, and n divides both terms on the right, so n∣k. For the second statement, if p does not divide m, then gcd(m,p)=1, because the only positive divisors of p are 1 and p, and the first statement gives p∣k. ■
The prime is essential. The number 6 divides 36=4⋅9, yet 4mod6=4 and 9mod6=3, so 6 divides neither factor. The companion script checks Euclid's lemma for every prime below 40.
On a clock, 5 hours after 9 o'clock is 2 o'clock, because 9+5=14=1⋅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 and 3 land on the same mark, since both leave remainder 3 and their difference −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.
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) and −17≡3(mod5). A congruence is a statement about two numbers, while amodn is a number, and the two are tied together as follows.
Proof. Write a=qn+r and b=q′n+r′ with both remainders from 0 to n−1. Then a−b=(q−q′)n+(r−r′). If r=r′, the difference is a multiple of n. Conversely, if n divides a−b, it divides r−r′, and as ∣r−r′∣≤n−1, that forces r−r′=0. ■
The companion script finds that −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+kn and b′=b+ln for integers k and l. Then a′+b′=a+b+(k+l)n and a′b′=ab+(al+bk+kln)n, and in each case the difference from the original is a multiple of n. ■
The theorem means a computation modulo n can reduce at every step, and the numbers involved never need to grow past about n2. Take 37⋅52mod7. Since 37mod7=2 and 52mod7=3, the product is congruent to 2⋅3=6. Computed the long way, 37⋅52=1924, and 1924−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 313mod11, write the exponent in binary, 13=11012=8+4+1, and square repeatedly, reducing each time. The powers 3, 32, 34 and 38 reduce to 3, 9, 4 and 5 modulo 11, since 81≡4 and 42=16≡5. Then 313=38⋅34⋅3≡5⋅4⋅3=60≡5(mod11). The full power is 313=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,…,x10 of the number to satisfy ∑i=110(11−i)xi≡0(mod11), 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≡0. The Luhn formula on card numbers is the same idea modulo 10 [10], and on 3141592653 its terms sum to 40≡0(mod10). 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.
Modulo 7, 3⋅5=15≡1, so multiplying by 5 undoes multiplying by 3, and 5 behaves like 1/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 x satisfies 2x≡1(mod6). Worse, 2⋅3≡2⋅0(mod6), since both sides are multiples of 6, yet 3≡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≡1. Which numbers are units is decided by the greatest common divisor.
Proof. If gcd(a,n)=1, Bezout's identity gives sa+tn=1, and reducing modulo n gives sa≡1, so s is an inverse. Conversely, if ab≡1, then ab−1=kn for some integer k, so ab−kn=1, and any common divisor of a and n divides the left side and hence divides 1. For uniqueness, if ab≡1 and ab′≡1, then b≡b(ab′)=(ba)b′≡b′(modn). ■
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⋅37 and 31⋅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=1. Reducing modulo 37 gives 29⋅(−14)≡1, and −14mod37=23, so the inverse of 29 is 23. As a check, 29⋅23=667 and 18⋅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−1, which exists by the theorem, and use the fact that congruence respects multiplication. ■
The failure modulo 6 is exactly the case gcd(2,6)=2, and the companion script checks cancellation for every modulus up to 30 and every c 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=6, and the other nine terms sum to 97, so the missing digit x satisfies 97+6x≡0(mod11), that is, 6x≡−97≡2(mod11). The inverse of 6 modulo 11 is 2, since 6⋅2=12≡1, so x≡2⋅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.
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 akmod7 of the nonzero residues modulo 7, for exponents k from 1 to 6
a
a1
a2
a3
a4
a5
a6
1
1
1
1
1
1
1
2
2
4
1
2
4
1
3
3
2
6
4
5
1
4
4
2
1
4
2
1
5
5
4
6
2
3
1
6
6
1
6
1
6
1
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, which reads 36⋅6!≡6!(mod7). Here 6!=720≡6, a unit modulo 7, so it cancels and leaves 36≡1.
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) modulo p. None is 0, because by Euclid's lemma p would then divide a or a number below p. No two are equal, because ak≡ak′ gives k≡k′ by cancellation, as gcd(a,p)=1. So the p−1 products are the numbers 1 to p−1 in some order, and multiplying them all together gives ap−1(p−1)!≡(p−1)!(modp). The factorial is a product of units, hence a unit, and cancelling it leaves ap−1≡1. ■
Proof. If p divides a, both sides are congruent to 0. Otherwise multiply both sides of Equation 7 by a. ■
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. A prime has every smaller positive number as a unit, so φ(7)=6. The units modulo 9 are 1, 2, 4, 5, 7 and 8, so φ(9)=6, and φ(8)=4. For powers of a prime there is a closed form.
Proof. A number shares a factor greater than 1 with pk exactly when p divides it, since every divisor of pk above 1 is a power of p. Among 1 to pk the multiples of p are p,2p,…,pk−1⋅p, which is pk−1 numbers. The other pk−pk−1 numbers are the units. ■
So φ(9)=9−3=6 and φ(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,…,um be the units modulo n, with m=φ(n). Each product aui is again a unit, with inverse ui−1a−1, and the products are distinct modulo n by cancellation. So the products au1,…,aum reduced modulo n are the units in some order, and multiplying them together gives amu1⋯um≡u1⋯um. The product of the units is a unit, and cancelling it leaves am≡1. ■
For a prime p, φ(p)=p−1 and Euler's theorem is Fermat's. Modulo 9, the theorem says 26≡1, and indeed 26=64=7⋅9+1. Modulo 12, every unit has square 1, as 52, 72 and 112 all leave 1, so the exponent φ(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) and 100=6⋅16+4, the power 3100=(36)16⋅34≡34=81≡4(mod7). They also give a second way to invert. Modulo a prime p, for a not divisible by p, a⋅ap−2=ap−1≡1, so ap−2 is the inverse of a. Modulo 11 the inverse of 6 is 69, and square and multiply, with 6, 62, 64 and 68 reducing to 6, 3, 9 and 4, gives 69=68⋅6≡4⋅6=24≡2, the same inverse that recovered the smudged ISBN digit. The full power 69=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.
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.
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=1. The number −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=8 has remainder 2 modulo 3 and remainder 3 modulo 5.
Proof. Since tn=1−sm, the number tn is congruent to 1 modulo m, and sm is congruent to 0 modulo m, so x≡a⋅1+b⋅0=a(modm). The same reasoning with the roles swapped gives x≡b(modn). If x′ is a second solution, then m and n both divide x−x′. Write x−x′=mk. Then n∣mk with gcd(m,n)=1, so n∣k by the corollary on dividing a product, and mn∣x−x′. ■
For a second example take m=4 and n=9, with −2⋅4+1⋅9=1, and ask for x≡3(mod4) and x≡5(mod9). The construction gives x=3⋅1⋅9+5⋅(−2)⋅4=27−40=−13, and −13mod36=23. Indeed 23=5⋅4+3 and 23=2⋅9+5. The companion script checks that the map from x to its pair of remainders is one to one for every coprime pair of moduli up to 15, and that m∣x and n∣x together give mn∣x for coprime m and n up to 12 and every x below 400. The theorem also splits the totient.
Proof. If m=1 or n=1 there is nothing to prove, so take both at least 2. By the theorem, sending x to the pair (xmodm,xmodn) matches the numbers 0 to mn−1 one to one with the pairs of remainders. A number x is coprime to mn exactly when it is coprime to both m and n. One direction holds because a common divisor of x and m also divides mn. For the other, Bezout's identity gives sx+tm=1 and ux+vn=1, so tvmn=(1−sx)(1−ux)=1−x(s+u−sux), that is, x(s+u−sux)+tvmn=1, and gcd(x,mn)=1. By the lemma that one division keeps the greatest common divisor, gcd(x,m)=gcd(m,xmodm), so x is coprime to m exactly when xmodm is a unit modulo m, and likewise for n. The units modulo mn therefore match the pairs of units, of which there are φ(m)φ(n). ■
So φ(12)=φ(4)φ(3)=2⋅2=4 and φ(36)=φ(4)φ(9)=2⋅6=12, and the companion script checks the rule for every coprime pair m and n 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.
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⋅3, 3⋅2, 3⋅4 and 4⋅3 are all 0 although neither factor is.
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=c with a=0 has exactly one solution, x=a−1c, and that is the property every decoder in Part II relies on.
Proof. The laws of addition and multiplication hold in Zn because they hold for the integers and congruence respects both operations, and the negative of a is n−a, or 0 for a=0. Only inverses are in question. If n=p is prime, every a from 1 to p−1 satisfies gcd(a,p)=1, so it has an inverse by the theorem on when an inverse exists. If n is not prime, write n=ab with 1<a,b<n. Then ab≡0 with both factors nonzero. If a had an inverse c, then b≡cab≡c⋅0=0(modn), which is false, since 0<b<n. So a has no inverse and Zn is not a field. ■
The companion script counts 6 units in Z7 and 2 in Z6, finds the four zero-divisor products in Z6, and checks the theorem for every n from 2 to 60. Zero divisors also break the rule that a polynomial has no more roots than its degree. In Z6 the polynomial 2x, of degree 1, has the two roots 0 and 3, since 2⋅3=6≡0. In a field this cannot happen, because ax=0 with a=0 gives x=a−1⋅0=0, and root counting of that kind is what lets a Reed–Solomon decoder locate errors.
The smallest field is Z2, with elements 0 and 1. Its addition has 1+1=2≡0, which is XOR, and its multiplication is 1 only for 1⋅1, which is AND, as Figure 8 shows. Since 1+1=0, the negative of 1 is 1 itself, and subtraction in Z2 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), 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), after Galois.
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≡0, so 2 is a zero divisor, and only the 128 odd numbers are units, φ(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, and a later chapter constructs it.
The integers modulo n 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 n 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.
[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]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]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]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]Lin, Shu and Costello, Jr., Daniel J. (2004). “Error Control Coding: Fundamentals and Applications.” 2nd edition. Pearson Prentice Hall.
[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.