Exercises: Modular Arithmetic

DataField.Dev

Exercises: Modular Arithmetic

These build from clock-arithmetic warm-ups to full proofs, code, and modeling. Difficulty: ⭐ foundational, ⭐⭐ intermediate, ⭐⭐⭐ challenging. Worked solutions to the starred-with-a-dagger (†) and odd-numbered problems are in the appendix answers-to-selected.md; try them before you peek. For the "implement it" problems, hand-trace your code and write an # Expected output: comment — never run it on the grader's machine.

Part A — Warm-ups (⭐)

23.1 † Decide each congruence by the divisibility test ("does $n$ divide $a-b$?"), showing the subtraction: (a) $38 \equiv 2 \pmod 9$, (b) $-4 \equiv 11 \pmod 5$, (c) $100 \equiv 0 \pmod 7$.

23.2 Compute each residue using the non-negative convention from §23.1: (a) $73 \bmod 10$, (b) $(-1) \bmod 12$, (c) $(-25) \bmod 7$, (d) $1000 \bmod 97$.

23.3 † Using the period-$4$ cycle of powers of $7$ modulo $10$ from §23.2, find the last digit of (a) $7^{53}$, (b) $7^{200}$, (c) $7^{4001}$. Show which residue in the cycle each exponent lands on.

23.4 Find a modular inverse by inspection (try the small residues): (a) $4^{-1} \bmod 9$, (b) $2^{-1} \bmod 7$, (c) $5^{-1} \bmod 11$. Verify each by multiplying back to $1$.

23.5 † In the worked computation of $7^{-1} \bmod 26$ in §23.3, point to the exact line of the back-substitution where the coefficient of $7$ first appears, and state what that coefficient becomes after reducing modulo $26$.

23.6 Using \pmod vs. \bmod correctly (§23.1), rewrite each English sentence as one symbolic statement: (a) "$23$ leaves remainder $2$ when divided by $7$"; (b) "$40$ and $4$ are congruent modulo $12$"; (c) "the residue of $58$ modulo $9$ is $4$."

Part B — Prove it (⭐⭐)

23.7 † (Scaffolded — fill the missing steps.) Prove the cancellation law for units: if $\gcd(c, n) = 1$ and $ca \equiv cb \pmod n$, then $a \equiv b \pmod n$. Fill the blanks:

Since $\gcd(c, n) = 1$, Theorem 23.3 guarantees that $c$ has $\underline{\hphantom{xxxxx}}$ modulo $n$; call it $c^{-1}$.
Multiply both sides of $ca \equiv cb \pmod n$ by $\underline{\hphantom{xxxxx}}$, giving $c^{-1}ca \equiv c^{-1}cb \pmod n$.
Because $c^{-1}c \equiv \underline{\hphantom{xxx}} \pmod n$, this simplifies to $\underline{\hphantom{xxxxx}}$, which is the claim. $\blacksquare$

23.8 Prove that if $a \equiv b \pmod n$, then $a^k \equiv b^k \pmod n$ for every integer $k \ge 1$. (Use Theorem 23.2 — the product rule — and induction on $k$, the technique from Chapter 6.)

23.9 † Prove that $a \equiv b \pmod n$ implies $\gcd(a, n) = \gcd(b, n)$. (Translate the congruence into $a = b + nk$ and use the fact from Chapter 22 that $\gcd(a, n) = \gcd(a - nk,\, n)$.)

23.10 Prove the uniqueness of the modular inverse: if $a x \equiv 1 \pmod n$ and $a y \equiv 1 \pmod n$, then $x \equiv y \pmod n$. (Multiply the first congruence by $y$ and use associativity; this is why §23.3 speaks of the inverse.)

23.11 † Prove that for a prime $p$, the only residues that are their own inverse are $1$ and $p - 1$. That is, $x^2 \equiv 1 \pmod p$ forces $x \equiv 1$ or $x \equiv p-1 \pmod p$. (Factor $x^2 - 1 = (x-1)(x+1)$ and use that $p$ is prime, i.e. Euclid's lemma from Chapter 22.)

23.12 Prove that if $\gcd(m, n) = 1$ then the map sending a residue $x$ modulo $mn$ to the pair $(x \bmod m,\ x \bmod n)$ is injective. (This is the uniqueness half of the CRT, Theorem 23.5; suppose two residues map to the same pair and show they are congruent modulo $mn$.)

Part C — Implement it (⭐⭐)

Write Python for each. Hand-trace and include an # Expected output: comment, matching the book's convention. You may reuse ext_gcd, mod_inverse, mod_pow, and crt from §§23.3–23.5.

23.13 † Write linear_congruence(a, b, n) that returns the sorted list of all solutions in $\{0, 1, \dots, n-1\}$ to $ax \equiv b \pmod n$, using the Theorem 23.4 rule: let $g = \gcd(a, n)$; return [] if $g \nmid b$, otherwise return the $g$ solutions. Test it on $6x \equiv 4 \pmod 8$ and on $4x \equiv 3 \pmod 6$.

23.14 Write order(a, n) that returns the multiplicative order of $a$ modulo $n$ — the smallest positive integer $k$ with $a^k \equiv 1 \pmod n$ — or None if $\gcd(a, n) \ne 1$. Use mod_pow. Test it on $a = 7, n = 10$ (the period-$4$ cycle of §23.2) and on $a = 2, n = 7$.

23.15 † Write totient_bruteforce(n) that computes $\phi(n)$ by counting the integers in $\{1, \dots, n\}$ coprime to $n$ (use gcd). Print $\phi(n)$ for $n = 1, \dots, 12$ and confirm $\phi(p) = p - 1$ at the primes and $\phi(12) = 4$ as in §23.6.

23.16 Write affine_decrypt(cipher, a, b, m) that inverts the affine map $x \mapsto (ax + b) \bmod m$ — i.e. recovers $x = a^{-1}(\text{cipher} - b) \bmod m$ — using mod_inverse. Decrypt the single value $c = 19$ under $a = 7, b = 3, m = 26$ (the multiplier whose inverse $15$ you met in §23.3).

Part D — Find the error (⭐⭐)

Each "proof" or computation below is wrong. State precisely which step fails and why.

23.17 † Claim: "Since $2 \cdot 4 \equiv 2 \cdot 1 \pmod 6$ (both sides are $\equiv 2$), we may cancel the $2$ to conclude $4 \equiv 1 \pmod 6$." Find the flaw. (Hint: §23.2's pitfall, and Theorem 23.3 — what does cancellation require?)

23.18 Claim: "To compute $3^{40} \bmod 7$, note $3^{40} = (3^7)^5 \cdot 3^5$, and by Fermat $3^7 \equiv 3 \pmod 7$, so $3^{40} \equiv 3^5 \cdot 3^5 = 3^{10} \pmod 7$." A student then says "and $3^{10} \equiv 3^{10}$, so I'm stuck." Diagnose the bookkeeping error: Fermat's exponent reduction works modulo a particular number — which one? Redo the reduction correctly using §23.6.

23.19 † Claim: "The system $x \equiv 1 \pmod 4$, $x \equiv 3 \pmod 6$ has a unique solution modulo $24$ by the Chinese Remainder Theorem." Find the flaw. (Check the hypothesis of Theorem 23.5. Does a solution even exist here? What is the right modulus to reason about?)

23.20 "Proof" that every nonzero residue modulo $n$ has an inverse: "Take the nonzero residues $1, 2, \dots, n-1$ and multiply each by $a$. As in the proof of Fermat's little theorem, this permutes them, so some $a \cdot i \equiv 1 \pmod n$, giving $a$ an inverse." Find the flaw. For which $n$ does the permutation argument actually hold, and where does it break for composite $n$ (give a concrete $a, n$)?

Part E — Model it & Conjecture and test (⭐⭐⭐)

23.21 † (Model it.) A barista's espresso machine runs a cleaning cycle every $6$th shot and a descaling cycle every $10$th shot, counting shots from $1$. The owner wants to know after how many shots both cycles fire on the same shot for the first time, and how often they coincide thereafter. Translate this into a statement about congruences (what are the two congruences a "coincidence shot" $x$ satisfies?), decide whether the CRT applies, and find the answer. Then explain — in the language of §23.4 — why the period of coincidences is $\operatorname{lcm}(6, 10)$ and not $6 \cdot 10$.

23.22 (Model it — hashing with relocation.) An open-addressing hash table of size $n = 13$ probes slots $h, h + s, h + 2s, h + 3s, \dots$ all taken $\bmod\ 13$, where $h$ is the initial hash and $s$ is a fixed step. Model "the probe sequence visits every slot" as a condition on $s$ and $n$ using §23.3. For which step values $s \in \{1, \dots, 12\}$ does the sequence hit all $13$ slots? State the general rule (in terms of $\gcd$) and justify it.

23.23 † (Conjecture and test, then prove.) Using mod_pow, tabulate $a^{n-1} \bmod n$ for $a = 2$ and every $n$ from $3$ to $20$. You will find that $2^{n-1} \equiv 1 \pmod n$ for every prime $n$ in range (Fermat, §23.6) — but conjecture what happens at the composite $n$. Find the smallest composite $n$ for which $2^{n-1} \equiv 1 \pmod n$ anyway. (Such an $n$ is a Fermat pseudoprime to base $2$; it is rare and shows why "$2^{n-1} \equiv 1$" is a necessary but not sufficient test for primality. You need not prove a general theorem — report the smallest one and explain what it means for primality testing, connecting to theme four.)

23.24 (Conjecture and test, then prove.) For a prime $p$, compute $(p-1)! \bmod p$ for $p = 3, 5, 7, 11, 13$ using a short loop with reduction at each step. Conjecture a clean formula for $(p-1)! \bmod p$. Then prove your conjecture for general prime $p$ by pairing each residue $2, 3, \dots, p-2$ with its inverse (Exercise 23.11 shows only $1$ and $p-1$ are self-paired). This is Wilson's theorem.

Part F — Interleaved & Deep Dive

Mixing techniques from earlier chapters keeps them sharp.

23.25 † (Ch. 22 + 23.) Use the extended Euclidean algorithm to compute $\gcd(240, 46)$ and integers $s, t$ with $240 s + 46 t = \gcd$. Then state whether $46$ has an inverse modulo $240$, and if so give it as a residue in $\{0, \dots, 239\}$. (This is the §23.3 inverse computation built directly on Chapter 22's algorithm.)

23.26 (Ch. 12 + 23.) Theorem 23.1 says congruence modulo $n$ is an equivalence relation. Recall from Chapter 12 that an equivalence relation on a set partitions it into equivalence classes. How many equivalence classes does congruence modulo $n$ produce, and what are their standard representatives? Briefly connect this to the definition of $\mathbb{Z}_n$.

23.27 † (Ch. 6 + 23.) Prove by induction on $a \ge 0$ that $a^p \equiv a \pmod p$ for every prime $p$ (the second form of Fermat's little theorem, §23.6). Use the base case $a = 0$ and, in the inductive step, the "freshman's dream" identity $(a + 1)^p \equiv a^p + 1 \pmod p$ — which holds because every interior binomial coefficient $\binom{p}{k}$ for $0 < k < p$ is divisible by the prime $p$ (Chapter 17). State clearly where the inductive hypothesis is used.

23.28 (Ch. 19 + 23.) The fast exponentiation of §23.5 is a divide-and-conquer algorithm: it reduces computing $b^e$ to computing $b^{\lfloor e/2 \rfloor}$. Write the recurrence $T(e)$ for the number of multiplications and use the reasoning of Chapter 19 to argue the solution is $\Theta(\log e)$. Why does this make a $2048$-bit RSA exponentiation feasible while the naive loop of §23.2 is not?

23.29 † (Deep Dive — the CRT speed-up.) RSA decryption computes $m = c^d \bmod n$ where $n = pq$. The standard optimization computes $m_p = c^d \bmod p$ and $m_q = c^d \bmod q$ separately, then reassembles $m$ via the CRT (§23.4). (a) Explain why each of $m_p, m_q$ is cheaper to compute than $m$ directly, referencing the cost model of Exercise 23.28. (b) Using Euler/Fermat, explain why one may further reduce the exponent $d$ modulo $p - 1$ when working modulo $p$. (c) Outline, in three or four sentences, how crt([m_p, m_q], [p, q]) recovers $m$ and why the answer is unique modulo $n$.

23.30 (Deep Dive.) Prove that $\phi$ is multiplicative for coprime arguments: if $\gcd(m, n) = 1$, then $\phi(mn) = \phi(m)\,\phi(n)$. Use the CRT bijection (§23.4): a residue modulo $mn$ corresponds to a pair (residue mod $m$, residue mod $n$), and argue that the pair is a unit modulo $(m, n)$ componentwise exactly when the original is a unit modulo $mn$. Conclude $\phi(pq) = (p-1)(q-1)$ for distinct primes — the number RSA's key generation uses.

Solutions to † and odd-numbered exercises: see appendices/answers-to-selected.md. For each proof, the rubric rewards: a clearly stated claim, correct translation of every congruence into "$a - b = nk$," explicit use of any inverse or hypothesis invoked, and a clean conclusion ending in $\blacksquare$.