Exercises: Number Theory Foundations

These run from mechanical warm-ups to full proofs, code, modeling, and a "conjecture-then-prove" investigation. Difficulty: ⭐ foundational, ⭐⭐ intermediate, ⭐⭐⭐ challenging. Worked solutions to the daggered (†) and odd-numbered problems are in the appendix answers-to-selected.md — try them before you peek. The single habit this chapter rewards: the moment you see $a \mid b$, rewrite it as $b = ak$ for some integer $k$.

Part A — Warm-ups & computation (⭐)

22.1 † Translate each divisibility statement into an equation with an explicit integer witness. (a) $7 \mid 56$. (b) $a \mid 0$ for nonzero $a$. (c) $13 \mid n$.

22.2 Compute by hand: (a) the list of all positive divisors of $36$; (b) $\gcd(48, 18)$ showing every division step; (c) the prime factorization of $600$.

22.3 † Apply the Division Algorithm: find the unique $q$ and $r$ with $0 \le r < d$ for (a) $a = 100$, $d = 7$; (b) $a = -100$, $d = 7$; (c) $a = 7$, $d = 100$. For each, verify $a = dq + r$.

22.4 Trace the Euclidean algorithm on $\gcd(1071, 462)$. Write each line in the form $a = bq + r$, and circle the last nonzero remainder.

22.5 † Using the factorizations $720 = 2^4 \cdot 3^2 \cdot 5$ and $168 = 2^3 \cdot 3 \cdot 7$, read off $\gcd(720, 168)$ and $\operatorname{lcm}(720, 168)$ directly from the prime fingerprints. Then confirm your lcm using the identity $\gcd \cdot \operatorname{lcm} = ab$.

22.6 List the primes below $50$ by mentally running the Sieve of Eratosthenes. After crossing out multiples of which prime can you stop, and why?

Part B — Prove it (⭐⭐)

Each elementary proof here runs on the unpack–combine–repackage recipe from §22.1.

22.7 † Prove directly from the definition: for every nonzero integer $a$, $a \mid a$, and $1 \mid b$ for every integer $b$.

22.8 Prove: if $a \mid b$ and $a \mid c$, then $a \mid (b - c)$ and $a \mid (b + c)$. (Then note this is the linear-combination lemma of §22.1 with specific $m, n$.)

22.9 † (Scaffolded — fill the missing steps.) Prove that for nonzero integers $a, b$: if $a \mid b$ and $b \mid a$, then $a = b$ or $a = -b$. Fill in each blank.

• By definition of divisibility, $a \mid b$ gives $b = a\underline{\hphantom{xxx}}$ for some integer $j$, and $b \mid a$ gives $a = b\underline{\hphantom{xxx}}$ for some integer $k$.
• Substituting the first into the second: $a = (a j)k = a(\underline{\hphantom{xxx}})$.
• Since $a \neq 0$, cancel $a$ to get $\underline{\hphantom{xxx}} = 1$, with $j, k$ integers.
• The only integer pairs whose product is $1$ are $\underline{\hphantom{xxx}}$ and $\underline{\hphantom{xxx}}$, so $k = \pm 1$, giving $a = \pm b$. $\blacksquare$

22.10 Prove: if $d \mid n$ and $n > 0$ and $d > 0$, then $d \le n$. (This is the size bound the chapter uses to argue the Euclidean algorithm terminates — pin down exactly where the equation $n = dk$ forces $k \ge 1$.)

22.11 † Prove that if $a \mid b$ then $a \mid bc$ for every integer $c$. State which one-line algebraic move ("repackage") finishes it.

22.12 Prove that the product of any three consecutive integers is divisible by $6$. (Hint: among any two consecutive integers one is even; among any three consecutive integers one is a multiple of $3$. Combine using §22.1's linear-combination thinking, or argue case by case on remainders mod $6$.)

22.13 † Adapt Euclid's infinitude-of-primes argument to prove there are infinitely many primes of the form $4k + 3$. Use the supporting fact (which you may assume) that a product of integers each of the form $4k+1$ is itself of the form $4k+1$; consider $N = 4(p_1 p_2 \cdots p_r) - 1$ where the $p_i$ are the supposed finite list of primes $\equiv 3 \pmod 4$. Identify where the contradiction arises.

Part C — Implement it (⭐⭐)

Write Python for each. Do not run it — hand-trace and include an # Expected output: comment, matching the book's convention. Reference solutions live in code/exercise-solutions.py.

22.14 † Write divisors_fast(n) that returns the sorted list of positive divisors of $n$ by only trying candidates up to $\sqrt{n}$, adding both $d$ and $n // d$ when $d$ divides $n$. Explain in one sentence why testing past $\sqrt{n}$ is unnecessary, and show your function on $n = 36$.

22.15 Write lcm(a, b) for positive integers using the chapter's gcd, via $\operatorname{lcm}(a,b) = ab / \gcd(a,b)$. Why is dividing before multiplying (a // gcd(a,b) * b) the safer order for large inputs?

22.16 † Write an iterative version of the extended Euclidean algorithm, ext_gcd_iter(a, b), returning (g, x, y) with a*x + b*y == g. (The chapter gave the recursive version; the iterative one carries two coefficient pairs and updates them each loop.) Test it on $(252, 198)$ and confirm it agrees with the recursive ext_gcd.

22.17 Write mod_inverse_via_bezout(a, n) that returns the inverse of $a$ modulo $n$ when $\gcd(a, n) = 1$, by calling ext_gcd(a, n) and reducing the relevant coefficient into the range $[0, n)$ with x % n; if $\gcd(a, n) \neq 1$, return None. (This is a preview of Chapter 23's mod_inverse.) Show it on $a = 7$, $n = 26$.

Part D — Find the error (⭐⭐)

Each argument below is wrong. State precisely which step fails and why.

22.18 † Claim: "If $a \mid bc$, then $a \mid b$ or $a \mid c$." "Proof": "This is Euclid's Lemma." Find the flaw, and give the smallest counterexample with $a$ composite.

22.19 Claim: "For all integers $a, b$, $\gcd(a, b)$ equals the smallest positive value of $ax + by$ — therefore $\gcd(6, 9) = 1$, since $6(-1) + 9(1) = 3$ is not the smallest; we can reach $6(2) + 9(-1) = 3$, and surely some combination reaches $1$." Diagnose the error in the reasoning, and state what the smallest positive value of $6x + 9y$ actually is.

22.20 † "Proof" that $N = p_1 p_2 \cdots p_r + 1$ is always prime: "Euclid's theorem constructs $N$ and concludes it is a prime not on the list, so $N$ is prime." Explain why this misreads the proof, and exhibit the chapter's counterexample with concrete numbers.

22.21 Claim: "$\gcd(a, 0) = 0$ for every $a$, because $0$ divides everything." Two things are wrong here. Identify both, and state the correct value of $\gcd(a, 0)$ for $a \neq 0$.

Part E — Model it (⭐⭐⭐)

Translate each real scenario into the discrete-math objects of this chapter, then answer.

22.22 † (Gear ratios / repeating cycles.) Two gears mesh: one has $252$ teeth, the other $198$. Mark one tooth on each gear; they start aligned. (a) After how many teeth of engagement do the two marks realign? Express the answer as an lcm and compute it. (b) The smallest pair of co-rotating counts before any repeated relative position is governed by a gcd — which quantity, and what is it here? Tie each answer to a definition from the chapter.

22.23 (Sharding by remainder.) A web service distributes user records across $k$ database shards by shard = user_id % k. (a) Model "two distinct users $u_1, u_2$ collide on the same shard" as a congruence/divisibility statement about $u_1 - u_2$ and $k$. (b) If $k = 12$, give the divisibility condition on $u_1 - u_2$ for a collision, and explain in chapter language why exactly $1/12$ of id-differences cause one. (Modular notation is formalized in Chapter 23; here, phrase it with divisibility.)

22.24 † (Tiling.) You must tile a $1071 \times 462$ cm floor with identical square tiles, no cutting, edges flush to the walls. (a) What is the largest tile side length, and which chapter quantity is it? (b) How many such tiles are used? (c) Connect the "no cutting, flush to both walls" constraint to the definition of a common divisor.

Part F — Conjecture and test, then prove (⭐⭐⭐)

Use code to gather evidence (theme four: computation tests, proof settles), then prove or disprove.

22.25 † (The "every quotient is 1" worst case.) Conjecture: among all pairs $(a, b)$ with $1 \le b < a \le 100$, the pair requiring the most Euclidean-algorithm division steps relative to its size is a pair of consecutive Fibonacci numbers. (a) Write a function gcd_steps(a, b) that counts the division steps the Euclidean algorithm takes; include its # Expected output: on the inputs $(13, 8)$ and $(100, 99)$. (b) Use it (by hand-tracing a few revealing cases — Fibonacci pairs vs. random pairs) to gather evidence. (c) Then prove the supporting fact that drives the worst case: $\gcd(F_{n+1}, F_n) = 1$ for all $n \ge 1$, by induction, using the Euclidean step $\gcd(F_{n+1}, F_n) = \gcd(F_n, F_{n-1})$. (Recall the Fibonacci recurrence from Chapter 6.)

22.26 (Coprime probability.) Conjecture (a famous one): the "probability" that two integers drawn uniformly from $\{1, \dots, N\}$ are coprime tends to about $0.6079$ as $N \to \infty$. (a) Write coprime_fraction(N) that computes the exact fraction of ordered pairs $(a, b)$ in $\{1,\dots,N\}^2$ with $\gcd(a, b) = 1$, using the chapter's gcd. Give its # Expected output: for $N = 1$ and $N = 2$ (small enough to hand-verify). (b) You are not asked to prove the limit (it is $6/\pi^2$, beyond this chapter), but state in one sentence why the chapter's gcd makes computing the exact fraction for moderate $N$ feasible while factoring every pair would not.

22.27 † (Mersenne-style trap.) Conjecture: "$2^p - 1$ is prime whenever $p$ is prime." (a) Write is_prime_trial(n) by trial division and use it (hand-trace the relevant cases) to test the conjecture for $p = 2, 3, 5, 7, 11$. (b) Report the smallest prime $p$ for which $2^p - 1$ is composite, and give its factorization. (c) Prove the contrapositive-style fact that does hold: if $2^n - 1$ is prime, then $n$ is prime — by showing that if $n = ab$ with $1 < a, b < n$ then $(2^a - 1) \mid (2^n - 1)$, so $2^n-1$ is composite. (Hint: $2^{ab} - 1 = (2^a)^b - 1$, and $x - 1 \mid x^b - 1$.)

Part G — Interleaved & Deep Dive

Mixing in earlier chapters keeps the whole toolbox sharp. Pull only on what those chapters established.

22.28 † (Ch. 6 + 22.) Both the "every integer $> 1$ has a prime divisor" lemma and the existence half of the Fundamental Theorem of Arithmetic were proved by strong induction, not ordinary induction. Explain precisely what feature of these arguments forces strong induction — point to the step where $n = ab$ splits and say why "assume $P(n-1)$" is not enough.

22.29 (Ch. 5 + 22.) Euclid's proof of the infinitude of primes and the uniqueness half of the FTA are both proofs by contradiction. For each, state (i) the assumption that gets contradicted and (ii) the contradiction reached.

22.30 † (Ch. 4 + 22.) In Chapter 4 you proved facts about even and odd numbers directly. Recast "the product of two odd numbers is odd" using the divisibility language of this chapter: write "odd" as "not divisible by $2$" via the Division Algorithm ($n = 2q + r$, $r \in \{0, 1\}$), and complete the proof.

22.31 (Ch. 2 + 22.) Write the statement of Euclid's Lemma as a fully quantified logical formula (quantifiers over the integers and the prime $p$), using the connectives and the $\mid$ relation. Then write the statement that fails for composite $m$ (the negation pattern you exhibited in 22.18).

22.32 † (Deep Dive — sets up §23.) Prove the half of the modular-inverse fact you will need next chapter: if $\gcd(a, n) = 1$, then there is an integer $x$ with $ax \equiv 1 \pmod n$ — i.e. $n \mid (ax - 1)$. Use Bézout's identity directly, and identify the term that "vanishes mod $n$." (Then state, in one sentence, why no such $x$ exists when $\gcd(a, n) > 1$.)

22.33 (Deep Dive.) Prove that the Euclidean algorithm runs in $O(\log(\min(a, b)))$ division steps, by showing that in any two consecutive steps the smaller argument is at least halved. (Hint: if $a \ge b$ and $r = a \bmod b$, argue that $r < a/2$ by splitting into the cases $b \le a/2$ and $b > a/2$.) Connect the worst case to the Fibonacci result of 22.25.

Solutions to † and odd-numbered exercises: see appendices/answers-to-selected.md. For each proof, the rubric rewards: hypotheses unpacked into equations, the right combination chosen, a clean "repackage" into the definition, and — for the inductive proofs — a correctly placed base case and an explicit use of the (strong, where needed) hypothesis.