The Zcash ArboretumI–IX The Complete Arboretum
Contents
PDF
Theme

2 The integers and modular arithmetic

This section develops the integers ℤ={…,−2,−1,0,1,2,…} from a small set of assumptions and constructs the integers modulo n—the set ℤ/nℤ of congruence classes—with its units and the algorithms that compute with them. It proves that division modulo n is multiplication by a modular inverse, that the class of a has one exactly when gcd(a,n)=1 (Theorem 2.24), and that an extension of the algorithm of Euclid’s Elements computes it efficiently, as cryptography requires. Every step of a prover or verifier in the proof systems of this series is an addition, a multiplication, or a division of remainders modulo a fixed large prime; addition and multiplication are computed in ℤ, after which multiples of the modulus are discarded. The finite number systems underlying elliptic curves, the scalar arithmetic of Halo 2, and the polynomial commitments of Orchard (short values that bind a prover to entire polynomials, which a verifier then tests by evaluation) all reduce to computations with congruence classes.

2.1 Well-ordering and the integers

We take the basic algebraic properties of ℤ for granted: addition and multiplication are associative and commutative, and multiplication distributes over addition; the integers 0 and 1 are identities for addition and multiplication respectively; every integer a has a negative −a; there are no zero divisors (if ab=0 then a=0 or b=0); and ℤ carries a total order ≤ compatible with the arithmetic. The one further property assumed as an axiom is the following.

Theorem 2.1 (Well-ordering principle).

Every nonempty subset S⊆ℕ={0,1,2,…} of the natural numbers has a least element: there exists m∈S such that m≤s for all s∈S.

The well-ordering principle is logically equivalent to the principle of mathematical induction; we use both freely. The existence results below (division with remainder, termination of the Euclidean algorithm, Bézout’s identity, prime factorisation) all rest on it.

2.2 Divisibility

Definition 2.2.

Let a,b∈ℤ. One says that a divides b, written a∣b, if there exists an integer c∈ℤ with b=ac. In this case a is called a divisor or factor of b, and b is a multiple of a. If no such c exists one writes a∤b.

The following consequences are used throughout, usually without citation.

Proposition 2.3.

Let a,b,c,d∈ℤ. Then:

  1. 1.

    a∣a (reflexivity), 1∣a, and a∣0.

  2. 2.

    If a∣b and b∣c then a∣c (transitivity).

  3. 3.

    If a∣b and a∣c then a∣(bx+cy) for all x,y∈ℤ; in particular a∣(b±c).

  4. 4.

    If a∣b and b≠0 then |a|≤|b|.

  5. 5.

    If a∣b and b∣a then a=±b.

  6. 6.

    0∣b if and only if b=0.

Proof.

Part (1) is immediate: a=a⋅1, a=1⋅a, 0=a⋅0. For (2), write b=ae and c=bf; then c=a(ef), so a∣c. For (3), write b=ae and c=af; then bx+cy=a(ex+fy). For (4), write b=ac with b≠0, so c≠0 and hence |c|≥1; then |b|=|a||c|≥|a|. For (5), if either is 0 then by (6) so is the other and the claim holds; otherwise (4) gives |a|≤|b| and |b|≤|a|, so |a|=|b| and a=±b. For (6), 0∣b means b=0⋅c=0; conversely 0∣0. □

Restricted to the natural numbers, where (5) becomes a=b, the relation ∣ is a partial order in the sense of §1.3; on ℤ it fails to be antisymmetric because of signs. The units of ℤ—the integers dividing 1—are exactly ±1, and two integers that divide each other are called associates; in ℤ the associates of a are ±a.

2.3 The division algorithm

Theorem 2.4 (Division algorithm).

Let a∈ℤ and b∈ℤ with b>0. Then there exist unique integers q (the quotient) and r (the remainder) such that

a=b⁢q+r,0≤r<b.
Proof.

Existence. Consider the set

S={a−b⁢k:k∈ℤ,a−b⁢k≥0}⊆ℕ.

First, S≠∅. If a≥0 then a=a−b⋅0∈S. If a<0 then, since b≥1, taking k=a gives a−ba=a(1−b)≥0 (a product of a nonpositive and a nonpositive factor), so a−ba∈S. Thus S is a nonempty subset of ℕ, and by the well-ordering principle (Theorem 2.1) it has a least element r=a−bq for some q∈ℤ. By construction r≥0. If r≥b, then r−b=a−b(q+1)≥0 would lie in S and be strictly smaller than r, contradicting minimality. Hence 0≤r<b.

Uniqueness. Suppose a=bq+r=bq′+r′ with 0≤r,r′<b. Then b(q−q′)=r′−r, so b∣(r′−r). But −b<r′−r<b, and the only multiple of b strictly between −b and b is 0. Hence r′=r, and then b(q−q′)=0 with b≠0 forces q=q′. □

Remark 2.5.

The hypothesis b>0 is only for definiteness. For general b≠0 one obtains unique q,r with a=bq+r and 0≤r<|b|, by applying the theorem to |b| and adjusting the sign of q. The remainder convention 0≤r<|b| differs from the truncation behaviour of many programming languages, where the remainder of a negative dividend may be negative; the results below use the former.

We denote the remainder r produced by the division algorithm by amodb, and the quotient q by ⌊a/b⌋ when b>0 (the floor of the rational number a/b). With this notation, b∣a holds precisely when amodb=0.

2.4 The greatest common divisor and the Euclidean algorithm

Definition 2.6.

A common divisor of integers a and b is an integer d with d∣a and d∣b. The greatest common divisor of a and b, not both zero, is the largest such d; it is denoted gcd(a,b). By convention gcd(0,0)=0. Integers a and b are coprime (or relatively prime) if gcd(a,b)=1.

The greatest common divisor is well defined when (a,b)≠(0,0): the set of common divisors is nonempty (it contains 1) and bounded above (every common divisor of, say, the nonzero a has absolute value at most |a| by Proposition 2.3(4)), so it has a largest element, which is positive since 1 is a common divisor. The computation of the gcd rests on the following lemma.

Lemma 2.7.

Let a,b∈ℤ. For any q∈ℤ,

gcd⁡(a,b)=gcd⁡(b,a−q⁢b).

In particular, if a=bq+r then gcd(a,b)=gcd(b,r), and gcd(a,0)=|a|.

Proof.

It suffices to show the two pairs (a,b) and (b,a−qb) have exactly the same common divisors; equal sets of common divisors have equal greatest elements (and the same coprimality status). If d∣a and d∣b, then d∣(a−qb) by Proposition 2.3(3), so d is a common divisor of b and a−qb. Conversely, if d∣b and d∣(a−qb), then d∣((a−qb)+qb)=a, so d is a common divisor of a and b. The two sets of common divisors coincide. Finally gcd(a,0)=|a| because the common divisors of a and 0 are exactly the divisors of a, the largest of which in absolute value is |a| (and |a|>0 when a≠0; the case a=0 is the convention gcd(0,0)=0). □

Theorem 2.8 (Euclidean algorithm).

Let a,b be integers with b≠0. Define a sequence of remainders by r0=|a|, r1=|b|, and, as long as ri≠0, let ri+1=ri−1modri, so that

ri−1=ri⁢qi+ri+1,0≤ri+1<ri.

The sequence r1>r2>⋯ of positive remainders is strictly decreasing, so some rn+1=0; the last nonzero remainder satisfies rn=gcd(a,b).

Proof.

The remainders r1,r2,… are nonnegative integers and, while nonzero, strictly decreasing because ri+1=ri−1modri<ri. A strictly decreasing sequence of nonnegative integers cannot be infinite (again by well-ordering: otherwise the set of values would have no least element), so the algorithm terminates with some rn+1=0 and rn>0. By Lemma 2.7, each step preserves the gcd:

gcd⁡(a,b)=gcd⁡(r0,r1)=gcd⁡(r1,r2)=⋯=gcd⁡(rn,rn+1)=gcd⁡(rn,0)=rn,

using gcd(|a|,|b|)=gcd(a,b) (signs do not affect common divisors). □

Example 2.9.

Compute gcd(1071,462):

1071 =2⋅462+147,
462 =3⋅147+21,
147 =7⋅21+0.

The last nonzero remainder is 21, so gcd(1071,462)=21. As a check, 1071=21⋅51 and 462=21⋅22, with gcd(51,22)=1.

Remark 2.10.

The number of division steps of the Euclidean algorithm for inputs a>b>0 is O(logb); the worst case occurs at consecutive Fibonacci numbers (Lamé’s theorem), where every quotient qi equals 1 except the final one (which equals 2) and the remainders shrink as slowly as possible. With schoolbook arithmetic on k-bit inputs the whole computation costs O(k2) bit operations. This bound makes gcd-based operations such as modular inversion practical at the sizes used in Halo 2 and Orchard.

2.5 The Bézout identity and the extended Euclidean algorithm

Back-substitution through the equations of the Euclidean algorithm expresses the gcd as an integer linear combination of the inputs.

Theorem 2.11 (Bézout’s identity).

Let a,b∈ℤ, not both zero, and let d=gcd(a,b). Then there exist integers u,v∈ℤ with

a⁢u+b⁢v=d.

Moreover d is the smallest positive integer expressible in the form ax+by with x,y∈ℤ, and the set of all such combinations is exactly the set of multiples of d:

{a⁢x+b⁢y:x,y∈ℤ}=d⁢ℤ={k⁢d:k∈ℤ}.
Proof.

Let I={ax+by:x,y∈ℤ}. This set contains a and b and is closed under addition and under multiplication by any integer; concretely, if s=ax1+by1 and t=ax2+by2 lie in I, then for any m,n∈ℤ one has

m⁢s+n⁢t=a⁢(m⁢x1+n⁢x2)+b⁢(m⁢y1+n⁢y2)∈I.

Since a,b are not both zero, I contains a positive element (one of ±a,±b), so the set I∩ℕ>0 of positive elements of I is nonempty. By well-ordering it has a least element g=au+bv>0.

We claim that g divides every element of I. Indeed, let c∈I and write c=gq+r with 0≤r<g by the division algorithm. Then r=c−gq∈I because I is closed under the operations just described. By minimality of g among positive elements of I, and 0≤r<g, necessarily r=0. Hence g∣c for every c∈I; in particular g∣a and g∣b, so g is a common divisor of a and b. Conversely, any common divisor e of a and b divides au+bv=g by Proposition 2.3(3). Therefore g is a common divisor that is divisible by every common divisor; being positive, it is in particular the greatest common divisor, so g=d. The displayed equation au+bv=d follows, d is the least positive element of I, and I=gℤ=dℤ because every element of I is a multiple of g, as shown, and conversely every multiple kg=a(ku)+b(kv) lies in I. □

Remark 2.12.

The proof yields a characterisation of the gcd that is independent of the order ≤: d=gcd(a,b) is, up to sign, the unique common divisor of a and b that is divisible by every common divisor. Later sections use this formulation outside the integers, where “largest” may make no sense but “divisible by every common divisor” still does. We call a nonempty subset I⊆ℤ closed under addition and under multiplication by arbitrary integers an ideal; the content of Bézout’s identity is that every ideal of ℤ has the form dℤ for a single generator d. Ideals recur in 4 in a construction that generalises the passage from integers to congruence classes below.

The Bézout coefficients u,v are not unique. If au+bv=d, then for every k∈ℤ,

a⁢(u+k⁢bd)+b⁢(v−k⁢ad)=d,

since the added terms ka⁢bd and −ka⁢bd cancel; and these are all the solutions. To prove completeness, observe first that a/d and b/d are coprime: a common divisor e of both makes de a common divisor of a and b, so de∣au+bv=d by Proposition 2.3(3), forcing e=±1. Now suppose au′+bv′=d. Subtracting au+bv=d and dividing by d>0 gives ad(u′−u)=−bd(v′−v), so b/d divides ad(u′−u); by Proposition 2.15(1) below (whose proof rests only on Bézout’s identity, already established), b/d divides u′−u, say u′=u+kbd with k∈ℤ. Substituting back gives b(v′−v+kad)=0, so v′=v−kad when b≠0; and when b=0 we have u′=u, a/d=±1, and k=(v−v′)ad places (u′,v′) in the family.

Theorem 2.13 (Extended Euclidean algorithm).

There is an algorithm that, on input a,b∈ℤ not both zero, outputs d=gcd(a,b) together with integers u,v satisfying au+bv=d, using the same number of division steps as the Euclidean algorithm.

Proof.

Alongside the remainder sequence of Theorem 2.8, maintain two auxiliary sequences (si) and (ti) with the invariant

ri=a⁢si+b⁢tifor all ⁢i.

Initialise (taking a,b≥0 for clarity; we restore signs at the end)

r0=a,s0=1,t0=0;r1=b,s1=0,t1=1,

so (2.5) holds for i=0,1. At step i≥1, having ri−1=riqi+ri+1 from the division algorithm, set

si+1=si−1−qi⁢si,ti+1=ti−1−qi⁢ti.

Then

a⁢si+1+b⁢ti+1=(a⁢si−1+b⁢ti−1)−qi⁢(a⁢si+b⁢ti)=ri−1−qi⁢ri=ri+1,

so induction preserves (2.5). When the algorithm terminates with rn+1=0 and rn=d=gcd(a,b), the invariant for i=n reads d=asn+btn; output u=sn, v=tn. If b=0, then a≠0 and termination is immediate with n=0: no division step runs, the last nonzero remainder is r0=a=gcd(a,0) (Lemma 2.7), and the invariant at i=0 already gives the output (d,u,v)=(a,1,0). If b≠0, termination and the value of d are exactly as in Theorem 2.8. In either case each step does only a constant amount of extra work. For general inputs, run the algorithm on (|a|,|b|) to obtain |a|u′+|b|v′=d (recall gcd(|a|,|b|)=gcd(a,b)) and output u=sgn(a)u′, v=sgn(b)v′, so that au+bv=d. □

Example 2.14.

Run the extended algorithm on a=1071, b=462 (continuing Example 2.9). The quotients are q1=2,q2=3,q3=7.

irisiti010711014620121471−2321−374022−51

For instance, row 2 is row 0 minus q1=2 times row 1: s2=1−2⋅0=1, t2=0−2⋅1=−2, and 1071⋅1+462⋅(−2)=1071−924=147. The last nonzero remainder is r3=21=gcd(1071,462), with

1071⋅(−3)+462⋅7=−3213+3234=21.

Thus (u,v)=(−3,7). The final row (s4,t4)=(22,−51)=(b/d,−a/d) up to sign records the homogeneous solution: 1071⋅22+462⋅(−51)=0.

Proposition 2.15 (Euclid’s lemma).

Let a,b,c∈ℤ.

  1. 1.

    If c∣ab and gcd(c,a)=1, then c∣b.

  2. 2.

    If gcd(a,b)=1, a∣n, and b∣n, then ab∣n.

  3. 3.

    If gcd(a,b)=1 and gcd(a,c)=1, then gcd(a,bc)=1.

Proof.

(1) By Bézout there are u,v with cu+av=1. Multiply by b: b=cub+avb=c(ub)+(ab)v. Since c∣ab, c divides both terms on the right, hence c∣b.

(2) Write n=ak. Since b∣n=ak and gcd(b,a)=1, part (1) gives b∣k, say k=bm. Then n=a(bm)=(ab)m, so ab∣n.

(3) By Bézout, ax1+by1=1 and ax2+cy2=1 for suitable integers. Multiplying,

1=(a⁢x1+b⁢y1)⁢(a⁢x2+c⁢y2)=a⁢(a⁢x1⁢x2+x1⁢c⁢y2+b⁢y1⁢x2)⏟∈ℤ+b⁢c⁢(y1⁢y2),

which exhibits 1 as an integer combination of a and bc. Hence gcd(a,bc) divides 1, so it equals 1. □

2.6 Primes and the fundamental theorem of arithmetic

Definition 2.16.

An integer p>1 is prime if its only positive divisors are 1 and p. An integer n>1 that is not prime is composite; thus n is composite iff n=ab for some integers 1<a,b<n. The integer 1 is a unit and is by convention neither prime nor composite.

Excluding 1 from the primes is necessary for factorisation into primes to be unique, since otherwise arbitrarily many factors of 1 could be inserted. The property of primes on which uniqueness rests is the prime case of Euclid’s lemma.

Lemma 2.17 (Euclid’s lemma for primes).

Let p be prime and a,b∈ℤ. If p∣ab then p∣a or p∣b. More generally, if p∣a1a2⋯ak then p∣ai for some i.

Proof.

The only positive divisors of p are 1 and p, so gcd(p,a)∈{1,p}. If gcd(p,a)=p then p∣a and the claim holds; otherwise gcd(p,a)=1, and Proposition 2.15(1) gives p∣b. The general statement follows by induction on k: from p∣a1(a2⋯ak) it follows that p∣a1 or p∣a2⋯ak, and the inductive hypothesis handles the latter. □

Theorem 2.18 (Fundamental theorem of arithmetic).

Every integer n>1 can be written as a product of primes,

n=p1⁢p2⁢⋯⁢pk,

and this factorisation is unique up to the order of the factors. Equivalently, there is a unique expression

n=p1e1⁢p2e2⁢⋯⁢prer,p1<p2<⋯<pr⁢ prime,ei≥1.
Proof.

Existence. Suppose, for contradiction, that some integer >1 is not a product of primes, and let n be the least such (well-ordering). Then n is not prime (a prime is trivially a product of one prime), so n=ab with 1<a,b<n. By minimality, each of a,b is a product of primes; concatenating these factorisations expresses n as a product of primes, a contradiction. Hence every n>1 factors into primes.

Uniqueness. Suppose

p1⁢p2⁢⋯⁢pk=q1⁢q2⁢⋯⁢qℓ

are two factorisations of the same integer into primes. The argument proceeds by induction on k. If k=0 the product is the empty product 1, forcing ℓ=0 as well (a nonempty product of primes is >1). For the inductive step, p1 divides the right-hand product, so by Lemma 2.17 p1∣qj for some j. Since qj is prime, its only divisor >1 is itself, so p1=qj. Cancelling this common factor (legitimate as ℤ has no zero divisors) yields

p2⁢⋯⁢pk=q1⁢⋯⁢qj^⁢⋯⁢qℓ,

where the hat denotes omission. By the inductive hypothesis these two factorisations agree up to order, with k−1=ℓ−1; restoring p1=qj shows the original factorisations agree up to order. Collecting equal primes into prime powers gives the canonical form, whose uniqueness is immediate from the uniqueness of the multiset of primes—the factors counted with multiplicity, without regard to order. □

Remark 2.19.

Existence rests on the order structure (well-ordering); uniqueness rests on Euclid’s lemma, hence on Bézout, hence on the division algorithm. In some number systems with a division-like structure, Euclid’s lemma fails and factorisation into irreducibles is not unique.

2.7 Congruences and residue classes

Congruence formalises the arithmetic of remainders. Fix an integer n≥1, the modulus.

Definition 2.20.

Let n≥1 and a,b∈ℤ. The integer a is congruent to b modulo n, written

a≡b(modn),

if n∣(a−b), equivalently if a and b leave the same remainder upon division by n.

The two formulations agree: if a=nq1+r1 and b=nq2+r2 with 0≤r1,r2<n, then a−b=n(q1−q2)+(r1−r2), and n∣(a−b) iff n∣(r1−r2) iff r1=r2 (since |r1−r2|<n).

Proposition 2.21.

Fix n≥1. Congruence modulo n is an equivalence relation on ℤ that is moreover compatible with addition and multiplication: if a≡a′ and b≡b′(modn), then

a+b≡a′+b′(modn),a⁢b≡a′⁢b′(modn).

Consequently ak≡(a′)k(modn) for all k≥0, and one may substitute congruent values freely in any polynomial expression with integer coefficients.

Proof.

Reflexivity (n∣0), symmetry (n∣(a−b)⇒n∣(b−a)), and transitivity (n∣(a−b) and n∣(b−c) give n∣(a−c) by Proposition 2.3(3)) are immediate. For compatibility, write a−a′=ns and b−b′=nt. Then

(a+b)−(a′+b′)=n⁢(s+t),

and

a⁢b−a′⁢b′=a⁢b−a′⁢b+a′⁢b−a′⁢b′=(a−a′)⁢b+a′⁢(b−b′)=n⁢(s⁢b+a′⁢t),

so both n∣((a+b)−(a′+b′)) and n∣(ab−a′b′). The statement about powers and polynomial expressions follows by induction from the multiplicative case. □

Because congruence is an equivalence relation, it partitions ℤ into disjoint congruence classes (also called residue classes).

Definition 2.22.

The congruence class (or residue class) of a modulo n is

[a]n={b∈ℤ:b≡a(modn)}={a+k⁢n:k∈ℤ}=a+n⁢ℤ.

We write the set of all congruence classes as

ℤ/n⁢ℤ={[a]n:a∈ℤ}.

By the division algorithm every integer is congruent modulo n to exactly one of 0,1,…,n−1, namely its remainder; hence the n classes [0]n,[1]n,…,[n−1]n are distinct and exhaust ℤ/nℤ. The set {0,1,…,n−1} is the standard system of representatives, called the least nonnegative residues.

2.8 Units modulo n and modular inverses

Division is the inverse of multiplication, so division of remainders modulo n reduces to determining the a for which the congruence ax≡1(modn) admits a solution.

Definition 2.23.

Let n≥1. A class [a]n∈ℤ/nℤ is a unit (or is invertible) if there exists an integer x with ax≡1(modn). Any class [x]n with this property is the (modular) inverse of [a]n, written [a]n−1; one also calls x a modular inverse of a modulo n. We write the set of units as

(ℤ/n⁢ℤ)×={[a]n:[a]n⁢ is a unit}.

The definition is well posed on classes: by Proposition 2.21, if a′≡a and x′≡x(modn) then a′x′≡ax(modn), so whether ax≡1(modn) holds depends only on the classes [a]n and [x]n. The uniqueness part of the next theorem justifies the definite article in “the inverse”.

Theorem 2.24.

Let n≥1 and a∈ℤ. The class [a]n is a unit in ℤ/nℤ if and only if gcd(a,n)=1. When gcd(a,n)=1, the inverse is unique, and the extended Euclidean algorithm computes a representative: if au+nv=1, then [a]n−1=[u]n.

Proof.

Suppose gcd(a,n)=1. By Bézout (Theorem 2.11) there are u,v with au+nv=1. Reducing modulo n, au≡1(modn), so [u]n is an inverse of [a]n. The extended Euclidean algorithm (Theorem 2.13) produces such a u explicitly.

Conversely, if [a]n is a unit, say ax≡1(modn), then ax−1=nk for some k, i.e. ax−nk=1. Any common divisor of a and n divides the left side, hence divides 1; thus gcd(a,n)=1.

Uniqueness: if ax≡1 and ax′≡1(modn), then x≡x(ax′)≡(xa)x′≡x′(modn)—a computation using only the associativity and commutativity of integer multiplication together with Proposition 2.21—so [x]n=[x′]n. □

Example 2.25.

Consider the computation of [17]43−1. The extended Euclidean algorithm on (43,17):

43 =2⋅17+9,
17 =1⋅9+8,
9 =1⋅8+1,
8 =8⋅1+0,

so gcd(43,17)=1. Back-substituting:

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

Hence −5⋅17≡1(mod43), and [17]43−1=[−5]43=[38]43. Check: 17⋅38=646=15⋅43+1, so 17⋅38≡1(mod43).

Later sections use the number of units.

Definition 2.26 (Euler totient).

Euler’s totient function φ(n) is the number of integers a with 1≤a≤n and gcd(a,n)=1. Equivalently, φ(n)=|(ℤ/n⁢ℤ)×|.

The two counts agree: the classes of 1,2,…,n run exactly once through all of ℤ/nℤ (the class of n being [0]n), and by Theorem 2.24 the class [a]n is a unit precisely when gcd(a,n)=1.

Example 2.27.

We have φ(1)=1, and φ(p)=p−1 for prime p: for 1≤a<p the positive divisor gcd(a,p) of p is 1 or p, and p∤a rules out p, so every one of the p−1 nonzero classes is a unit. By direct enumeration, φ(12)=|{1,5,7,11}|=4.

Division by a modulo n is therefore multiplication by the inverse class [a]n−1. By Theorem 2.24 that inverse exists precisely when gcd(a,n)=1, hence for every nonzero class when the modulus is prime, and the extended Euclidean algorithm computes it in O(logn) division steps (Remark 2.10). The laws used in this section—associativity, commutativity, distributivity, identities, negatives, and inverses—are the defining laws of the structures that Sections 3 and 4 introduce, with ℤ/nℤ as an instance.