Math Guide Mathematical foundations for Halo 2 and Zcash Orchard 1 Notation: sets, functions, and relations 3 Groups

2 The integers and modular arithmetic

How does one divide in a finite world? The proof systems documented in this series do their arithmetic not with the unbounded integers of school algebra but with the finitely many remainders left upon division by a fixed, enormous prime. Every step a prover or verifier takes is an addition, a multiplication, or—the delicate case—a division of such remainders. Adding and multiplying remainders is easy to imagine: compute in $\mathbb{Z}$ , then discard multiples of the modulus. But what can it mean to divide, when “one half” names no remainder? The answer developed in this section is that division is multiplication by a modular inverse; that a remainder possesses an inverse exactly when a certain greatest common divisor equals one; and that an algorithm already in Euclid’s Elements, suitably extended, computes the inverse efficiently.

The integers $\mathbb{Z}=\{\dots,-2,-1,0,1,2,\dots\}$ are the arithmetical bedrock on which every algebraic and cryptographic structure in this monograph ultimately rests. 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, in the end, to computations with congruence classes of integers. This section develops the theory of the integers from a small set of assumptions and arrives at the integers modulo $n$ —the set $\mathbb{Z}/n\mathbb{Z}$ of congruence classes—together with its units and the algorithms that make arithmetic with them effective. We keep the treatment constructive throughout: every existence statement comes, wherever possible, with an algorithm that produces the object in question, since cryptography requires not merely that inverses and representatives exist but that one can compute them efficiently.

2.1 Well-ordering and the integers

We take the basic algebraic properties of $\mathbb{Z}$ 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 $\mathbb{Z}$ carries a total order $\leq$ compatible with the arithmetic. The single deep property we assume axiomatically is the following.

Theorem 2.1 (Well-ordering principle).

Every nonempty subset $S\subseteq\mathbb{N}=\{0,1,2,\dots\}$ of the natural numbers has a least element: there exists $m\in S$ such that $m\leq s$ for all $s\in S$ .

The well-ordering principle is logically equivalent to the principle of mathematical induction; we use both freely. It is also the engine of this section: nearly every existence result below is, at bottom, an application of well-ordering, in which one exhibits a nonempty set of natural numbers and extracts its minimum. Four instances map the road ahead. The remainder in the division algorithm is the least element of the set $\{\,a-bk:k\in\mathbb{Z},\ a-bk\geq 0\,\}$ ; the Euclidean algorithm terminates because a strictly decreasing sequence of nonnegative integers cannot be infinite; the Bézout identity extracts the least positive element of a set of integer combinations; and existence in the fundamental theorem of arithmetic proceeds by minimal counterexample.

2.2 Divisibility

Definition 2.2.

Let $a,b\in\mathbb{Z}$ . One says that $a$ divides $b$ , written $a\mid b$ , if there exists an integer $c\in\mathbb{Z}$ 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\nmid b$ .

Several immediate consequences of the definition deserve to be recorded; we shall use them constantly and usually without explicit citation.

Proposition 2.3.

Let $a,b,c,d\in\mathbb{Z}$ . Then:

1.

$a\mid a$ (reflexivity), $1\mid a$ , and $a\mid 0$ .
2.

If $a\mid b$ and $b\mid c$ then $a\mid c$ (transitivity).
3.

If $a\mid b$ and $a\mid c$ then $a\mid(bx+cy)$ for all $x,y\in\mathbb{Z}$ ; in particular $a\mid(b\pm c)$ .
4.

If $a\mid b$ and $b\neq 0$ then $|a|\leq|b|$ .
5.

If $a\mid b$ and $b\mid a$ then $a=\pm b$ .
6.

$0\mid b$ if and only if $b=0$ .

Proof.

(1) is immediate: $a=a\cdot 1$ , $a=1\cdot a$ , $0=a\cdot 0$ . For (2), write $b=ae$ and $c=bf$ ; then $c=a(ef)$ , so $a\mid c$ . For (3), write $b=ae$ and $c=af$ ; then $bx+cy=a(ex+fy)$ . For (4), write $b=ac$ with $b\neq 0$ , so $c\neq 0$ and hence $|c|\geq 1$ ; then $|b|=|a|\,|c|\geq|a|$ . For (5), if either is $0$ then by (6) so is the other and the claim holds; otherwise (4) gives $|a|\leq|b|$ and $|b|\leq|a|$ , so $|a|=|b|$ and $a=\pm b$ . For (6), $0\mid b$ means $b=0\cdot c=0$ ; conversely $0\mid 0$ . □

The relation $\mid$ is thus reflexive and transitive; it is a partial order in the sense of §1.3 when restricted to the natural numbers (where (5) becomes $a=b$ ), but on all of $\mathbb{Z}$ it fails to be antisymmetric precisely because of signs. The units of $\mathbb{Z}$ —the integers dividing $1$ —are exactly $\pm 1$ , and two integers that divide each other are called associates; in $\mathbb{Z}$ the associates of $a$ are $\pm a$ .

2.3 The division algorithm

Divisibility is the special case of exact division. The fundamental fact that makes the arithmetic of $\mathbb{Z}$ tractable is that one can always divide with remainder, and that the quotient and remainder are uniquely determined once a convention for the remainder’s range is fixed.

Theorem 2.4 (Division algorithm).

Let $a\in\mathbb{Z}$ and $b\in\mathbb{Z}$ with $b>0$ . Then there exist unique integers $q$ (the quotient) and $r$ (the remainder) such that

a=bq+r,\qquad 0\leq r<b.

Proof.

Existence. Consider the set

S=\{\,a-bk:k\in\mathbb{Z},\ a-bk\geq 0\,\}\subseteq\mathbb{N}.

First, $S\neq\varnothing$ . If $a\geq 0$ then $a=a-b\cdot 0\in S$ . If $a<0$ then, since $b\geq 1$ , taking $k=a$ gives $a-ba=a(1-b)\geq 0$ (a product of a nonpositive and a nonpositive factor), so $a-ba\in S$ . Thus $S$ is a nonempty subset of $\mathbb{N}$ , and by the well-ordering principle (Theorem 2.1) it has a least element $r=a-bq$ for some $q\in\mathbb{Z}$ . By construction $r\geq 0$ . If $r\geq b$ , then $r-b=a-b(q+1)\geq 0$ would lie in $S$ and be strictly smaller than $r$ , contradicting minimality. Hence $0\leq r<b$ .

Uniqueness. Suppose $a=bq+r=bq^{\prime}+r^{\prime}$ with $0\leq r,r^{\prime}<b$ . Then $b(q-q^{\prime})=r^{\prime}-r$ , so $b\mid(r^{\prime}-r)$ . But $-b<r^{\prime}-r<b$ , and the only multiple of $b$ strictly between $-b$ and $b$ is $0$ . Hence $r^{\prime}=r$ , and then $b(q-q^{\prime})=0$ with $b\neq 0$ forces $q=q^{\prime}$ . □

Remark 2.5.

The hypothesis $b>0$ is only for definiteness. For general $b\neq 0$ one obtains unique $q, r$ with $a=bq+r$ and $0\leq r<|b|$ , by applying the theorem to $|b|$ and adjusting the sign of $q$ . Note that the remainder convention $0\leq r<|b|$ differs from the truncation behaviour of many programming languages, where the remainder of a negative dividend may be negative; for the number-theoretic results below the convention above is the appropriate one.

We denote the remainder $r$ produced by the division algorithm by $a\bmod b$ , and the quotient $q$ by $\lfloor a/b\rfloor$ when $b>0$ (the floor of the rational number $a/b$ ). With this notation, $b\mid a$ holds precisely when $a\bmod b=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\mid a$ and $d\mid 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)\neq(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. We establish a much stronger characterisation shortly: the gcd is not merely the numerically largest common divisor but is divisible by every common divisor. The key computational engine is the following observation.

Lemma 2.7.

Let $a,b\in\mathbb{Z}$ . For any $q\in\mathbb{Z}$ ,

\gcd(a,b)=\gcd(b,\,a-qb).

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\mid a$ and $d\mid b$ , then $d\mid(a-qb)$ by Proposition 2.3(3), so $d$ is a common divisor of $b$ and $a-qb$ . Conversely, if $d\mid b$ and $d\mid(a-qb)$ , then $d\mid\bigl{(}(a-qb)+qb\bigr{)}=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\neq 0$ ; the case $a=0$ is the convention $\gcd(0,0)=0$ ). □

Iterating the lemma with the division algorithm yields the oldest nontrivial algorithm in mathematics.

Theorem 2.8 (Euclidean algorithm).

Let $a, b$ be integers with $b\neq 0$ . Define a sequence of remainders by $r_{0}=|a|$ , $r_{1}=|b|$ , and, as long as $r_{i}\neq 0$ , let $r_{i+1}=r_{i-1}\bmod r_{i}$ , so that

r_{i-1}=r_{i}q_{i}+r_{i+1},\qquad 0\leq r_{i+1}<r_{i}.

The sequence $r_{1}>r_{2}>\cdots$ of positive remainders is strictly decreasing, so some $r_{n+1}=0$ ; the last nonzero remainder satisfies $r_{n}=\gcd(a,b)$ .

Proof.

The remainders $r_{1},r_{2},\dots$ are nonnegative integers and, while nonzero, strictly decreasing because $r_{i+1}=r_{i-1}\bmod r_{i}<r_{i}$ . 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 $r_{n+1}=0$ and $r_{n}>0$ . By Lemma 2.7, each step preserves the gcd:

\gcd(a,b)=\gcd(r_{0},r_{1})=\gcd(r_{1},r_{2})=\cdots=\gcd(r_{n},r_{n+1})=\gcd(% r_{n},0)=r_{n},

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

Example 2.9.

Compute $\gcd(1071,462)$ :

	$\displaystyle 1071$	$\displaystyle=2\cdot 462+147,$
	$\displaystyle 462$	$\displaystyle=3\cdot 147+21,$
	$\displaystyle 147$	$\displaystyle=7\cdot 21+0.$

The last nonzero remainder is $21$ , so $\gcd(1071,462)=21$ . Indeed $1071=21\cdot 51$ and $462=21\cdot 22$ , with $\gcd(51,22)=1$ .

Remark 2.10.

The Euclidean algorithm is efficient. The number of division steps for inputs $a>b>0$ is $O(\log b)$ ; the worst case occurs at consecutive Fibonacci numbers (Lamé’s theorem), where every quotient $q_{i}$ 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(k^{2})$ bit operations. This efficiency is what renders gcd-based cryptographic operations—above all modular inversion, below—practical at the sizes used in Halo 2 and Orchard.

2.5 The Bézout identity and the extended Euclidean algorithm

The Euclidean algorithm computes the gcd, but the back-substitution of its equations yields something more powerful: the gcd is an integer linear combination of the inputs. This is among the most useful facts in elementary number theory.

Theorem 2.11 (Bézout’s identity).

Let $a,b\in\mathbb{Z}$ , not both zero, and let $d=\gcd(a,b)$ . Then there exist integers $u,v\in\mathbb{Z}$ with

au+bv=d.

Moreover $d$ is the smallest positive integer expressible in the form $ax+by$ with $x,y\in\mathbb{Z}$ , and the set of all such combinations is exactly the set of multiples of $d$ :

\{\,ax+by:x,y\in\mathbb{Z}\,\}=d\mathbb{Z}=\{\,kd:k\in\mathbb{Z}\,\}.

Proof.

Let $I=\{\,ax+by:x,y\in\mathbb{Z}\,\}$ . This set contains $a$ and $b$ and is closed under addition and under multiplication by any integer; concretely, if $s=ax_{1}+by_{1}$ and $t=ax_{2}+by_{2}$ lie in $I$ , then for any $m,n\in\mathbb{Z}$ one has

ms+nt=a(mx_{1}+nx_{2})+b(my_{1}+ny_{2})\in I.

Since $a, b$ are not both zero, $I$ contains a positive element (one of $\pm a,\pm b$ ), so the set $I\cap\mathbb{N}_{>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\in I$ and write $c=gq+r$ with $0\leq r<g$ by the division algorithm. Then $r=c-gq\in I$ because $I$ is closed under the operations just described. By minimality of $g$ among positive elements of $I$ , and $0\leq r<g$ , necessarily $r=0$ . Hence $g\mid c$ for every $c\in I$ ; in particular $g\mid a$ and $g\mid 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\mathbb{Z}=d\mathbb{Z}$ 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 $\leq$ : $d=\gcd(a,b)$ is, up to sign, the unique common divisor of $a$ and $b$ that is divisible by every common divisor. This is the formulation that survives in settings where “largest” may make no sense but “divisible by every common divisor” still does; later sections adopt it when they leave the integers. We call a nonempty subset $I\subseteq\mathbb{Z}$ closed under addition and under multiplication by arbitrary integers an ideal; the content of Bézout’s identity is that every ideal of $\mathbb{Z}$ has the form $d\mathbb{Z}$ for a single generator $d$ . Ideals recur in 4, where they drive a general construction whose prototype is the passage from integers to congruence classes carried out later in this section.

The Bézout coefficients $u, v$ are not unique. If $au+bv=d$ , then for every $k\in\mathbb{Z}$ ,

a\Bigl{(}u+k\tfrac{b}{d}\Bigr{)}+b\Bigl{(}v-k\tfrac{a}{d}\Bigr{)}=d,

since the added terms $k\tfrac{ab}{d}$ and $-k\tfrac{ab}{d}$ cancel; and these are all the solutions. To see this, note first that $a/d$ and $b/d$ are coprime: a common divisor $e$ of both makes $d e$ a common divisor of $a$ and $b$ , so $de\mid au+bv=d$ by Proposition 2.3(3), forcing $e=\pm 1$ . Now suppose $au^{\prime}+bv^{\prime}=d$ . Subtracting $au+bv=d$ and dividing by $d>0$ gives $\tfrac{a}{d}(u^{\prime}-u)=-\tfrac{b}{d}(v^{\prime}-v)$ , so $b/d$ divides $\tfrac{a}{d}(u^{\prime}-u)$ ; by Proposition 2.15(1) below (whose proof rests only on Bézout’s identity, already established), $b/d$ divides $u^{\prime}-u$ , say $u^{\prime}=u+k\tfrac{b}{d}$ with $k\in\mathbb{Z}$ . Substituting back gives $b\bigl{(}v^{\prime}-v+k\tfrac{a}{d}\bigr{)}=0$ , so $v^{\prime}=v-k\tfrac{a}{d}$ when $b\neq 0$ ; and when $b=0$ we have $u^{\prime}=u$ , $a/d=\pm 1$ , and $k=(v-v^{\prime})\,\tfrac{a}{d}$ places $(u^{\prime},v^{\prime})$ in the family. To compute a particular pair $(u,v)$ efficiently, we augment the Euclidean algorithm so that it carries each remainder as an explicit combination of $a$ and $b$ .

Theorem 2.13 (Extended Euclidean algorithm).

There is an algorithm that, on input $a,b\in\mathbb{Z}$ 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 $(s_{i})$ and $(t_{i})$ with the invariant

r_{i}=a\,s_{i}+b\,t_{i}\qquad\text{for all }i.

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

r_{0}=a,\ s_{0}=1,\ t_{0}=0;\qquad r_{1}=b,\ s_{1}=0,\ t_{1}=1,

so (2.5) holds for $i=0,1$ . At step $i\geq 1$ , having $r_{i-1}=r_{i}q_{i}+r_{i+1}$ from the division algorithm, set

s_{i+1}=s_{i-1}-q_{i}s_{i},\qquad t_{i+1}=t_{i-1}-q_{i}t_{i}.

Then

a\,s_{i+1}+b\,t_{i+1}=(as_{i-1}+bt_{i-1})-q_{i}\,(as_{i}+bt_{i})=r_{i-1}-q_{i}% r_{i}=r_{i+1},

so induction preserves (2.5). When the algorithm terminates with $r_{n+1}=0$ and $r_{n}=d=\gcd(a,b)$ , the invariant for $i=n$ reads $d=as_{n}+bt_{n}$ ; output $u=s_{n}$ , $v=t_{n}$ . If $b=0$ , then $a\neq 0$ and termination is immediate with $n=0$ : no division step runs, the last nonzero remainder is $r_{0}=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\neq 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^{\prime}+|b|\,v^{\prime}=d$ (recall $\gcd(|a|,|b|)=\gcd(a,b)$ ) and output $u=\operatorname{sgn}(a)\,u^{\prime}$ , $v=\operatorname{sgn}(b)\,v^{\prime}$ , so that $au+bv=d$ . □

In practice it is convenient to lay the computation out as a table with columns $(r_{i},q_{i},s_{i},t_{i})$ , computing each new row from the previous two.

Example 2.14.

Run the extended algorithm on $a=1071$ , $b=462$ (continuing Example 2.9). The quotients are $q_{1}=2,q_{2}=3,q_{3}=7$ .

\begin{array}[]{c|c|c|c}i&r_{i}&s_{i}&t_{i}\\ \hline\cr 0&1071&1&0\\ 1&462&0&1\\ 2&147&1&-2\\ 3&21&-3&7\\ 4&0&22&-51\end{array}

For instance, row $2$ is row $0$ minus $q_{1}=2$ times row $1$ : $s_{2}=1-2\cdot 0=1$ , $t_{2}=0-2\cdot 1=-2$ , and indeed $1071\cdot 1+462\cdot(-2)=1071-924=147$ . The last nonzero remainder is $r_{3}=21=\gcd(1071,462)$ , with

1071\cdot(-3)+462\cdot 7=-3213+3234=21.

Thus $(u,v)=(-3,7)$ . The final row $(s_{4},t_{4})=(22,-51)=(b/d,-a/d)$ up to sign records the homogeneous solution: $1071\cdot 22+462\cdot(-51)=0$ .

A first, decisive application of Bézout’s identity is Euclid’s lemma, the property of primes that ultimately forces unique factorisation.

Proposition 2.15 (Euclid’s lemma).

Let $a,b,c\in\mathbb{Z}$ .

1.

If $c\mid ab$ and $\gcd(c,a)=1$ , then $c\mid b$ .
2.

If $\gcd(a,b)=1$ , $a\mid n$ , and $b\mid n$ , then $ab\mid n$ .
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\mid ab$ , $c$ divides both terms on the right, hence $c\mid b$ .

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

(3) By Bézout, $ax_{1}+by_{1}=1$ and $ax_{2}+cy_{2}=1$ for suitable integers. Multiplying,

1=(ax_{1}+by_{1})(ax_{2}+cy_{2})=a\underbrace{(ax_{1}x_{2}+x_{1}cy_{2}+by_{1}x% _{2})}_{\in\mathbb{Z}}+bc\,(y_{1}y_{2}),

which exhibits $1$ as an integer combination of $a$ and $b c$ . 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.

The exclusion of $1$ from the primes is not arbitrary: it is exactly what makes factorisation into primes unique, since otherwise one could insert arbitrarily many factors of $1$ . The decisive property of primes is the prime case of Euclid’s lemma.

Lemma 2.17 (Euclid’s lemma for primes).

Let $p$ be prime and $a,b\in\mathbb{Z}$ . If $p\mid ab$ then $p\mid a$ or $p\mid b$ . More generally, if $p\mid a_{1}a_{2}\cdots a_{k}$ then $p\mid a_{i}$ for some $i$ .

Proof.

The only positive divisors of $p$ are $1$ and $p$ , so $\gcd(p,a)\in\{1,p\}$ . If $\gcd(p,a)=p$ then $p\mid a$ and the claim holds; otherwise $\gcd(p,a)=1$ , and Proposition 2.15(1) gives $p\mid b$ . The general statement follows by induction on $k$ : from $p\mid a_{1}(a_{2}\cdots a_{k})$ it follows that $p\mid a_{1}$ or $p\mid a_{2}\cdots a_{k}$ , 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=p_{1}p_{2}\cdots p_{k},

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

n=p_{1}^{e_{1}}p_{2}^{e_{2}}\cdots p_{r}^{e_{r}},\qquad p_{1}<p_{2}<\cdots<p_{% r}\text{ prime},\ e_{i}\geq 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

p_{1}p_{2}\cdots p_{k}=q_{1}q_{2}\cdots q_{\ell}

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 $\ell=0$ as well (a nonempty product of primes is $>1$ ). For the inductive step, $p_{1}$ divides the right-hand product, so by Lemma 2.17 $p_{1}\mid q_{j}$ for some $j$ . Since $q_{j}$ is prime, its only divisor $>1$ is itself, so $p_{1}=q_{j}$ . Cancelling this common factor (legitimate as $\mathbb{Z}$ has no zero divisors) yields

p_{2}\cdots p_{k}=q_{1}\cdots\widehat{q_{j}}\cdots q_{\ell},

where the hat denotes omission. By the inductive hypothesis these two factorisations agree up to order, with $k-1=\ell-1$ ; restoring $p_{1}=q_{j}$ 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.

Both halves of the theorem are needed and have different characters. Existence is a statement about the order structure (well-ordering) and would hold in any reasonable factorisation; uniqueness rests squarely on Euclid’s lemma, hence on Bézout, hence on the division algorithm. There are number systems with a division-like structure failing Euclid’s lemma in which factorisation into irreducibles is not unique; the integers avoid this pathology precisely because they admit division with remainder, from which the whole chain above flows.

2.7 Congruences and residue classes

The development now passes from divisibility to the arithmetic of remainders. Fix an integer $n\geq 1$ , the modulus.

Definition 2.20.

Let $n\geq 1$ and $a,b\in\mathbb{Z}$ . The integer $a$ is congruent to $b$ modulo $n$ , written

a\equiv b\pmod{n},

if $n\mid(a-b)$ , equivalently if $a$ and $b$ leave the same remainder upon division by $n$ .

The two formulations agree: if $a=nq_{1}+r_{1}$ and $b=nq_{2}+r_{2}$ with $0\leq r_{1},r_{2}<n$ , then $a-b=n(q_{1}-q_{2})+(r_{1}-r_{2})$ , and $n\mid(a-b)$ iff $n\mid(r_{1}-r_{2})$ iff $r_{1}=r_{2}$ (since $|r_{1}-r_{2}|<n$ ).

Proposition 2.21.

Fix $n\geq 1$ . Congruence modulo $n$ is an equivalence relation on $\mathbb{Z}$ that is moreover compatible with addition and multiplication: if $a\equiv a^{\prime}$ and $b\equiv b^{\prime}\pmod{n}$ , then

a+b\equiv a^{\prime}+b^{\prime}\pmod{n},\qquad ab\equiv a^{\prime}b^{\prime}% \pmod{n}.

Consequently $a^{k}\equiv(a^{\prime})^{k}\pmod{n}$ for all $k\geq 0$ , and one may substitute congruent values freely in any polynomial expression with integer coefficients.

Proof.

Reflexivity ( $n\mid 0$ ), symmetry ( $n\mid(a-b)\Rightarrow n\mid(b-a)$ ), and transitivity ( $n\mid(a-b)$ and $n\mid(b-c)$ give $n\mid(a-c)$ by Proposition 2.3(3)) are immediate. For compatibility, write $a-a^{\prime}=ns$ and $b-b^{\prime}=nt$ . Then

(a+b)-(a^{\prime}+b^{\prime})=n(s+t),

and

ab-a^{\prime}b^{\prime}=ab-a^{\prime}b+a^{\prime}b-a^{\prime}b^{\prime}=(a-a^{% \prime})b+a^{\prime}(b-b^{\prime})=n(sb+a^{\prime}t),

so both $n\mid\bigl{(}(a+b)-(a^{\prime}+b^{\prime})\bigr{)}$ and $n\mid(ab-a^{\prime}b^{\prime})$ . The statement about powers and polynomial expressions follows by induction from the multiplicative case. □

Because congruence is an equivalence relation, it partitions $\mathbb{Z}$ 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\in\mathbb{Z}:b\equiv a\pmod{n}\,\}=\{\,a+kn:k\in\mathbb{Z}\,\}=a% +n\mathbb{Z}.

We write the set of all congruence classes as

\mathbb{Z}/n\mathbb{Z}=\{\,[a]_{n}:a\in\mathbb{Z}\,\}.

By the division algorithm every integer is congruent modulo $n$ to exactly one of $0,1,\dots,n-1$ , namely its remainder; hence the $n$ classes $[0]_{n},[1]_{n},\dots,[n-1]_{n}$ are distinct and exhaust $\mathbb{Z}/n\mathbb{Z}$ . The set $\{0,1,\dots,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 the opening problem of the section comes down to a multiplicative question about congruences: for which $a$ does the congruence $ax\equiv 1\pmod{n}$ admit a solution? The Euclidean machinery characterises the solvable cases completely and computes the solutions.

Definition 2.23.

Let $n\geq 1$ . A class $[a]_{n}\in\mathbb{Z}/n\mathbb{Z}$ is a unit (or is invertible) if there exists an integer $x$ with $ax\equiv 1\pmod{n}$ . 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

(\mathbb{Z}/n\mathbb{Z})^{\times}=\{\,[a]_{n}:[a]_{n}\text{ is a unit}\,\}.

The definition is well posed on classes: by Proposition 2.21, if $a^{\prime}\equiv a$ and $x^{\prime}\equiv x\pmod{n}$ then $a^{\prime}x^{\prime}\equiv ax\pmod{n}$ , so whether $ax\equiv 1\pmod{n}$ holds depends only on the classes $[a]_{n}$ and $[x]_{n}$ , never on the representatives chosen. The definite article in “the inverse” is justified by the uniqueness part of the next theorem—the payoff of the section.

Theorem 2.24.

Let $n\geq 1$ and $a\in\mathbb{Z}$ . The class $[a]_{n}$ is a unit in $\mathbb{Z}/n\mathbb{Z}$ 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\equiv 1\pmod{n}$ , 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\equiv 1\pmod{n}$ , 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\equiv 1$ and $ax^{\prime}\equiv 1\pmod{n}$ , then $x\equiv x(ax^{\prime})\equiv(xa)x^{\prime}\equiv x^{\prime}\pmod{n}$ —a sandwich using only the associativity and commutativity of integer multiplication together with Proposition 2.21—so $[x]_{n}=[x^{\prime}]_{n}$ . □

Example 2.25.

Consider the computation of $[17]_{43}^{-1}$ . The extended Euclidean algorithm on $(43,17)$ :

	$\displaystyle 43$	$\displaystyle=2\cdot 17+9,$
	$\displaystyle 17$	$\displaystyle=1\cdot 9+8,$
	$\displaystyle 9$	$\displaystyle=1\cdot 8+1,$
	$\displaystyle 8$	$\displaystyle=8\cdot 1+0,$

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

1=9-8=9-(17-9)=2\cdot 9-17=2(43-2\cdot 17)-17=2\cdot 43-5\cdot 17.

Hence $-5\cdot 17\equiv 1\pmod{43}$ , and $[17]_{43}^{-1}=[-5]_{43}=[38]_{43}$ . Check: $17\cdot 38=646=15\cdot 43+1$ , so $17\cdot 38\equiv 1\pmod{43}$ .

Counting the units will matter as much as finding them: the count defined next carries structural weight in later sections, and we fix it here so that those sections can cite a definition rather than re-derive one.

Definition 2.26 (Euler totient).

Euler’s totient function $\varphi(n)$ is the number of integers $a$ with $1\leq a\leq n$ and $\gcd(a,n)=1$ . Equivalently, $\varphi(n)=\lvert(\mathbb{Z}/n\mathbb{Z})^{\times}\rvert$ .

The two counts agree: the classes of $1,2,\dots,n$ run exactly once through all of $\mathbb{Z}/n\mathbb{Z}$ (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 $\varphi(1)=1$ , and $\varphi(p)=p-1$ for prime $p$ : for $1\leq a<p$ the positive divisor $\gcd(a,p)$ of $p$ is $1$ or $p$ , and $p\nmid a$ rules out $p$ , so every one of the $p-1$ nonzero classes is a unit. By direct enumeration, $\varphi(12)=\lvert\{1,5,7,11\}\rvert=4$ .

The cheque presented at the head of the section is now cashed. To divide by $a$ in the finite world of remainders modulo $n$ is to multiply by the inverse class $[a]_{n}^{-1}$ ; Theorem 2.24 says exactly when 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(\log n)$ division steps (Remark 2.10). The laws verified along the way—associativity, commutativity, distributivity, identities, negatives, and now inverses—have been stated concretely, for the integers and their congruence classes alone. They are instances of patterns that pervade mathematics; Sections 3 and 4 isolate those patterns, give them their standard names, and re-read $\mathbb{Z}/n\mathbb{Z}$ in their light. Nothing proved there revises anything proved here.