---
title: "Integer Arithmetic"
book: "University Mathematics — Year 1"
subject: math
language: en
chapter: 6
exercises: 12
source: https://one-course.com/books/math/3/en/chapter/6-integer-arithmetic
---

# Chapter 6 — Integer Arithmetic

Arithmetic — the study of [divisibility](#def-b1-arith-divides) in $\Z$ — was begun in the High School volume. This chapter rebuilds it completely from the Euclidean division, with full proofs: [greatest common divisor](#thm-b1-arith-gcd) and the [Euclidean algorithm](#met-b1-arith-euclid), Bézout’s identity and Gauss’s lemma, [prime factorization](#thm-b1-arith-fta), and the calculus of [congruences](#def-b1-arith-congruence) up to Fermat’s little theorem. Beyond its own charm, this material is the model that [Chapter 8](https://one-course.com/books/math/3/en/chapter/8-polynomials#ch-b1-poly) 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](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-sets) $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\ZZ; existence of the gcd).**

1. Every subgroup of $(\Z, +)$ is of the form $n\Z = \{nk : k  \in \Z\}$ for a unique $n \in \N$ .
2. For $a, b \in \Z$ not both zero, the [set](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-sets) $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](#def-b1-arith-divides) $a$ and $b$ , and every common divisor of $a$ and $b$ [divides](#def-b1-arith-divides) $d$ .

**Proof.** (1) Let $H \subseteq \Z$ be a subgroup (nonempty, stable under subtraction; the formal definition is in [Chapter 7](https://one-course.com/books/math/3/en/chapter/7-algebraic-structures#ch-b1-structures), 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](#thm-b1-arith-division)); $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](#def-b1-arith-divides) both. And if $c$ [divides](#def-b1-arith-divides) $a$ and $b$, then $c$ [divides](#def-b1-arith-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](#cor-b1-arith-bezout) 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$.

1. (Gauss’s lemma) If $a \mid bc$ and $\gcd(a, b) = 1$ , then $a \mid c$ .
2. If $a \mid c$ , $b \mid c$ and $\gcd(a,b) = 1$ , then $ab \mid  c$ .
3. 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](#cor-b1-arith-bezout), $\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](#def-b1-arith-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](https://one-course.com/books/math/3/en/chapter/5-linear-differential-equations#ch-b1-diffeq), 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](#def-b1-arith-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](#thm-b1-arith-gauss)), *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](#def-b1-arith-prime) divisor $\leq
\sqrt n$. Hence to test whether $n$ is [prime](#def-b1-arith-prime) it suffices to try the [primes](#def-b1-arith-prime) 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](#def-b1-arith-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](#thm-b1-arith-fermat).

**Theorem 6.14 (Euclid).**

There are infinitely many [primes](#def-b1-arith-prime).

**Proof.** Every integer $n \geq 2$ has a [prime](#def-b1-arith-prime) divisor: its smallest divisor $\geq 2$ is [prime](#def-b1-arith-prime) (a proper factorization of it would produce a smaller divisor of $n$). Now suppose $p_1, \dots, p_k$ were all the [primes](#def-b1-arith-prime), and let $N = p_1 p_2 \cdots p_k + 1 \geq 2$. Some [prime](#def-b1-arith-prime) $p_i$ [divides](#def-b1-arith-divides) $N$; but $p_i$ also [divides](#def-b1-arith-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](#def-b1-arith-prime), 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](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#thm-b1-logic-induction)): $n = 2$ is [prime](#def-b1-arith-prime); for $n > 2$, either $n$ is [prime](#def-b1-arith-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](#def-b1-arith-prime) 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](#def-b1-arith-prime) exceeds $1$). For $r \geq 1$: the [prime](#def-b1-arith-prime) $p_1$ [divides](#def-b1-arith-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](#def-b1-arith-divides) some $q_j$. But $q_j$ is [prime](#def-b1-arith-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](#def-b1-arith-prime). ∎

**Proposition 6.16 (Valuations).**

For $p$ [prime](#def-b1-arith-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](#def-b1-arith-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](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-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](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-equiv) 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](#exo-b1-arith-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](#ex-b1-arith-pseudoprime) in miniature: [congruence](#def-b1-arith-congruence) checks refute, they do not certify.

**Proposition 6.20 (Invertibility mod nnn).**

$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](#met-b1-arith-euclid).

**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](#cor-b1-arith-bezout)). Uniqueness: if $ab \equiv ab' \equiv 1$, then $b \equiv b(ab') = (ab)b' \equiv b' \pmod n$. ∎

**Example 6.21 (Inverting 777 modulo 262626).**

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](#def-b1-arith-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](#rem-b1-arith-whereused), 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](#def-b1-arith-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](#def-b1-arith-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](https://one-course.com/books/math/3/en/chapter/2-counting#def-b1-counting-objects) $\binom pk
= \frac{p!}{k!(p-k)!}$ is divisible by $p$: indeed $k!\,(p-k)!\,
\binom pk = p!$ and $p$ [divides](#def-b1-arith-divides) $p!$ but is [coprime](#cor-b1-arith-bezout) 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](#prop-b1-arith-invmod)). ∎

**Example 6.24 (Fermat’s converse fails: 341341341).**

Fermat’s little theorem gives a cheap *compositeness* test: if $a^{n-1} \not\equiv 1 \pmod n$ for some $a$ [coprime](#cor-b1-arith-bezout) to $n$, then $n$ is not [prime](#def-b1-arith-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](#def-b1-arith-prime) of [Remark 6.27](#rem-b1-arith-whereused). Moral: an implication and its converse live separate lives ([Remark 1.10](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#rem-b1-logic-pitfalls)), 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).**

1. *Dividing a [congruence](#def-b1-arith-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](#def-b1-arith-divides) the [modulus](https://one-course.com/books/math/3/en/chapter/3-complex-numbers#def-b1-complex-field) too: $ac  \equiv bc \pmod n \iff a \equiv b \pmod{n/\gcd(c,n)}$ .
2. *Misusing Euclid’s lemma.* $a \mid bc$ implies $a  \mid b$ or $a \mid c$ only for $a$ *[prime](#def-b1-arith-prime)* (or [coprime](#cor-b1-arith-bezout) to one factor): $6 \mid 4 \times 9$ yet $6$ [divides](#def-b1-arith-divides) neither factor.
3. *[Coprime](#cor-b1-arith-bezout) is a relation, not a property.* “ $8$ and $9$ are [coprime](#cor-b1-arith-bezout) ” is true though neither is [prime](#def-b1-arith-prime) ; “pairwise [coprime](#cor-b1-arith-bezout) ” is stronger than “globally [coprime](#cor-b1-arith-bezout) ” ( $\gcd(6, 10, 15) = 1$ but no pair is [coprime](#cor-b1-arith-bezout) ).
4. *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](#ex-b1-arith-congruences) 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](https://one-course.com/books/math/3/en/chapter/8-polynomials#ch-b1-poly), where “degree” plays the role of absolute value; comparing the two chapters side by side is the best way to understand both. The [congruence](#def-b1-arith-congruence) calculus becomes the ring $\Z/n\Z$ in [Chapter 7](https://one-course.com/books/math/3/en/chapter/7-algebraic-structures#ch-b1-structures), whose invertible elements ([Proposition 6.20](#prop-b1-arith-invmod)) 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](https://one-course.com/books/math/3/en/chapter/10-real-numbers#ch-b1-reals). 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](#def-b1-arith-prime) used there.

**Remark 6.28 (Interlude: Z\ZZ 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](#def-b1-arith-divides) 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](https://one-course.com/books/math/3/en/chapter/8-polynomials#ch-b1-poly), where division by degree replaces division by size and everything above repeats *verbatim*; and, in miniature, inside every $\Z/n\Z$ of [Chapter 7](https://one-course.com/books/math/3/en/chapter/7-algebraic-structures#ch-b1-structures), where invertibility questions (this chapter’s [Proposition 6.20](#prop-b1-arith-invmod)) become structural [statements](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-statement) 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.](https://one-course.com/images/onecourse/chapters/math-3/b1-arith/fig-8546c89fa14c.svg)

*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](#met-b1-arith-euclid), and a Bézout pair for it.

**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](#def-b1-arith-divides) 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 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 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 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](#prop-b1-arith-valuation) and $\min(\alpha,\beta) +
\max(\alpha,\beta) = \alpha + \beta$.)*

**Solution of Exercise 6.5.**

For every [prime](#def-b1-arith-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](#def-b1-arith-prime) are equal ([Proposition 6.16](#prop-b1-arith-valuation)), 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 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](#prop-b1-arith-valuation)); 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](#def-b1-arith-prime) $p$, using valuations: compare $v_p$ of both sides of $p q^2 = r^2$.

**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](#cor-b1-arith-bezout) $m, n$, the pair of [congruences](#def-b1-arith-congruence) $x \equiv a \ (m)$, $x \equiv b\ (n)$ always has a solution, unique mod $mn$.

**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](#thm-b1-arith-gauss) (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](#exo-b1-arith-8))*.

**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](#exo-b1-arith-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](#met-b1-arith-euclid).*

**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](#def-b1-arith-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](#met-b1-arith-euclid) 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](#def-b1-arith-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](#def-b1-arith-prime), then $(n-1)!
\not\equiv -1 \pmod n$.

**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](#prop-b1-arith-invmod)). 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$.

1. Prove that $F_0 F_1 \cdots F_{n-1} = F_n - 2$ for $n \geq  1$ (induction).
2. Deduce that the Fermat numbers are pairwise [coprime](#cor-b1-arith-bezout) .
3. Deduce a second proof, independent of [Theorem 6.14](#thm-b1-arith-euclidprimes) , that there are infinitely many [primes](#def-b1-arith-prime) .

**Solution of Exercise 6.12.**

1. 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 .$$
2. Let $m < n$ and $d = \gcd(F_m, F_n)$ . By (1), $F_m$ [divides](#def-b1-arith-divides) $F_n - 2$ , so $d$ [divides](#def-b1-arith-divides) both $F_n$ and $F_n -  2$ , hence [divides](#def-b1-arith-divides) $2$ . But every Fermat number is odd, so $d = 1$ .
3. Each $F_n \geq 3$ has a [prime](#def-b1-arith-prime) divisor $p_n$ ( [Theorem 6.14](#thm-b1-arith-euclidprimes) ’s first step). If $m  \neq n$ , then $p_m \neq p_n$ , since a common [prime](#def-b1-arith-prime) would divide $\gcd(F_m, F_n) = 1$ . The [map](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-map) $n \mapsto p_n$ is therefore [injective](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-inj) from $\N$ into the [primes](#def-b1-arith-prime) : there are infinitely many [primes](#def-b1-arith-prime) .

## 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](#def-b1-arith-prime) $p$ dividing $n!$, or dividing a [binomial coefficient](https://one-course.com/books/math/3/en/chapter/2-counting#def-b1-counting-objects)? 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](#def-b1-arith-prime) theorem. Throughout, $p$ is a [prime](#def-b1-arith-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.**

1. 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$ .
2. Prove that for $x \in \R$ and $n \in \N^*$ , $\bigl\lfloor \lfloor x \rfloor / n \bigr\rfloor =  \lfloor x/n \rfloor$ .
3. 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)$ .
4. Show that the number of multiples of $m$ in $\intint1n$ is $\lfloor n/m \rfloor$ .
5. 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.**

6. Compute $v_5(1000!)$ and $v_2(1000!)$ , and conclude: how many zeros end $1000!$ ?
7. 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} .$$
8. Two consequences for $p = 2$ : show that $2^n$ never [divides](#def-b1-arith-divides) $n!$ , and that $2^{n-1}$ [divides](#def-b1-arith-divides) $n!$ exactly when $n$ is a power of $2$ .
9. 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.
10. 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.**

11. 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$.
12. 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$.)*
13. 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](#thm-b1-arith-fermat), recovered.)
14. Prove that $v_2\binom{2n}n = s_2(n)$ . Deduce that the central [binomial coefficient](https://one-course.com/books/math/3/en/chapter/2-counting#def-b1-counting-objects) is always even, and that $\binom{2n}n \equiv 2 \pmod 4$ exactly when $n$ is a power of $2$ .
15. Show, using Vandermonde’s identity ( [Exercise 2.7](https://one-course.com/books/math/3/en/chapter/2-counting#exo-b1-counting-7) ) and question 13, that $\binom{2p}p \equiv 2 \pmod p$ for every [prime](#def-b1-arith-prime) $p$ .
16. 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.**

17. 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$ .
18. Deduce that row $n$ of Pascal’s triangle contains exactly $2^{s_2(n)}$ odd entries; verify on rows $4$ and $5$ .
19. Deduce that all interior entries $\binom nk$ ( $0 < k < n$ ) are even if and only if $n$ is a power of $2$ .
20. Prove that every [prime](#def-b1-arith-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?)*
21. Deduce that $\binom{2n}n$ [divides](#def-b1-arith-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](#def-b1-arith-prime).

**Part V — Synthesis.**

22. 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.)*
23. 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.
24. 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](https://one-course.com/books/math/3/en/chapter/2-counting#ch-b1-counting) ? One sentence each.
25. Synthesis, in a short paragraph: Legendre’s formula turns a [divisibility](#def-b1-arith-divides) 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](#def-b1-arith-prime) (the full [statement](https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps#def-b1-logic-statement) , the [prime number](#def-b1-arith-prime) theorem, is far beyond this volume; the polynomial analogue of this chapter’s toolkit is [Chapter 8](https://one-course.com/books/math/3/en/chapter/8-polynomials#ch-b1-poly) ).

**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](#def-b1-arith-divides) used in [Theorem 6.23](#thm-b1-arith-fermat).

**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](#def-b1-arith-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](#prop-b1-arith-valuation), $\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](#def-b1-arith-prime) below $2n$, the lcm could not be this large: exponential growth of the lcm is a quantitative trace of the abundance of [primes](#def-b1-arith-prime).

**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](#def-b1-arith-divides) conclusion ([Proposition 6.16](#prop-b1-arith-valuation)). (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](https://one-course.com/books/math/3/en/chapter/2-counting#ch-b1-counting)-style arguments.

**25.** Legendre converts “what power of $p$ [divides](#def-b1-arith-divides) $n!$” into base-$p$ digit arithmetic; Kummer compresses the answer for [binomial coefficients](https://one-course.com/books/math/3/en/chapter/2-counting#def-b1-counting-objects) into the carries of a single addition — [divisibility](#def-b1-arith-divides), 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](#def-b1-arith-prime) theorem, whose proof lies far beyond this volume. The entire toolkit — division, gcd, valuations — is replayed for polynomials in [Chapter 8](https://one-course.com/books/math/3/en/chapter/8-polynomials#ch-b1-poly), where the analogue of a digit expansion is expansion in powers of $(X - a)$.