University Mathematics — Year 1 · Bachelor Year 1

6Integer Arithmetic

Arithmetic — the study of divisibility in $\Z$ — was begun in the High School volume. This chapter rebuilds it completely from the Euclidean division, with full proofs: greatest common divisor and the Euclidean algorithm, Bézout’s identity and Gauss’s lemma, prime factorization, and the calculus of congruences up to Fermat’s little theorem. Beyond its own charm, this material is the model that Chapter 8 imitates for polynomials.

6.1 Divisibility and Euclidean division

Definition 6.1 (Divisibility)

For $a, b \in \Z$ , $b$ divides $a$ (written $b \mid a$ ) when $a = bq$ for some $q \in \Z$ . Basic consequences: if $b \mid a$ and $b \mid a'$ then $b \mid (ua + va')$ for all $u, v \in \Z$ ; if $b \mid a$ and $a \neq 0$ then $\abs b \leq \abs a$ ; and $a \mid b$ together with $b \mid a$ force $b = \pm a$ .

Theorem 6.2 (Euclidean division)

For all $a \in \Z$ and $b \in \N^*$ , there is exactly one pair $(q, r) \in \Z \times \N$ with

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

Proof. Existence. The set $A = \{a - bk : k \in \Z\} \cap \N$ is a nonempty subset of $\N$ (take $k = -\abs a$ : $a + b\abs a \geq a + \abs a \geq 0$ ). Let $r = a - bq$ be its least element. If $r \geq b$ , then $r - b = a - b(q+1)$ would be a smaller element of $A$ : contradiction. So $0 \leq r < b$ .

Uniqueness. If $bq + r = bq' + r'$ with $0 \leq r, r' < b$ , then $b(q - q') = r' - r$ and $\abs{r' - r} < b$ : the multiple of $b$ in the left-hand side must be $0$ , so $q = q'$ and $r = r'$ . ∎

Example 6.3 (Positional numeration by repeated division)

Write $2026$ in base $7$ . Divide repeatedly by $7$ , keeping the remainders:

2026 = 7 \times 289 + 3, \quad 289 = 7 \times 41 + 2, \quad 41 = 7 \times 5 + 6, \quad 5 = 7 \times 0 + 5 .

Reading the remainders from last to first: $2026 = (5\,6\,2\,3)_7$ . Check: $5 \times 343 + 6 \times 49 + 2 \times 7 + 3 = 1715 + 294 + 14 + 3 = 2026$ . The uniqueness of Euclidean division is exactly what makes each digit forced: at every step the remainder is the only integer in $\intint06$ congruent to the current value mod $7$ , so base- $7$ writing is unique — the fact silently used whenever the weekend problem manipulates “the digits of $n$ in base $p$ ”.

6.2 Greatest common divisor

Theorem 6.4 (Subgroups of $\Z$ ; existence of the gcd)

Every subgroup of $(\Z, +)$ is of the form $n\Z = \{nk : k \in \Z\}$ for a unique $n \in \N$ .
For $a, b \in \Z$ not both zero, the set $a\Z + b\Z = \{au + bv : u, v \in \Z\}$ is a subgroup of $\Z$ , hence equals $d\,\Z$ for a unique $d \in \N^*$ . This $d$ is the greatest common divisor $\gcd(a, b)$ : it divides $a$ and $b$ , and every common divisor of $a$ and $b$ divides $d$ .

Proof. (1) Let $H \subseteq \Z$ be a subgroup (nonempty, stable under subtraction; the formal definition is in Chapter 7, and only these two properties are used). If $H = \{0\}$ , take $n = 0$ . Otherwise $H$ contains a nonzero element and its opposite, hence a smallest strictly positive element $n$ . Then $n\Z \subseteq H$ . For $x \in H$ , write $x = nq + r$ with $0 \leq r < n$ (Theorem 6.2); $r = x - nq \in H$ , and minimality of $n$ forces $r = 0$ : $x \in n\Z$ . Uniqueness: $n$ is the least positive element of $n\Z$ .

(2) $a\Z + b\Z$ contains $0$ and is stable under subtraction, so it is $d\Z$ with $d \geq 1$ (it contains $a$ or $b$ nonzero). Since $a, b \in d\Z$ , $d$ divides both. And if $c$ divides $a$ and $b$ , then $c$ divides every $au + bv$ — in particular $c \mid d$ , since $d \in a\Z + b\Z$ . This is the property announced (and it implies $\abs c \leq d$ , so $d$ deserves the name greatest common divisor). ∎

Corollary 6.5 (Bézout’s identity)

For $a, b$ not both zero, there exist $u, v \in \Z$ with

au + bv = \gcd(a, b) .

In particular ( $\gcd(a,b) = 1$ , the coprime case): $a$ and $b$ are coprime if and only if $au + bv = 1$ has a solution.

Proof. $\gcd(a,b) = d \in d\Z = a\Z + b\Z$ . For the equivalence: if $\gcd(a,b) = 1$ , Bézout provides the solution; conversely $au + bv = 1$ forces every common divisor of $a, b$ to divide $1$ . ∎

Method 6.6 (Euclidean algorithm, extended)

To compute $\gcd(a, b)$ ( $a > b > 0$ ): divide $a = bq + r$ ; then $\gcd(a, b) = \gcd(b, r)$ (common divisors of $(a,b)$ and of $(b,r)$ coincide, since $r = a - bq$ ); iterate until the remainder is $0$ ; the last nonzero remainder is the gcd. Running the divisions backwards (or maintaining the coefficients on the way down) produces a Bézout pair $(u, v)$ .

Example 6.7

$\gcd(120, 23)$ : $120 = 5 \times 23 + 5$ ; $23 = 4 \times 5 + 3$ ; $5 = 1\times 3 + 2$ ; $3 = 1 \times 2 + 1$ ; $2 = 2 \times 1 + 0$ . So $\gcd = 1$ . Backwards:

\begin{align*} 1 &= 3 - 2 = 3 - (5 - 3) = 2\times 3 - 5 = 2(23 - 4\times 5) - 5 \\ &= 2 \times 23 - 9 \times 5 = 2\times 23 - 9(120 - 5\times 23) = 47 \times 23 - 9 \times 120 . \end{align*}

Check: $47 \times 23 = 1081$ , $9 \times 120 = 1080$ .

Theorem 6.8 (Gauss’s lemma and consequences)

Let $a, b, c \in \Z$ .

(Gauss’s lemma) If $a \mid bc$ and $\gcd(a, b) = 1$ , then $a \mid c$ .
If $a \mid c$ , $b \mid c$ and $\gcd(a,b) = 1$ , then $ab \mid c$ .
If $\gcd(a, b) = \gcd(a, c) = 1$ , then $\gcd(a, bc) = 1$ .

Proof. (1) Bézout: $au + bv = 1$ . Multiply by $c$ : $acu + bcv = c$ . Both terms are divisible by $a$ (the second because $a \mid bc$ ), so $a \mid c$ .

(2) Write $c = aq$ ; from $b \mid aq$ and $\gcd(a, b) = 1$ , point (1) gives $b \mid q$ , so $ab \mid aq = c$ .

(3) $au + bv = 1$ and $au' + cv' = 1$ . Multiply the two relations:

1 = (au + bv)(au' + cv') = a\,\bigl(auu' + ucv' + u'bv\bigr) + bc\,(vv') ,

a Bézout relation between $a$ and $bc$ : by Corollary 6.5, $\gcd(a, bc) = 1$ . ∎

Example 6.9 (Solving a linear Diophantine equation)

Find all $(x, y) \in \Z^2$ with $6x + 10y = 4$ . First, the existence test: $\gcd(6, 10) = 2$ divides $4$ , so solutions exist (if the gcd did not divide the right-hand side, the left side would always be a multiple of it and there would be none). Divide through: $3x + 5y = 2$ . A particular solution is visible: $(x_0, y_0) = (-1, 1)$ . For the general one, subtract: $3(x + 1) = -5(y - 1)$ , so $3 \mid 5(y-1)$ , and Gauss’s lemma ( $\gcd(3,5) = 1$ ) gives $3 \mid y - 1$ : $y = 1 - 3k$ , then $x = -1 + 5k$ . Conversely every such pair works:

(x, y) = (-1 + 5k,\ 1 - 3k), \qquad k \in \Z .

The pattern is general: one particular solution plus the integer multiples of $\bigl(\frac b{\gcd}, -\frac a{\gcd}\bigr)$ — the same “particular plus homogeneous” structure as in Chapter 5, with Gauss’s lemma playing the uniqueness role.

Definition 6.10 (Least common multiple)

$\operatorname{lcm}(a, b)$ is the generator in $\N$ of the subgroup $a\Z \cap b\Z$ : it is a common multiple of $a$ and $b$ that divides every common multiple, and for $a, b \in \N^*$ ,

\gcd(a,b) \times \operatorname{lcm}(a,b) = ab \qquad (\text{proof in } \text{Exercise 6.5}).

Example 6.11 (Alignment problems are lcm problems)

Two meshed gears have $84$ and $36$ teeth. After how many teeth of common motion do they return to their initial position together? The configuration repeats when the number of elapsed teeth is a common multiple of $84$ and $36$ ; the first time is

\operatorname{lcm}(84, 36) = \frac{84 \times 36}{\gcd(84, 36)} = \frac{3024}{12} = 252

teeth — that is, $3$ turns of the large gear and $7$ of the small one ( $252/84$ and $252/36$ ). Note the practical route: compute the gcd first (Euclid: $84 = 2\times36 + 12$ , $36 = 3\times12$ ), then divide — never build the lcm by listing multiples. Every periodic-coincidence question (gears, planetary alignments, repeating decimals meeting) reduces to this one computation.

6.3 Prime numbers

Definition 6.12

An integer $p \geq 2$ is prime when its only positive divisors are $1$ and $p$ . For $p$ prime and $a \in \Z$ : either $p \mid a$ , or $\gcd(p, a) = 1$ . Consequently (Theorem 6.8), Euclid’s lemma holds: if $p \mid ab$ then $p \mid a$ or $p \mid b$ .

Remark 6.13 (Testing primality by trial division)

If $n = ab$ with $2 \leq a \leq b$ , then $a^2 \leq ab = n$ , so $a \leq \sqrt n$ : a composite $n$ always has a prime divisor $\leq \sqrt n$ . Hence to test whether $n$ is prime it suffices to try the primes up to $\sqrt n$ . For $n = 271$ : $\sqrt{271} < 17$ , and $271$ is divisible by none of $2, 3, 5, 7, 11, 13$ (odd, digit sum $10$ , does not end in $0$ or $5$ , $271 = 7\cdot38 + 5 = 11\cdot24 + 7 = 13\cdot20 + 11$ ): prime, after six divisions instead of two hundred. The $\sqrt n$ barrier is a genuine threshold: crossing it efficiently for hundred-digit numbers requires the modern primality tests grown out of Theorem 6.23.

Theorem 6.14 (Euclid)

There are infinitely many primes.

Proof. Every integer $n \geq 2$ has a prime divisor: its smallest divisor $\geq 2$ is prime (a proper factorization of it would produce a smaller divisor of $n$ ). Now suppose $p_1, \dots, p_k$ were all the primes, and let $N = p_1 p_2 \cdots p_k + 1 \geq 2$ . Some prime $p_i$ divides $N$ ; but $p_i$ also divides $N - 1 = p_1\cdots p_k$ , so $p_i \mid 1$ — absurd. ∎

Theorem 6.15 (Fundamental theorem of arithmetic)

Every integer $n \geq 2$ is a product of primes, and the factorization

n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k} \qquad (p_1 < p_2 < \dots < p_k \text{ primes},\ \alpha_i \in \N^*)

is unique.

Proof. Existence by strong induction (Theorem 1.12): $n = 2$ is prime; for $n > 2$ , either $n$ is prime, or $n = ab$ with $2 \leq a, b < n$ , and the induction hypothesis factors $a$ and $b$ .

Uniqueness. Suppose $p_1 \cdots p_r = q_1 \cdots q_s$ (primes listed with repetition, $r \leq s$ say), and induct on $r$ . If $r = 0$ the left side is $1$ , forcing $s = 0$ (a nonempty product of primes exceeds $1$ ). For $r \geq 1$ : the prime $p_1$ divides $q_1(q_2\cdots q_s)$ , so by Euclid’s lemma either $p_1 \mid q_1$ or $p_1 \mid q_2\cdots q_s$ ; iterating, $p_1$ divides some $q_j$ . But $q_j$ is prime and $p_1 \geq 2$ : necessarily $p_1 = q_j$ . Cancel this common factor (legitimate: $\Z$ is an integral domain) to get

p_2 \cdots p_r = q_1 \cdots \widehat{q_j} \cdots q_s

(the hat marking omission), an equality of shorter products; the induction hypothesis says the two lists $p_2, \dots, p_r$ and $q_1, \dots, \widehat{q_j}, \dots, q_s$ coincide up to order, hence so did the original ones. The exponent form groups equal primes. ∎

Proposition 6.16 (Valuations)

For $p$ prime and $n \in \N^*$ , write $v_p(n)$ for the exponent of $p$ in the factorization of $n$ (with $v_p(n) = 0$ if $p \nmid n$ ). Then

v_p(mn) = v_p(m) + v_p(n), \qquad m \mid n \iff \forall p,\ v_p(m) \leq v_p(n),

v_p\bigl(\gcd(m,n)\bigr) = \min\bigl(v_p(m), v_p(n)\bigr), \qquad v_p\bigl(\operatorname{lcm}(m,n)\bigr) = \max\bigl(v_p(m), v_p(n)\bigr).

Proof. The first identity holds because the factorizations multiply and the factorization of $mn$ is unique. If $m \mid n$ , write $n = mq$ and apply it. Conversely, if all $v_p(m) \leq v_p(n)$ , the integer $q = \prod_p p^{\,v_p(n) - v_p(m)}$ satisfies $mq = n$ . The gcd formula: the integer $d = \prod p^{\min}$ divides both by the criterion, and every common divisor $c$ has $v_p(c) \leq \min$ for all $p$ , so $c \mid d$ ; same reasoning for the lcm with $\max$ . ∎

Example 6.17 (Squares and cubes through valuations)

An integer $n \geq 1$ is a perfect square if and only if every $v_p(n)$ is even (if $n = m^2$ , then $v_p(n) = 2v_p(m)$ ; conversely halve every exponent). Likewise for cubes with multiples of $3$ . Thus $21168 = 2^4 \times 3^3 \times 7^2$ is not a square ( $v_3 = 3$ is odd) and not a cube ( $v_2 = 4$ ); the smallest positive integer $m$ such that $21168\,m$ is a cube is found by topping up each exponent to the next multiple of $3$ :

m = 2^{6-4} \times 3^{3-3} \times 7^{3-2} = 2^2 \times 7 = 28, \qquad 21168 \times 28 = 2^6\,3^3\,7^3 = (2^2 \times 3 \times 7)^3 = 84^3 .

The insight: multiplicative questions (squares, cubes, divisors, gcd, lcm) become coordinatewise questions on the exponent vectors $(v_2, v_3, v_5, \dots)$ — unique factorization is the statement that these coordinates exist and are well defined.

6.4 Congruences

Definition 6.18

For $n \in \N^*$ : $a \equiv b \pmod n$ when $n \mid a - b$ . This is an equivalence relation compatible with addition and multiplication: if $a \equiv b$ and $a' \equiv b'$ (mod $n$ ), then $a + a' \equiv b + b'$ , $aa' \equiv bb'$ , and $a^k \equiv b^k$ for $k \in \N$ .

Example 6.19 (Casting out nines)

Compatibility with $+$ and $\times$ is a checking device as old as commerce. Since $10 \equiv 1 \pmod 9$ , every integer is congruent mod $9$ to its digit sum (proved as Exercise 6.2). To check the claim $1234 \times 567 = 699\,678$ : digit sums give $1234 \equiv 1$ and $567 \equiv 18 \equiv 0 \pmod 9$ , so the product must be $\equiv 1 \times 0 = 0$ ; and indeed $6 + 9 + 9 + 6 + 7 + 8 = 45 \equiv 0$ . The check passes (and the product is in fact correct). Had someone reported $699\,478$ , the digit sum $43 \equiv 7 \not\equiv 0$ would convict them instantly. The test is one-sided — it catches an error unless the error is itself a multiple of $9$ — which is exactly the pseudoprime lesson of Example 6.24 in miniature: congruence checks refute, they do not certify.

Proposition 6.20 (Invertibility mod $n$ )

$a$ is invertible mod $n$ (i.e. $ab \equiv 1 \pmod n$ for some $b$ ) if and only if $\gcd(a, n) = 1$ . The inverse is then unique mod $n$ and computed by the extended Euclidean algorithm.

Proof. $ab \equiv 1 \pmod n$ means $ab + nk = 1$ for some $k$ : a Bézout relation, which exists iff $\gcd(a,n) = 1$ (Corollary 6.5). Uniqueness: if $ab \equiv ab' \equiv 1$ , then $b \equiv b(ab') = (ab)b' \equiv b' \pmod n$ . ∎

Example 6.21 (Inverting $7$ modulo $26$ )

Since $\gcd(7, 26) = 1$ , the class of $7$ is invertible mod $26$ . Extended Euclid:

26 = 3 \times 7 + 5, \qquad 7 = 1 \times 5 + 2, \qquad 5 = 2 \times 2 + 1 ,

then backwards:

1 = 5 - 2 \times 2 = 5 - 2(7 - 5) = 3 \times 5 - 2 \times 7 = 3(26 - 3 \times 7) - 2 \times 7 = 3 \times 26 - 11 \times 7 .

Hence $7 \times (-11) \equiv 1 \pmod{26}$ , i.e. $7^{-1} \equiv -11 \equiv 15 \pmod{26}$ ; check: $7 \times 15 = 105 = 4 \times 26 + 1$ . With the inverse in hand, any congruence $7x \equiv c \pmod{26}$ is solved in one multiplication: $x \equiv 15c$ . This mechanical inversion is the workhorse of modular arithmetic — and of the public-key protocols mentioned in Remark 6.27, where the moduli have hundreds of digits but the algorithm is exactly this one.

Example 6.22 (When the coefficient is not invertible)

Solve $12x \equiv 8 \pmod{20}$ . Here $\gcd(12, 20) = 4$ , so $12$ is not invertible mod $20$ — but the equation is still tractable. The congruence says $20 \mid 12x - 8$ ; dividing the whole relation by $4$ (divisor of all three ingredients), it is equivalent to $5 \mid 3x - 2$ , i.e.

3x \equiv 2 \pmod 5 .

Now $\gcd(3, 5) = 1$ and $3^{-1} \equiv 2 \pmod 5$ ( $3 \times 2 = 6 \equiv 1$ ), so $x \equiv 4 \pmod 5$ : the solutions are $x \equiv 4, 9, 14, 19 \pmod{20}$ — four classes mod $20$ , matching the gcd. (Had the right side not been divisible by $4$ , say $12x \equiv 6 \pmod{20}$ , there would be no solution at all: the left side is always $\equiv 0 \pmod 4$ .) General shape: $ax \equiv b \pmod n$ is solvable iff $\gcd(a, n) \mid b$ , and then has exactly $\gcd(a, n)$ solution classes — divide everything by the gcd and invert.

Theorem 6.23 (Fermat’s little theorem)

Let $p$ be prime. For every $a \in \Z$ :

a^p \equiv a \pmod p,

and if $p \nmid a$ , then $a^{p-1} \equiv 1 \pmod p$ .

Proof. First, for $1 \leq k \leq p - 1$ , the binomial coefficient $\binom pk = \frac{p!}{k!(p-k)!}$ is divisible by $p$ : indeed $k!\,(p-k)!\, \binom pk = p!$ and $p$ divides $p!$ but is coprime to $k!(p-k)!$ (all factors are $< p$ ), so Gauss’s lemma gives $p \mid \binom pk$ .

Now prove $a^p \equiv a$ for $a \in \N$ by induction. True for $a = 0$ . If $a^p \equiv a$ , then by the binomial theorem

(a+1)^p = \sum_{k=0}^{p} \binom pk a^k \equiv a^p + 1 \equiv a + 1 \pmod p,

all middle terms vanishing mod $p$ . For $a < 0$ , apply the result to $-a$ and separate $p = 2$ (where $x \equiv -x$ ) from odd $p$ (where $(-a)^p = -a^p$ ). Finally, if $p \nmid a$ , multiply $a^p \equiv a$ by an inverse of $a$ mod $p$ (Proposition 6.20). ∎

Example 6.24 (Fermat’s converse fails: $341$ )

Fermat’s little theorem gives a cheap compositeness test: if $a^{n-1} \not\equiv 1 \pmod n$ for some $a$ coprime to $n$ , then $n$ is not prime. Could the test also certify primality? No: take $n = 341 = 11 \times 31$ , composite, and $a = 2$ . Since $2^{10} = 1024 = 3 \times 341 + 1$ ,

2^{10} \equiv 1 \pmod{341} \qquad\Longrightarrow\qquad 2^{340} = \bigl(2^{10}\bigr)^{34} \equiv 1 \pmod{341} :

the composite $341$ passes Fermat’s test for the base $2$ (it is the smallest such pseudoprime). The base $3$ unmasks it ( $3^{340} \not\equiv 1$ ), and practical primality testing therefore runs the test on several bases, plus refinements — the industrial versions of this idea are what certify the large primes of Remark 6.27. Moral: an implication and its converse live separate lives (Remark 1.10), even for theorems.

Example 6.25 (Practical congruence computations)

What is the remainder of $7^{2026}$ mod $11$ ? By Fermat, $7^{10} \equiv 1 \pmod{11}$ . Since $2026 = 10 \times 202 + 6$ :

7^{2026} \equiv 7^6 = (7^2)^3 = 49^3 \equiv 5^3 = 125 \equiv 4 \pmod{11}.

The remainder is $4$ . The strategy: reduce the exponent modulo the order provided by Fermat, then reduce intermediate powers at every step.

Remark 6.26 (Common pitfalls in arithmetic)

Dividing a congruence. From $ac \equiv bc \pmod n$ one may not conclude $a \equiv b$ unless $\gcd(c, n) = 1$ : $6 \equiv 2 \pmod 4$ but $3 \not\equiv 1 \pmod 4$ . The correct general rule divides the modulus too: $ac \equiv bc \pmod n \iff a \equiv b \pmod{n/\gcd(c,n)}$ .
Misusing Euclid’s lemma. $a \mid bc$ implies $a \mid b$ or $a \mid c$ only for $a$ prime (or coprime to one factor): $6 \mid 4 \times 9$ yet $6$ divides neither factor.
Coprime is a relation, not a property. “ $8$ and $9$ are coprime” is true though neither is prime; “pairwise coprime” is stronger than “globally coprime” ( $\gcd(6, 10, 15) = 1$ but no pair is coprime).
Exponents do not live mod $n$ . In $a^k \bmod n$ , the exponent may only be reduced modulo the order of $a$ (for instance $p - 1$ when Fermat applies), never modulo $n$ : $2^{10} \bmod 11$ is $1$ , not $2^{10 \bmod 11} = 2^{10}$ — the reduction that works is the one Example 6.25 performs.

Remark 6.27 (Where this chapter is used)

This chapter is a template as much as a toolbox. The whole chain — Euclidean division, gcd, Bézout, Gauss, unique factorization — is replayed verbatim for polynomials in Chapter 8, where “degree” plays the role of absolute value; comparing the two chapters side by side is the best way to understand both. The congruence calculus becomes the ring $\Z/n\Z$ in Chapter 7, whose invertible elements (Proposition 6.20) form the first nontrivial example of a group of units. Valuations return in the weekend problem below (Legendre’s formula) and power the irrationality proofs of Chapter 10. Beyond this volume, Bézout inversion mod $n$ is the engine of public-key cryptography, and Fermat’s little theorem is the grandfather of the primality tests that certify the large primes used there.

Remark 6.28 (Interlude: $\Z$ as a template)

Step back from the individual theorems and observe the architecture of the chapter: one tool (Euclidean division) produced a classification (subgroups $n\Z$ ), which produced an existence theorem (gcd, Bézout), which produced a divisibility calculus (Gauss), which produced unique factorization — each floor resting only on the one below. The same building will be erected twice more in this volume with different ground floors: in Chapter 8, where division by degree replaces division by size and everything above repeats verbatim; and, in miniature, inside every $\Z/n\Z$ of Chapter 7, where invertibility questions (this chapter’s Proposition 6.20) become structural statements about rings and fields. Recognizing an argument as “the $\Z$ -argument, transplanted” is the fastest way to learn those chapters — and the first taste of algebra’s core habit, proving theorems about axioms rather than about objects.

Rows 0 to 7 of Pascal’s triangle with the odd entries filled: row n contains 2s_2(n) of them, where s_2(n) is the number of ones in the binary writing of n (rows 1, 2, 4: two odd entries; row 7 = (111)_2: all eight). The self-similar pattern — each “triangle of odds” spawns two copies of itself — is Kummer’s theorem in picture form, proved in the weekend problem below. — Rows $0$ to $7$ of Pascal’s triangle with the *odd* entries filled: row $n$ contains $2^{s_2(n)}$ of them, where $s_2(n)$ is the number of ones in the binary writing of $n$ (rows $1, 2, 4$ : two odd entries; row $7 = (111)_2$ : all eight). The self-similar pattern — each “triangle of odds” spawns two copies of itself — is Kummer’s theorem in picture form, proved in the weekend problem below.

6.5 Exercises

Exercise 6.1 ★

Compute $\gcd(1\,001, 777)$ by the Euclidean algorithm, and a Bézout pair for it.

Solution

Solution of Exercise 6.1.

$1001 = 1 \times 777 + 224$ ; $777 = 3 \times 224 + 105$ ; $224 = 2 \times 105 + 14$ ; $105 = 7 \times 14 + 7$ ; $14 = 2 \times 7 + 0$ . So $\gcd(1001, 777) = 7$ . Backwards:

7 = 105 - 7 \times 14 = 105 - 7(224 - 2\times 105) = 15 \times 105 - 7 \times 224

= 15(777 - 3\times 224) - 7\times 224 = 15 \times 777 - 52 \times 224 = 15 \times 777 - 52(1001 - 777) = 67 \times 777 - 52 \times 1001 .

Check: $67 \times 777 = 52\,059$ and $52 \times 1001 = 52\,052$ ; difference $7$ . Bézout pair: $(u, v) = (-52, 67)$ for $1001u + 777v = 7$ .

Exercise 6.2 ★

Prove the divisibility rules in base $10$ : an integer is congruent mod $9$ to the sum of its digits, and mod $11$ to the alternating sum of its digits. What is $123\,456\,789$ mod $9$ and mod $11$ ?

Solution

Solution of Exercise 6.2.

Since $10 \equiv 1 \pmod 9$ : $10^k \equiv 1$ , so $\sum_k d_k 10^k \equiv \sum_k d_k \pmod 9$ . Since $10 \equiv -1 \pmod{11}$ : $10^k \equiv (-1)^k$ , so the integer is congruent to the alternating sum $\sum_k (-1)^k d_k$ mod $11$ (starting from the units digit with sign $+$ ).

$123\,456\,789$ : digit sum $45 \equiv 0 \pmod 9$ . Alternating sum from the units: $9 - 8 + 7 - 6 + 5 - 4 + 3 - 2 + 1 = 5$ , so the number is $\equiv 5 \pmod{11}$ .

Exercise 6.3 ★

Solve in $\Z$ : $91x \equiv 1 \pmod{237}$ (extended Euclid).

Solution

Solution of Exercise 6.3.

Euclid: $237 = 2 \times 91 + 55$ ; $91 = 1 \times 55 + 36$ ; $55 = 1 \times 36 + 19$ ; $36 = 1 \times 19 + 17$ ; $19 = 1 \times 17 + 2$ ; $17 = 8 \times 2 + 1$ . Backwards:

1 = 17 - 8\times 2 = 17 - 8(19 - 17) = 9\times 17 - 8\times 19 = 9(36 - 19) - 8\times 19 = 9\times 36 - 17\times 19

= 9\times 36 - 17(55 - 36) = 26\times 36 - 17\times 55 = 26(91 - 55) - 17\times 55 = 26\times 91 - 43\times 55

= 26\times 91 - 43(237 - 2\times 91) = 112 \times 91 - 43 \times 237.

So $91 \times 112 \equiv 1 \pmod{237}$ : the solutions are $x \equiv 112 \pmod{237}$ . (Check: $91 \times 112 = 10\,192 = 43 \times 237 + 1$ .)

Exercise 6.4 ★

Find all pairs $(x, y) \in \Z^2$ with $17x + 39y = 1$ ; then all pairs with $17 x + 39 y = 5$ .

Solution

Solution of Exercise 6.4.

$\gcd(17, 39) = 1$ : Euclid gives $39 = 2\times 17 + 5$ , $17 = 3\times 5 + 2$ , $5 = 2\times 2 + 1$ , and backwards

1 = 5 - 2\times 2 = 5 - 2(17 - 3\times 5) = 7\times 5 - 2\times 17 = 7(39 - 2\times 17) - 2\times 17 = 7\times 39 - 16\times 17 .

Particular solution $(x_0, y_0) = (-16, 7)$ . General solution of the homogeneous equation $17x + 39y = 0$ : $x = 39k$ , $y = -17k$ (since $17 \mid 39y$ and $\gcd(17,39) = 1$ force $17 \mid y$ — Gauss’s lemma). Hence

(x, y) = (-16 + 39k,\; 7 - 17k), \qquad k \in \Z .

For the right-hand side $5$ , multiply the particular solution by $5$ : $(x, y) = (-80 + 39k,\; 35 - 17k)$ , $k \in \Z$ .

Exercise 6.5 ★★

Prove that for $a, b \in \N^*$ : $\gcd(a,b) \times \operatorname{lcm}(a,b) = ab$ . (Use the valuation formulas of Proposition 6.16 and $\min(\alpha,\beta) + \max(\alpha,\beta) = \alpha + \beta$ .)

Solution

Solution of Exercise 6.5.

For every prime $p$ , with $\alpha = v_p(a)$ and $\beta = v_p(b)$ :

v_p\bigl(\gcd(a,b)\bigr) + v_p\bigl(\operatorname{lcm}(a,b)\bigr) = \min(\alpha, \beta) + \max(\alpha, \beta) = \alpha + \beta = v_p(ab) .

Two positive integers with the same valuation at every prime are equal (Proposition 6.16), so $\gcd(a,b)\operatorname{lcm}(a,b) = ab$ .

Exercise 6.6 ★★

Let $a = 2^{10} \times 3^4 \times 5^2$ and $b = 2^6 \times 3^7 \times 7$ . Compute $\gcd(a, b)$ , $\operatorname{lcm}(a,b)$ , and the number of positive divisors of $a$ . (Prove the divisor-count formula $\prod_i (\alpha_i + 1)$ .)

Solution

Solution of Exercise 6.6.

Valuations: $\gcd(a, b) = 2^{\min(10,6)} 3^{\min(4,7)} 5^{\min(2,0)} 7^{\min(0,1)} = 2^6\, 3^4 = 5184$ ; $\operatorname{lcm}(a,b) = 2^{10}\, 3^7\, 5^2\, 7$ .

Divisor count: a positive divisor of $n = \prod p_i^{\alpha_i}$ is exactly a choice $\prod p_i^{\beta_i}$ with $0 \leq \beta_i \leq \alpha_i$ (Proposition 6.16); the choices are independent, so there are $\prod_i (\alpha_i + 1)$ divisors. For $a$ : $(10+1)(4+1)(2+1) = 165$ .

Exercise 6.7 ★★

Prove that $\sqrt p$ is irrational for every prime $p$ , using valuations: compare $v_p$ of both sides of $p q^2 = r^2$ .

Solution

Solution of Exercise 6.7.

Suppose $\sqrt p = \frac rq$ with $r, q \in \N^*$ , i.e. $p q^2 = r^2$ . Apply $v_p$ : $v_p(pq^2) = 1 + 2v_p(q)$ is odd, while $v_p(r^2) = 2 v_p(r)$ is even. An integer cannot have an odd and an even $p$ -valuation at once: contradiction. So $\sqrt p \notin \Q$ .

Exercise 6.8 ★★

(Chinese remainder problem) Find all integers $x$ with

x \equiv 2 \pmod 7, \qquad x \equiv 5 \pmod{11}.

Prove along the way that for coprime $m, n$ , the pair of congruences $x \equiv a \ (m)$ , $x \equiv b\ (n)$ always has a solution, unique mod $mn$ .

Solution

Solution of Exercise 6.8.

General fact. With $\gcd(m,n) = 1$ , Bézout gives $mu + nv = 1$ . Set $x_0 = b\,mu + a\,nv$ . Then $x_0 \equiv a\,nv \equiv a(1 - mu) \equiv a \pmod m$ and similarly $x_0 \equiv b \pmod n$ : existence. If $x$ and $x'$ are two solutions, $m$ and $n$ divide $x - x'$ , so $mn \mid x - x'$ (Theorem 6.8 (2)): uniqueness mod $mn$ .

Numerically: $m = 7$ , $n = 11$ : $7 \times (-3) + 11 \times 2 = 1$ . So $x_0 = 5 \times 7 \times (-3) + 2 \times 11 \times 2 = -105 + 44 = -61 \equiv 16 \pmod{77}$ . Check: $16 = 2\times 7 + 2 \equiv 2 \pmod 7$ ; $16 = 11 + 5 \equiv 5 \pmod{11}$ . Solutions: $x \equiv 16 \pmod{77}$ .

Exercise 6.9 ★★

Compute $3^{1000}$ mod $7$ , and the last two decimal digits of $7^{100}$ (mod $100 = 4 \times 25$ : use Exercise 6.8).

Solution

Solution of Exercise 6.9.

Mod $7$ : Fermat gives $3^6 \equiv 1$ , and $1000 = 6 \times 166 + 4$ , so $3^{1000} \equiv 3^4 = 81 \equiv 4 \pmod 7$ .

Last two digits of $7^{100}$ : work mod $4$ and mod $25$ . Mod $4$ : $7 \equiv -1$ , so $7^{100} \equiv 1$ . Mod $25$ : $7^2 = 49 \equiv -1$ , so $7^4 \equiv 1$ and $7^{100} = (7^4)^{25} \equiv 1$ . By the Chinese remainder theorem (Exercise 6.8), $7^{100} \equiv 1 \pmod{100}$ : the last two digits are $01$ .

Exercise 6.10 ★★★

For $m, n \in \N^*$ , prove that $\gcd(2^m - 1,\, 2^n - 1) = 2^{\gcd(m,n)} - 1$ . Hint: show first that the remainder of $2^m - 1$ mod $2^n - 1$ is $2^r - 1$ where $r$ is the remainder of $m$ mod $n$ ; then follow the Euclidean algorithm.

Solution

Solution of Exercise 6.10.

Write $m = nq + r$ , $0 \leq r < n$ . Then

2^m - 1 = 2^r\bigl(2^{nq} - 1\bigr) + 2^r - 1,

and $2^n - 1$ divides $2^{nq} - 1 = (2^n - 1)(2^{n(q-1)} + \dots + 1)$ . So mod $2^n - 1$ , $\;2^m - 1 \equiv 2^r - 1$ , and since $0 \leq 2^r - 1 < 2^n - 1$ , this is the Euclidean remainder.

Therefore the Euclidean algorithm on the pair $(2^m - 1, 2^n - 1)$ mirrors, exponent by exponent, the algorithm on $(m, n)$ : each division step replaces $(m, n)$ by $(n, r)$ upstairs and $(2^m - 1, 2^n - 1)$ by $(2^n - 1, 2^r - 1)$ downstairs. The algorithm upstairs terminates at $\gcd(m,n)$ , so downstairs it terminates at $2^{\gcd(m,n)} - 1$ .

Exercise 6.11 ★★★

(Wilson’s theorem) Let $p$ be a prime. Prove that

(p-1)! \equiv -1 \pmod p ,

by pairing each factor of $(p-1)!$ with its inverse mod $p$ and identifying the self-paired factors (solve $x^2 \equiv 1 \pmod p$ first). Check the converse: if $n \geq 2$ is not prime, then $(n-1)! \not\equiv -1 \pmod n$ .

Solution

Solution of Exercise 6.11.

First solve $x^2 \equiv 1 \pmod p$ : $p \mid (x-1)(x+1)$ , so by Euclid’s lemma $x \equiv 1$ or $x \equiv -1 \pmod p$ .

In the product $(p-1)! = 1 \times 2 \times \dots \times (p-1)$ , every factor $a$ is invertible mod $p$ , and its inverse $a^{-1}$ is again one of the factors (Proposition 6.20). Pair each $a$ with $a^{-1}$ : the pairs multiply to $1$ , except that self-paired factors ( $a = a^{-1}$ , i.e. $a^2 \equiv 1$ ) stand alone — and these are exactly $1$ and $p - 1$ . Hence

(p-1)! \equiv 1 \times (p - 1) \equiv -1 \pmod p .

(For $p = 2$ : $1! = 1 \equiv -1 \pmod 2$ ; the pairing argument degenerates but the result holds.)

Converse. Let $n \geq 2$ be composite, $n = ab$ with $1 < a \leq b < n$ . If $a < b$ , both appear as distinct factors of $(n-1)!$ , so $n \mid (n-1)!$ and $(n-1)! \equiv 0 \not\equiv -1$ . If $a = b$ (i.e. $n = a^2$ ): for $a \geq 3$ , both $a$ and $2a$ are $< n$ , so $n = a^2 \mid a \times 2a \mid (n-1)!$ , same conclusion; for $n = 4$ , $(n-1)! = 6 \equiv 2 \not\equiv -1 \pmod 4$ .

Exercise 6.12 ★★★

(Fermat numbers) For $n \in \N$ , let $F_n = 2^{2^n} + 1$ .

Prove that $F_0 F_1 \cdots F_{n-1} = F_n - 2$ for $n \geq 1$ (induction).
Deduce that the Fermat numbers are pairwise coprime.
Deduce a second proof, independent of Theorem 6.14, that there are infinitely many primes.

Solution

Solution of Exercise 6.12.

Induction. For $n = 1$ : $F_0 = 3 = F_1 - 2 = 5 - 2$ . Assuming $F_0\cdots F_{n-1} = F_n - 2$ :

$F_0 \cdots F_n = (F_n - 2)F_n = \bigl(2^{2^n} - 1\bigr)\bigl(2^{2^n} + 1\bigr) = 2^{2^{n+1}} - 1 = F_{n+1} - 2 .$
Let $m < n$ and $d = \gcd(F_m, F_n)$ . By (1), $F_m$ divides $F_n - 2$ , so $d$ divides both $F_n$ and $F_n - 2$ , hence divides $2$ . But every Fermat number is odd, so $d = 1$ .
Each $F_n \geq 3$ has a prime divisor $p_n$ (Theorem 6.14’s first step). If $m \neq n$ , then $p_m \neq p_n$ , since a common prime would divide $\gcd(F_m, F_n) = 1$ . The map $n \mapsto p_n$ is therefore injective from $\N$ into the primes: there are infinitely many primes.

6.6 Problem: Legendre’s formula and Kummer’s carries

Problem 6.1

How many zeros end the decimal writing of $1000!$ — and, deeper, what is the exact power of a prime $p$ dividing $n!$ , or dividing a binomial coefficient? The complete answers are two gems of elementary arithmetic: Legendre’s formula $v_p(n!) = \sum_{k\geq1} \lfloor n/p^k \rfloor$ , with its digital avatar $v_p(n!) = \frac{n - s_p(n)}{p-1}$ , and Kummer’s theorem: $v_p\binom{m+n}m$ counts the carries when adding $m$ and $n$ in base $p$ . This problem proves both, checks them against each other numerically, and harvests the classical consequences — trailing zeros, the parity of Pascal’s triangle, and a first bound in the direction of the prime number theorem. Throughout, $p$ is a prime, $\floor{x}$ is the integer part, and $s_p(n)$ denotes the sum of the digits of $n$ written in base $p$ .

Part I — Floors, valuations, and Legendre’s formula.

Warm-up: compute $10!$ and read off its number of trailing zeros; compute $v_2(10!)$ and $v_5(10!)$ directly from the factorization of each factor $1, 2, \dots, 10$ .
Prove that for $x \in \R$ and $n \in \N^*$ , $\bigl\lfloor \lfloor x \rfloor / n \bigr\rfloor = \lfloor x/n \rfloor$ .
Prove that $v_p(a + b) \geq \min\bigl(v_p(a), v_p(b)\bigr)$ for all $a, b \in \N^*$ , with equality whenever $v_p(a) \neq v_p(b)$ .
Show that the number of multiples of $m$ in $\intint1n$ is $\lfloor n/m \rfloor$ .
Prove Legendre’s formula: for every $n \in \N^*$ ,

$v_p(n!) = \sum_{k=1}^{\infty} \Bigl\lfloor \frac{n}{p^k} \Bigr\rfloor$

(a finite sum: the terms vanish once $p^k > n$ ). Count, for each $k$ , the factors of $\intint1n$ divisible by $p^k$ : each contributes exactly one unit per level it reaches.

Part II — The digital form and trailing zeros.

Compute $v_5(1000!)$ and $v_2(1000!)$ , and conclude: how many zeros end $1000!$ ?
Prove the digital form of Legendre’s formula: writing $n = \sum_i a_i p^i$ in base $p$ ,

$v_p(n!) = \frac{n - s_p(n)}{p - 1} .$
Two consequences for $p = 2$ : show that $2^n$ never divides $n!$ , and that $2^{n-1}$ divides $n!$ exactly when $n$ is a power of $2$ .
Bound the defect: show $\frac n{p-1} - \log_p(n) - 1 \leq v_p(n!) < \frac n{p-1}$ , so that $\frac{v_p(n!)}{n} \to \frac1{p-1}$ : in the long run, a proportion $\frac1{p-1}$ of one factor $p$ accrues per unit.
Let $Z(n) = v_5(n!)$ be the number of trailing zeros of $n!$ . Show $Z(n) - Z(n-1) = v_5(n)$ , deduce that $Z$ skips the value $5$ entirely (compute $Z(24)$ and $Z(25)$ ), and prove that no factorial ends in exactly five zeros.

Part III — Kummer’s theorem.

Prove that $\lfloor x + y \rfloor - \lfloor x \rfloor - \lfloor y \rfloor \in \{0, 1\}$ for all $x, y \in \R$ , and deduce from Legendre’s formula that

$v_p\binom{m+n}m = \sum_{k\geq1}\Bigl( \Bigl\lfloor\frac{m+n}{p^k}\Bigr\rfloor - \Bigl\lfloor\frac{m}{p^k}\Bigr\rfloor - \Bigl\lfloor\frac{n}{p^k}\Bigr\rfloor\Bigr),$

a sum of terms each equal to $0$ or $1$ .
Prove Kummer’s theorem: the $k$ -th term of that sum equals $1$ exactly when the addition of $m$ and $n$ in base $p$ produces a carry into position $k$ ; hence $v_p\binom{m+n}m$ is the total number of carries. (Write $m = p^km_1 + m_0$ and $n = p^kn_1 + n_0$ with $0 \leq m_0, n_0 < p^k$ and inspect $\lfloor (m_0 + n_0)/p^k \rfloor$ .)
Deduce that for $0 < j < p^k$ :

$v_p\binom{p^k}{j} = k - v_p(j) ,$

by counting the carries in the addition $j + (p^k - j)$ . (In particular $p \mid \binom p j$ for $0 < j < p$ : the key step of Theorem 6.23, recovered.)
Prove that $v_2\binom{2n}n = s_2(n)$ . Deduce that the central binomial coefficient is always even, and that $\binom{2n}n \equiv 2 \pmod 4$ exactly when $n$ is a power of $2$ .
Show, using Vandermonde’s identity (Exercise 2.7) and question 13, that $\binom{2p}p \equiv 2 \pmod p$ for every prime $p$ .
Compute $v_3\binom{1000}{500}$ twice: once by Kummer (write $500$ in base $3$ and count the carries in $500 + 500$ ), once by Legendre’s digital form (compute $s_3(500)$ and $s_3(1000)$ ); check that both give the same value.

Part IV — The parity of Pascal’s triangle, and a prime-density bound.

Prove the digit criterion: $\binom nk$ is odd if and only if every binary digit of $k$ is at most the corresponding digit of $n$ . State and prove the analogous criterion for $p \nmid \binom nk$ in base $p$ .
Deduce that row $n$ of Pascal’s triangle contains exactly $2^{s_2(n)}$ odd entries; verify on rows $4$ and $5$ .
Deduce that all interior entries $\binom nk$ ( $0 < k < n$ ) are even if and only if $n$ is a power of $2$ .
Prove that every prime power dividing $\binom{m+n}m$ is at most $m + n$ : if $p^a \mid \binom{m+n}m$ then $p^a \leq m + n$ . (How many nonzero terms can the sum of question 11 have?)
Deduce that $\binom{2n}n$ divides $\operatorname{lcm}(1, 2, \dots, 2n)$ , and combine with the lower bound $\binom{2n}n \geq \frac{4^n}{2n+1}$ (which you will prove: the central entry is the largest of the $2n + 1$ entries of row $2n$ ) to obtain

$\operatorname{lcm}(1, \dots, 2n) \geq \frac{4^n}{2n+1} :$

the common multiples of the first integers grow exponentially — a first quantitative glimpse of the abundance of primes.

Part V — Synthesis.

Find the smallest $n$ such that $n!$ ends in at least $2026$ zeros. (Estimate $Z(n) \approx n/4$ , then adjust using the exact formula.)
One last cross-check: show that $7$ does not divide $\binom{100}{50}$ , first by writing $50$ in base $7$ and checking that the addition $50 + 50$ is carry-free, then by computing $v_7(100!)$ and $v_7(50!)$ with Legendre’s formula.
Where exactly did the problem use: (i) unique factorization; (ii) the Euclidean-division decomposition $n = p^k n_1 + n_0$ ; (iii) a counting argument from Chapter 2? One sentence each.
Synthesis, in a short paragraph: Legendre’s formula turns a divisibility question into digit arithmetic, and Kummer’s theorem reads the answer off the carries of one addition — comment on this translation, on the checks of question 16, and on what the bound of question 21 suggests about primes (the full statement, the prime number theorem, is far beyond this volume; the polynomial analogue of this chapter’s toolkit is Chapter 8).

Solution

Solution of Problem 6.1.

1. $10! = 3\,628\,800$ : two trailing zeros. Valuations factor by factor: powers of $2$ come from $2, 4 = 2^2, 6, 8 = 2^3, 10$ , totaling $v_2(10!) = 1 + 2 + 1 + 3 + 1 = 8$ ; powers of $5$ from $5$ and $10$ : $v_5(10!) = 2$ . Trailing zeros $= \min(v_2, v_5) = 2$ , consistent.

2. Write the Euclidean division $\lfloor x\rfloor = nq + r$ , $0 \leq r \leq n - 1$ . Then $x = nq + r + \{x\}$ with $0 \leq r + \{x\} < n$ , so $\lfloor x/n \rfloor = q = \bigl\lfloor \lfloor x \rfloor / n \bigr\rfloor$ .

3. Let $\alpha = v_p(a) \leq \beta = v_p(b)$ (swap if needed) and write $a = p^\alpha a'$ , $b = p^\beta b'$ with $p \nmid a', b'$ . Then $a + b = p^\alpha\bigl(a' + p^{\beta - \alpha}b'\bigr)$ , so $v_p(a + b) \geq \alpha = \min$ . If $\alpha < \beta$ , the parenthesis is $a' + p^{\beta-\alpha}b' \equiv a' \not\equiv 0 \pmod p$ : the valuation is exactly $\alpha$ .

4. The multiples of $m$ in $\intint1n$ are $m, 2m, \dots, qm$ where $q$ is the largest integer with $qm \leq n$ , i.e. $q = \lfloor n/m \rfloor$ .

5. By unique factorization, $v_p(n!) = \sum_{j=1}^{n} v_p(j)$ . Count differently: each $j$ contributes $v_p(j) = \#\{k \geq 1 : p^k \mid j\}$ , so

v_p(n!) = \sum_{j=1}^n \#\{k : p^k \mid j\} = \sum_{k\geq1} \#\{j \leq n : p^k \mid j\} = \sum_{k\geq1} \Bigl\lfloor \frac n{p^k} \Bigr\rfloor

by question 4 — Legendre’s formula. The sum is finite: terms with $p^k > n$ vanish.

6. $v_5(1000!) = 200 + 40 + 8 + 1 = 249$ (divisions by $5, 25, 125, 625$ ); $v_2(1000!) = 500 + 250 + 125 + 62 + 31 + 15 + 7 + 3 + 1 = 994$ . Trailing zeros of $1000!$ : each zero consumes one $2$ and one $5$ , so there are $\min(994, 249) = 249$ of them.

7. With $n = \sum_i a_ip^i$ , question 2 gives $\lfloor n/p^k \rfloor = \sum_{i \geq k} a_ip^{i-k}$ (truncate the base- $p$ expansion). Summing over $k \geq 1$ and exchanging the two finite sums:

v_p(n!) = \sum_{i\geq1} a_i \sum_{k=1}^{i} p^{i-k} = \sum_{i\geq0} a_i\,\frac{p^i - 1}{p - 1} = \frac{n - s_p(n)}{p - 1} .

8. For $p = 2$ : $v_2(n!) = n - s_2(n)$ . Since $n \geq 1$ has $s_2(n) \geq 1$ , always $v_2(n!) \leq n - 1 < n$ : $2^n \nmid n!$ . And $v_2(n!) = n - 1$ iff $s_2(n) = 1$ iff $n$ is a power of $2$ .

9. $n$ has $\lfloor \log_p n \rfloor + 1$ base- $p$ digits, each at most $p - 1$ , so $1 \leq s_p(n) \leq (p-1)\bigl(\log_p(n) + 1\bigr)$ . Substituting in question 7:

\frac n{p-1} - \log_p(n) - 1 \;\leq\; v_p(n!) \;<\; \frac n{p-1},

and dividing by $n$ : $\frac{v_p(n!)}n \to \frac1{p-1}$ .

10. $Z(n) - Z(n-1) = v_5(n!/(n-1)!) = v_5(n)$ : the count of trailing zeros jumps by $v_5(n)$ at each multiple of $5$ and is constant in between. $Z(24) = \lfloor24/5\rfloor = 4$ and $Z(25) = 5 + 1 = 6$ : at $n = 25$ the count jumps from $4$ straight to $6$ ( $v_5(25) = 2$ ), and since $Z$ is nondecreasing with $Z \leq 4$ before and $Z \geq 6$ after, the value $5$ is never attained: no factorial ends in exactly five zeros.

11. Write $x = \lfloor x\rfloor + \{x\}$ : $\lfloor x + y\rfloor = \lfloor x\rfloor + \lfloor y\rfloor + \lfloor \{x\} + \{y\}\rfloor$ , and $0 \leq \{x\} + \{y\} < 2$ makes the last floor $0$ or $1$ . Then, by Legendre applied three times,

v_p\binom{m+n}m = v_p\bigl((m{+}n)!\bigr) - v_p(m!) - v_p(n!) = \sum_{k\geq1}\Bigl( \Bigl\lfloor\frac{m+n}{p^k}\Bigr\rfloor - \Bigl\lfloor\frac{m}{p^k}\Bigr\rfloor - \Bigl\lfloor\frac{n}{p^k}\Bigr\rfloor\Bigr),

a finite sum of $0$ s and $1$ s (apply the first claim to $x = m/p^k$ , $y = n/p^k$ ).

12. Fix $k \geq 1$ and write $m = p^km_1 + m_0$ , $n = p^kn_1 + n_0$ with $0 \leq m_0, n_0 < p^k$ (Euclidean division: $m_0$ is the number formed by the $k$ low digits of $m$ ). Then

\Bigl\lfloor\frac{m+n}{p^k}\Bigr\rfloor - \Bigl\lfloor\frac m{p^k}\Bigr\rfloor - \Bigl\lfloor\frac n{p^k}\Bigr\rfloor = \Bigl\lfloor\frac{m_0 + n_0}{p^k}\Bigr\rfloor ,

which is $1$ if $m_0 + n_0 \geq p^k$ and $0$ otherwise. But $m_0 + n_0 \geq p^k$ says precisely that adding the $k$ low digits of $m$ and $n$ overflows into position $k$ — a carry into position $k$ in the schoolbook addition algorithm. Summing over $k$ : $v_p\binom{m+n}m$ is the number of carries in the base- $p$ addition $m + n$ . (Kummer, 1852.)

13. Apply Kummer to $m = j$ , $n = p^k - j$ , sum $p^k = (1\underbrace{0\cdots0}_{k})_p$ . Let $a = v_p(j)$ , so the base- $p$ digits of $j$ at positions $0, \dots, a-1$ are $0$ and the digit at position $a$ is nonzero. The digits of $p^k - j$ below position $a$ are $0$ too ( $p^k - j = p^a(p^{k-a} - j/p^a)$ ). At position $a$ , the two nonzero digits must sum to $p$ (result digit $0$ ): one carry; at each position $a+1, \dots, k-1$ , digits plus the incoming carry sum to $p$ (result digit $0$ again): the carry propagates. Total: $k - a$ carries, so $v_p\binom{p^k}j = k - v_p(j)$ . For $k = 1$ : $v_p\binom pj = 1$ for $0 < j < p$ , the divisibility used in Theorem 6.23.

14. By the digital form (question 7), using $s_2(2n) = s_2(n)$ (appending a zero digit):

v_2\binom{2n}n = \bigl(2n - s_2(2n)\bigr) - 2\bigl(n - s_2(n)\bigr) = 2s_2(n) - s_2(2n) = s_2(n) \geq 1 :

$\binom{2n}n$ is always even, and $v_2 = 1$ (i.e. $\binom{2n}n \equiv 2 \pmod 4$ ) exactly when $s_2(n) = 1$ , i.e. when $n$ is a power of $2$ .

15. Vandermonde with $m = n = k = p$ : $\binom{2p}p = \sum_{j=0}^p \binom pj\binom p{p-j} = \sum_{j=0}^p \binom pj^2$ . For $0 < j < p$ , $p \mid \binom pj$ (question 13), so $\binom pj^2 \equiv 0 \pmod p$ ; the end terms give $1 + 1$ : $\binom{2p}p \equiv 2 \pmod p$ .

16. Base $3$ : $500 = 486 + 9 + 3 + 2$ , digits (low to high) $(2, 1, 1, 0, 0, 2)$ , so $s_3(500) = 6$ ; and $1000 = 729 + 243 + 27 + 1$ , digits $(1, 0, 0, 1, 0, 1, 1)$ , so $s_3(1000) = 4$ . Kummer: add $500 + 500$ in base $3$ : position $0$ : $2 + 2 = 4$ , digit $1$ carry $1$ ; position $1$ : $1 + 1 + 1 = 3$ , digit $0$ carry $1$ ; position $2$ : $1 + 1 + 1 = 3$ , digit $0$ carry $1$ ; position $3$ : $0 + 0 + 1 = 1$ , no carry; position $4$ : $0$ ; position $5$ : $2 + 2 = 4$ , digit $1$ carry $1$ ; position $6$ : carry lands: digit $1$ . Four carries: $v_3\binom{1000}{500} = 4$ . Legendre: $v_3(1000!) = \frac{1000 - 4}2 = 498$ and $v_3(500!) = \frac{500 - 6}2 = 247$ , so $v_3\binom{1000}{500} = 498 - 2\times247 = 4$ . The two computations agree — and the addition digits $(1, 0, 0, 1, 0, 1, 1)$ reproduce $1000$ , as they must.

17. By Kummer ( $p = 2$ , $m = k$ , $n' = n - k$ ): $\binom nk$ is odd iff the addition $k + (n - k)$ in base $2$ has no carry, iff at every position the digits satisfy $k_i + (n - k)_i = n_i$ ; in that case $k_i \leq n_i$ for all $i$ . Conversely, if $k_i \leq n_i$ for all $i$ , then the number with digits $n_i - k_i$ is $n - k$ and the addition is carry-free. Same proof in base $p$ : $p \nmid \binom nk$ iff every base- $p$ digit of $k$ is at most the corresponding digit of $n$ .

18. Counting the $k \in \intint0n$ whose digits obey $k_i \leq n_i$ : each digit of $k$ is chosen independently among $n_i + 1$ values, giving $\prod_i (n_i + 1)$ choices; in base $2$ this is $2^{\#\{i : n_i = 1\}} = 2^{s_2(n)}$ . Row $4 = (100)_2$ : $2^1 = 2$ odd entries — indeed $1, 4, 6, 4, 1$ has odd entries only at the ends. Row $5 = (101)_2$ : $2^2 = 4$ — indeed $1, 5, 10, 10, 5, 1$ .

19. All interior entries even $\iff$ the row has exactly $2$ odd entries (the two ends always are odd) $\iff 2^{s_2(n)} = 2 \iff s_2(n) = 1 \iff n$ is a power of $2$ .

20. In question 11’s sum, the $k$ -th term vanishes as soon as $p^k > m + n$ (all three floors are then equal, indeed the first is $0$ when $p^k > m+n$ ; more simply each term is $0$ ). Hence at most $\lfloor \log_p(m+n)\rfloor$ terms are nonzero, each worth $1$ : $a = v_p\binom{m+n}m \leq \log_p(m+n)$ , i.e. $p^a \leq m + n$ .

21. For every prime $p$ , $v_p\bigl(\operatorname{lcm}(1, \dots, 2n)\bigr) = \lfloor\log_p(2n)\rfloor$ (the largest power of $p$ not exceeding $2n$ appears among $1, \dots, 2n$ ). Question 20 with $m = n$ gives $v_p\binom{2n}n \leq \lfloor\log_p(2n)\rfloor$ for every $p$ : by Proposition 6.16, $\binom{2n}n \mid \operatorname{lcm}(1, \dots, 2n)$ . For the size: the ratio $\binom{2n}{k+1}/\binom{2n}k = \frac{2n-k}{k+1} \geq 1$ exactly for $k < n$ , so the central entry is the largest of the $2n + 1$ entries of row $2n$ , whence $4^n = \sum_k \binom{2n}k \leq (2n+1)\binom{2n}n$ . Combining:

\operatorname{lcm}(1, \dots, 2n) \geq \binom{2n}n \geq \frac{4^n}{2n + 1} .

If there were few primes below $2n$ , the lcm could not be this large: exponential growth of the lcm is a quantitative trace of the abundance of primes.

22. $Z(n) = \sum_k\lfloor n/5^k\rfloor \approx \frac n4$ , so aim near $n = 4 \times 2026 = 8104$ : $Z(8104) = 1620 + 324 + 64 + 12 + 2 = 2022$ . Step up by multiples of $5$ : $Z(8110) = 2024$ , $Z(8115) = 2025$ , and

Z(8120) = 1624 + 324 + 64 + 12 + 2 = 2026 .

Since $Z$ is constant between multiples of $5$ and $Z(8119) = Z(8115) = 2025$ , the smallest $n$ with at least $2026$ trailing zeros is $n = 8120$ .

23. Base $7$ : $50 = 49 + 1$ , digits (low to high) $(1, 0, 1)$ . Adding $50 + 50$ : position $0$ : $1 + 1 = 2 < 7$ , no carry; position $1$ : $0 + 0 = 0$ ; position $2$ : $1 + 1 = 2 < 7$ , no carry. Carry-free, so by Kummer $v_7\binom{100}{50} = 0$ : $7 \nmid \binom{100}{50}$ . Legendre agrees: $v_7(100!) = \lfloor 100/7 \rfloor + \lfloor 100/49 \rfloor = 14 + 2 = 16$ and $v_7(50!) = 7 + 1 = 8$ , so $v_7\binom{100}{50} = 16 - 2\times8 = 0$ .

24. (i) Unique factorization underlies the very definition of $v_p$ and its additivity, hence Legendre’s formula and every divisibility conclusion (Proposition 6.16). (ii) Euclidean division produced the truncation identity of question 2 and the split $m = p^km_1 + m_0$ that isolates the carry (question 12). (iii) Counting: the multiples-of- $m$ count (question 4), the digit-choice product (question 18), and the row-sum bound $4^n \leq (2n+1)\binom{2n}n$ (question 21) are all Chapter 2-style arguments.

25. Legendre converts “what power of $p$ divides $n!$ ” into base- $p$ digit arithmetic; Kummer compresses the answer for binomial coefficients into the carries of a single addition — divisibility, seemingly a global property of huge numbers, is read off locally, digit by digit. Question 16 is the paradigm: four carries, computed by hand, determine the exact power of $3$ in a number with hundreds of digits. And question 21 shows the same circle of ideas brushing against deep waters: an exponential lower bound for $\operatorname{lcm}(1, \dots, 2n)$ is a first, fully elementary step toward the prime number theorem, whose proof lies far beyond this volume. The entire toolkit — division, gcd, valuations — is replayed for polynomials in Chapter 8, where the analogue of a digit expansion is expansion in powers of $(X - a)$ .