The Lumenary · Early undergraduate

Congruences

Name: ______________________

Date: ______________________

You will learn to

Prove that congruence modulo $n$ is an equivalence relation compatible with addition and multiplication, and use it to compute with remainders
Decide when $a$ has an inverse modulo $n$ and solve linear congruences $ax \equiv b \pmod n$ using Euclid's algorithm
State and prove the Chinese remainder theorem, and solve systems of congruences with coprime moduli
Prove Fermat's little theorem, Euler's theorem and Wilson's theorem, and use them to compute large powers modulo $n$
Explain why the converse of Fermat's theorem fails, using the Carmichael number $561$

1.
Which of these statements are true? (Choose all that apply.)
- A. $-3 \equiv 11 \pmod 7$
- B. $100 \equiv 1 \pmod 9$
- C. $2 \cdot 5 \equiv 2 \cdot 8 \pmod 6$ , so $5 \equiv 8 \pmod 6$
- D. $a \equiv b \pmod{12}$ implies $a \equiv b \pmod 4$
- E. $2^{10} \equiv 2^{0} \pmod{10}$ , because $10 \equiv 0 \pmod{10}$
2.
What is the last digit of $3^{2026}$ ?
3.
Find the inverse of $17$ modulo $43$ : the $x \in \{1, \dots, 42\}$ with $17x \equiv 1 \pmod{43}$ .
4.
Find the smallest positive integer $x$ with $x \equiv 2 \pmod 5$ , $x \equiv 3 \pmod 7$ and $x \equiv 4 \pmod 9$ .
5.
How many solutions modulo $36$ does the congruence $8x \equiv 12 \pmod{36}$ have?
6.
The second proof of Fermat's theorem reaches $a^{p-1}(p-1)! \equiv (p-1)! \pmod p$ and then cancels $(p-1)!$ . What justifies the cancellation?
- A. $(p-1)!$ is coprime to $p$ , because the prime $p$ divides none of the factors $1, \dots, p - 1$ (Euclid's lemma)
- B. $(p-1)! \equiv -1 \pmod p$ , by Wilson's theorem
- C.Any non-zero number can be cancelled in a congruence
- D. $(p-1)!$ is smaller than $p$
7.
Claim: "If $a^{n-1} \equiv 1 \pmod n$ for every $a$ coprime to $n$ , then $n$ is prime." Which number is a counterexample?
- A. $341 = 11 \cdot 31$
- B. $561 = 3 \cdot 11 \cdot 17$
- C. $91 = 7 \cdot 13$
- D. $97$
8.
Which Lean statement correctly formalises the existence half of the Chinese remainder theorem? (IsCoprime m n means $um + vn = 1$ for some $u, v$ .)
- A.theorem t {m n : ℤ} (h : IsCoprime m n) (a b : ℤ) : ∃ x, x ≡ a [ZMOD m] ∧ x ≡ b [ZMOD n]
- B.theorem t {m n : ℤ} (a b : ℤ) : ∃ x, x ≡ a [ZMOD m] ∧ x ≡ b [ZMOD n]
- C.theorem t {m n : ℤ} (h : IsCoprime m n) (a b : ℤ) : ∀ x, x ≡ a [ZMOD m] ∧ x ≡ b [ZMOD n]
- D.theorem t {m n x y : ℤ} (h : IsCoprime m n) (hm : x ≡ y [ZMOD m]) (hn : x ≡ y [ZMOD n]) : x ≡ y [ZMOD m * n]
9.
Write crt(residues, moduli) that returns the smallest $x \ge 0$ with $x \equiv r_i \pmod{m_i}$ for all $i$ , assuming the moduli are pairwise coprime. Combine the congruences one at a time, using an inverse modulo $m_i$ (Python's pow(a, -1, m) computes one). Then check Sunzi's answer.
Computational — Practice

Answer key — Congruences

1.
(a), (b) and (d) are true. (c) cancels the factor $2$ , which shares a divisor with $6$ : from $6 \mid 2(8 - 5)$ we only get $3 \mid 8 - 5$ . (e) reduces an exponent modulo $n$ , which is not allowed: Theorem 2 lets us reduce bases, and Euler's theorem lets us reduce exponents modulo $\varphi(n)$ for bases coprime to $n$ .
2.
$3^4 = 81 \equiv 1 \pmod{10}$ and $2026 = 4 \cdot 506 + 2$ , so $3^{2026} = (3^4)^{506} \cdot 3^2 \equiv 1 \cdot 9 = 9 \pmod{10}$ . The last digit is $9$ . (Euler's theorem gives $3^{\varphi(10)} = 3^4 \equiv 1$ directly.)
3.
$1 = 9 - 8 = 9 - (17 - 9) = 2 \cdot 9 - 17 = 2(43 - 2 \cdot 17) - 17 = 2 \cdot 43 - 5 \cdot 17$ . So $17 \cdot (-5) \equiv 1 \pmod{43}$ , and $-5 \equiv 38$ . Check: $17 \cdot 38 = 646 = 15 \cdot 43 + 1$ .
4.
Modulo $35$ : the numbers $\equiv 2 \pmod 5$ are $2, 7, 12, 17, \dots$ , and $17 \equiv 3 \pmod 7$ , so $x \equiv 17 \pmod{35}$ . Then $17 + 35k \equiv 8 - k \pmod 9$ , which is $4$ when $k \equiv 4$ . So $x = 17 + 140 = 157$ , unique modulo $315$ . Check: $157 = 31 \cdot 5 + 2 = 22 \cdot 7 + 3 = 17 \cdot 9 + 4$ .
5.
$d = \gcd(8, 36) = 4$ divides $12$ , so there are exactly $4$ solutions modulo $36$ . Dividing by $4$ : $2x \equiv 3 \pmod 9$ , whose unique solution is $x \equiv 6 \pmod 9$ ( $2 \cdot 6 = 12 \equiv 3$ ). Modulo $36$ this is $x \equiv 6, 15, 24, 33$ . Check one: $8 \cdot 15 = 120 = 3 \cdot 36 + 12$ .
6.
Theorem 3 allows cancelling $c$ when $\gcd(c, n) = 1$ . If the prime $p$ divided $(p - 1)! = 1 \cdot 2 \cdots (p - 1)$ , Euclid's lemma would make it divide one of the factors, each of which is smaller than $p$ and positive — impossible. So $\gcd((p - 1)!, p) = 1$ and the cancellation is valid.
7.
$561$ . It is composite, and for every prime factor $p \in \{3, 11, 17\}$ , $p - 1$ divides $560$ ; Fermat modulo each prime and the Chinese remainder theorem give $a^{560} \equiv 1 \pmod{561}$ for all $a$ coprime to $561$ . $341$ and $91$ fool some bases but not all; $97$ is prime.
8.
Option (a). (b) drops the coprimality hypothesis and is false; (c) replaces "there exists" by "for all"; (d) is the uniqueness half of the theorem.
9.
```
def crt(residues, moduli):
    x, M = 0, 1
    for r, m in zip(residues, moduli):
        t = (r - x) * pow(M, -1, m) % m
        x, M = x + t * M, M * m
    return x % M
```
Each step keeps the old congruences (we add a multiple of $M$ ) and makes the new one true; the inverse of $M$ modulo $m$ exists because $M$ is a product of moduli coprime to $m$ . For $[5, 6]$ modulo $[7, 11]$ : $61 = 8 \cdot 7 + 5 = 5 \cdot 11 + 6$ .