These notes cover MATH 145, the honours enrichment of MATH 135 at the University of Waterloo. The course develops the algebraic foundations underlying modern number theory and cryptography — divisibility, congruences, prime factorization, and the structure of modular arithmetic — at a level of rigour and depth suited to students who will continue into pure mathematics. Where MATH 135 states results, MATH 145 proves them; where MATH 135 computes, MATH 145 asks why the computation works.

---

Chapter 1: Logic and Proofs

Mathematics is a language before it is a subject. Before we can prove anything about integers, we need precise conventions for what it means to make a claim and what it means to establish that claim. This chapter sets up that vocabulary.

Mathematical Statements and Connectives

A mathematical statement is not merely a sentence — it is a sentence with a definite truth value. The power of formal logic is that it lets us manipulate truth values symbolically, building complex guarantees from simple ones.

The logical connectives allow us to build compound statements from simpler ones.

Two statements are logically equivalent if they agree on every possible truth assignment to their components.

The following equivalences are among the most useful. De Morgan’s Laws say that negation “distributes” through \(\vee\) and \(\wedge\) by swapping them.

Two further equivalences govern implications: the contrapositive and the negation.

Notice that the converse \(B \Rightarrow A\) is not equivalent to \(A \Rightarrow B\); confusing an implication with its converse is one of the most common errors in mathematical argument.

Quantifiers and Negation

Real mathematical statements almost always quantify over sets: “for all integers \(n\)…” or “there exists a prime \(p\) such that…”.

When quantifiers are nested, order matters enormously. The statement \(\forall x\, \exists y,\, x + y = 0\) says every integer has an additive inverse; the statement \(\exists y\, \forall x,\, x + y = 0\) would say there is a single \(y\) that works for all \(x\) simultaneously — a very different (and false) claim.

Proof Techniques

The four fundamental proof strategies each correspond to a logical manipulation.

A particularly important special case is the proof of an if and only if statement \(A \Leftrightarrow B\): one must prove both \(A \Rightarrow B\) and \(B \Rightarrow A\) separately.

---

Chapter 2: Mathematical Induction and Well-Ordering

Induction is the engine of number theory. Nearly every result about integers — from the existence of prime factorizations to Fermat’s Little Theorem — ultimately rests on induction or its close relative, the Well-Ordering Principle. Understanding the relationship between these two principles is itself an important theorem.

Simple Induction

Strong Induction and Well-Ordering

Simple induction proves \(P(k+1)\) using only the single hypothesis \(P(k)\). But for many problems — for instance, proving every integer greater than 1 has a prime factor — we need to use all the previous cases simultaneously. This motivates strong induction.

The third avatar of the same principle is the Well-Ordering Principle, which asserts that every non-empty set of natural numbers has a smallest element.

Proof (sketch). POMI \(\Rightarrow\) WOP: Suppose for contradiction that \(S \subseteq \mathbb{N}\) is non-empty with no smallest element. Let \(P(n)\) be “\(n \notin S\)”. Since \(S\) has no smallest element, \(1 \notin S\) (otherwise 1 would be smallest). If \(1, \ldots, k \notin S\), then \(k+1 \notin S\) (else it would be the minimum). By POMI, \(P(n)\) holds for all \(n\), so \(S = \emptyset\), a contradiction. WOP \(\Rightarrow\) POSI: If POSI fails, the set \(S = \{n : P(n) \text{ is false}\}\) is non-empty, so by WOP it has a minimum \(m\). Then \(P(j)\) holds for all \(j < m\), so the inductive step forces \(P(m)\) — contradicting \(m \in S\). \(\square\)

The practical upshot: in any proof by contradiction involving integers, we may freely invoke WOP; in any induction, we may freely use all previous cases.

---

Chapter 3: Divisibility and the Euclidean Algorithm

Divisibility is the central organizing concept of elementary number theory. Two integers may share common factors, and the greatest such factor — the GCD — encodes surprisingly deep information about their relationship. The Euclidean algorithm, some 2300 years old, computes this quantity efficiently and reveals its innermost structure.

Divisibility

The following three propositions are the workhorse lemmas of divisibility. Their proofs are direct: write everything in terms of the definition and observe that integer linear combinations of integers are integers.

Proof. Write \(b = ka\) and \(c = \ell b\) for integers \(k, \ell\). Then \(c = \ell b = \ell k a = (\ell k) a\), so \(a \mid c\). \(\square\)

Proof. Write \(b = sa\) and \(c = ta\). Then \(bx + cy = sax + tay = a(sx + ty)\), so \(a \mid (bx + cy)\). \(\square\)

Proof. Write \(b = ka\). Since \(b \neq 0\), we have \(k \neq 0\), so \(\lvert k \rvert \geq 1\). Then \(\lvert b \rvert = \lvert k \rvert \cdot \lvert a \rvert \geq \lvert a \rvert\). \(\square\)

The Division Algorithm

Before we can discuss GCDs, we need to establish that integer division always leaves a well-defined remainder. This is so basic it seems obvious — but it requires a proof.

Proof (existence). Consider the set \(S = \{a - qb : q \in \mathbb{Z},\, a - qb \geq 0\}\). This set is non-empty (take \(q = -\lvert a \rvert\), so \(a - qb = a + \lvert a \rvert b \geq 0\)). By the Well-Ordering Principle, \(S\) has a minimum element; call it \(r = a - q_0 b\) for some \(q_0\). We claim \(r < b\). If \(r \geq b\), then \(r - b = a - (q_0 + 1)b \geq 0\), so \(r - b \in S\) with \(r - b < r\), contradicting minimality. Hence \(0 \leq r < b\).

Uniqueness. Suppose \(a = q_1 b + r_1 = q_2 b + r_2\) with \(0 \leq r_1, r_2 < b\). Subtracting: \((q_1 - q_2)b = r_2 - r_1\). Since \(\lvert r_2 - r_1 \rvert < b\), we get \(\lvert q_1 - q_2 \rvert < 1\), forcing \(q_1 = q_2\) and hence \(r_1 = r_2\). \(\square\)

GCD and the Euclidean Algorithm

The GCD measures the “arithmetic complexity” of the pair \((a,b)\). Two integers with \(\gcd(a,b) = 1\) are called coprime and are, in an arithmetic sense, as unrelated as integers can be.

The key tool for computing GCDs efficiently is the following lemma, which says GCDs are preserved when we subtract a multiple.

Proof. It suffices to show the two pairs have the same set of common divisors. If \(d \mid a\) and \(d \mid b\), then \(d \mid (a - qb) = r\), so \(d\) is a common divisor of \(b\) and \(r\). Conversely, if \(d \mid b\) and \(d \mid r\), then \(d \mid (qb + r) = a\). The two sets of common divisors coincide, so their maxima coincide. \(\square\)

\[\gcd(a,b) = \gcd(b, r_1) = \gcd(r_1, r_2) = \cdots = \gcd(r_{k-1}, r_k) = \gcd(r_k, 0) = r_k.\]

The remainders \(r_1 > r_2 > \cdots \geq 0\) strictly decrease, so the algorithm terminates. The last nonzero remainder is the GCD.

Bézout’s Identity

Perhaps the single most important theorem in elementary number theory: the GCD is not merely the largest common divisor, it is the smallest positive integer combination of \(a\) and \(b\).

Proof. Let \(S = \{ax + by : x, y \in \mathbb{Z},\, ax + by > 0\}\). Since \(a^2 + b^2 > 0 \in S\) (well, \(a \cdot a + b \cdot b = a^2 + b^2 > 0\) for \((a,b) \neq (0,0)\)), \(S\) is non-empty. Let \(d\) be the smallest element of \(S\) (by WOP), say \(d = ax_0 + by_0\). We show \(d = \gcd(a,b)\).

First, every common divisor of \(a\) and \(b\) divides \(d = ax_0 + by_0\) (by DIC). In particular, \(d\) is an integer combination, so any common divisor is at most \(d\).

Second, \(d \mid a\). Write \(a = qd + r\) with \(0 \leq r < d\). Then \(r = a - qd = a - q(ax_0 + by_0) = a(1 - qx_0) + b(-qy_0)\) is an integer combination of \(a\) and \(b\). If \(r > 0\), then \(r \in S\) with \(r < d\), contradicting minimality. So \(r = 0\) and \(d \mid a\). Similarly \(d \mid b\).

Thus \(d\) is a positive common divisor of \(a\) and \(b\), and it is divisible by every common divisor, so \(d\) is the greatest common divisor. \(\square\)

The Extended Euclidean Algorithm (EEA) computes the Bézout coefficients \(x, y\) constructively by back-substituting through the steps of the Euclidean Algorithm.

Proof. By Corollary 3.11, write \(ax + cy = 1\) for integers \(x,y\). Multiply by \(b\): \(abx + cby = b\). Now \(c \mid ab\) so \(c \mid abx\), and certainly \(c \mid cby\), so \(c \mid (abx + cby) = b\). \(\square\)

---

Chapter 4: Primes and Unique Factorization

Primes are the atoms of multiplicative arithmetic — the integers that cannot be broken down further. The Fundamental Theorem of Arithmetic says that the factorization into primes is unique, a fact so basic that we rarely question it. But uniqueness is a genuine theorem; it does not hold in every number system, and its failure in rings like \(\mathbb{Z}[\sqrt{-5}]\) is one of the motivating problems of algebraic number theory.

Prime Numbers

Proof. Suppose \(p \nmid a\). Since \(p\) is prime, its only positive divisors are \(1\) and \(p\). Since \(p \nmid a\), we have \(\gcd(a,p) = 1\). By Proposition 3.12, \(p \mid b\). \(\square\)

Proof. Let \(p\) be the smallest divisor of \(n\) greater than 1. If \(p = ab\) with \(1 < a, b < p\), then \(a \mid n\) and \(a < p\), contradicting minimality; so \(p\) is prime. For the bound: if \(n\) is composite, write \(n = ab\) with \(1 < a \leq b < n\). Then \(a^2 \leq ab = n\), so \(a \leq \sqrt{n}\). \(\square\)

Infinitude of Primes

\[N = p_1 p_2 \cdots p_k + 1.\]

By Proposition 4.3, \(N > 1\) has a prime factor \(p\). Since every \(p_i\) divides the product \(p_1 \cdots p_k\), we have \(p_i \mid (N - p_1 \cdots p_k) = 1\) if \(p = p_i\), which is impossible. So \(p \notin \{p_1, \ldots, p_k\}\), contradicting that the list was complete. \(\square\)

The Fundamental Theorem of Arithmetic

Proof. Existence by strong induction: if \(n\) is prime we are done; if \(n\) is composite, write \(n = ab\) with \(1 < a, b < n\). By the inductive hypothesis both \(a\) and \(b\) have prime factorizations, and their product is a prime factorization of \(n\).

Uniqueness. Suppose \(n = p_1 p_2 \cdots p_s = q_1 q_2 \cdots q_t\) are two prime factorizations. Then \(p_1 \mid q_1 q_2 \cdots q_t\). By Euclid’s Lemma applied repeatedly, \(p_1 \mid q_j\) for some \(j\). Since \(q_j\) is prime and \(p_1 > 1\), we have \(p_1 = q_j\). Cancel \(p_1\) from both sides and repeat by strong induction on the number of prime factors. This forces \(s = t\) and the \(p_i\)’s are a rearrangement of the \(q_j\)’s. \(\square\)

---

Chapter 5: Diophantine Equations

A Diophantine equation asks: given integer coefficients, do integer solutions exist, and if so, what are all of them? The simplest nontrivial case — two unknowns, total degree one — is completely solved by the GCD theory we have built.

Linear Diophantine Equations

Proof. If \(ax + by = c\) has a solution, then since \(d \mid a\) and \(d \mid b\), by DIC we get \(d \mid c\). Conversely, if \(d \mid c\), write \(c = d \cdot m\). By Bézout, there exist \(x_0, y_0\) with \(ax_0 + by_0 = d\). Multiply through by \(m\): \(a(mx_0) + b(my_0) = dm = c\), giving the solution \(x = mx_0\), \(y = my_0\). \(\square\)

Proof. Any solution satisfies \(a(x - x_0) + b(y - y_0) = 0\), i.e., \(\frac{a}{d}(x - x_0) = -\frac{b}{d}(y - y_0)\). Since \(\gcd(a/d,\, b/d) = 1\) and the left side is divisible by \(b/d\), by CAD we get \((b/d) \mid (x - x_0)\), say \(x - x_0 = (b/d)n\). Substituting back gives \(y - y_0 = -(a/d)n\). \(\square\)

The Frobenius (Chicken McNugget) Theorem

The Frobenius problem asks: given relatively prime positive integers \(a\) and \(b\), what is the largest integer that cannot be represented as \(ax + by\) with \(x, y \geq 0\)?

Proof (sketch). By LDET 1, since \(\gcd(a,b) = 1\) divides every integer, the equation \(ax + by = n\) always has integer solutions. By LDET 2, the solutions are \(x = x_0 + bn\), \(y = y_0 - an\) for \(n \in \mathbb{Z}\). Among all solutions, choose the one with \(0 \leq x < b\). Then \(y = (n - ax)/b\). One checks that \(y \geq 0\) iff \(n \geq ax\). Since \(x \leq b-1\), this holds when \(n \geq a(b-1) = ab - a\). More carefully, the representable integers form the set \(\{ax + by : x,y \geq 0\}\); the non-representable integers are exactly those \(n\) for which no choice of remainder forces \(y \geq 0\), and \(ab - a - b\) is the largest such. \(\square\)

---

Chapter 6: Congruences

Modular arithmetic is the study of remainders after division, formalized as an equivalence relation on the integers. What makes it so powerful is that the equivalence is compatible with arithmetic operations — addition and multiplication of residues are well-defined — giving the integers modulo \(n\) the structure of a ring.

Basic Congruence Arithmetic

Equivalently, \(a \equiv b \pmod{m}\) if and only if \(a\) and \(b\) have the same remainder when divided by \(m\). The value \(m\) is called the modulus.

Proof. Write \(a = a' + sm\) and \(b = b' + tm\). Then \(a + b = (a' + b') + (s+t)m\), giving (1). For (3): \(ab = (a' + sm)(b' + tm) = a'b' + (a't + b's + stm)m\), giving (3). \(\square\)

Cancellation, however, requires care:

Proof. From \(ac \equiv bc\) we get \(m \mid c(a-b)\). Since \(\gcd(c,m) = 1\), by CAD, \(m \mid (a-b)\). \(\square\)

The Ring \(\mathbb{Z}/n\mathbb{Z}\)

The ring \(\mathbb{Z}/n\mathbb{Z}\) has additive identity \([0]\) and multiplicative identity \([1]\). Every element has an additive inverse (\(-[a] = [n-a]\)). But not every element has a multiplicative inverse: \([a]\) is invertible in \(\mathbb{Z}/n\mathbb{Z}\) if and only if \(\gcd(a,n) = 1\).

Proof. \([a]\) is a unit iff \(\exists b: ab \equiv 1 \pmod{n}\) iff the equation \(ax + ny = 1\) has integer solutions iff \(\gcd(a,n) \mid 1\) iff \(\gcd(a,n) = 1\). \(\square\)

The collection of all units forms a group under multiplication:

Linear Congruences

Proof. The congruence \(ax \equiv c \pmod{m}\) is equivalent to the LDE \(ax - my = c\). By LDET 1, solutions exist iff \(d \mid c\). By LDET 2, the general solution is \(x = x_0 + (m/d)n\) for \(n \in \mathbb{Z}\). Modulo \(m\), the values \(x_0, x_0 + m/d, x_0 + 2m/d, \ldots, x_0 + (d-1)m/d\) are the \(d\) distinct solutions. \(\square\)

The Chinese Remainder Theorem

One of the jewels of number theory: a system of simultaneous congruences with coprime moduli always has a unique simultaneous solution. The theorem has a constructive proof that doubles as an algorithm.

Proof. We give the constructive proof for \(k = 2\) and then describe the general case.

Case \(k = 2\): We want \(n\) with \(n \equiv a_1 \pmod{m_1}\) and \(n \equiv a_2 \pmod{m_2}\). The first congruence gives \(n = a_1 + m_1 t\) for some integer \(t\). Substituting into the second: \(a_1 + m_1 t \equiv a_2 \pmod{m_2}\), i.e., \(m_1 t \equiv a_2 - a_1 \pmod{m_2}\). Since \(\gcd(m_1, m_2) = 1\), this has a unique solution \(t_0 \pmod{m_2}\) by LCT. Setting \(n_0 = a_1 + m_1 t_0\) gives a solution unique modulo \(m_1 m_2\).

\[n \equiv \sum_{i=1}^k a_i M_i y_i \pmod{M}.\]

Since \(m_j \mid M_i\) for \(j \neq i\), the \(j\)-th term with \(i \neq j\) vanishes mod \(m_j\), leaving \(n \equiv a_j M_j y_j \equiv a_j \pmod{m_j}\). Uniqueness mod \(M\) follows because any two solutions differ by a multiple of each \(m_i\), hence by a multiple of \(M\). \(\square\)

---

Chapter 7: The Structure of \(\mathbb{Z}/n\mathbb{Z}\)

With the algebraic framework in place, we can prove the deep structure theorems: Fermat’s Little Theorem, its generalization via Euler’s totient, Wilson’s Theorem (an elegant characterization of primes), and the existence of primitive roots (generators of the multiplicative group).

Euler’s Totient Function

Proof. Among \(1, 2, \ldots, p^k\), exactly those divisible by \(p\) are not coprime to \(p^k\). There are \(p^{k-1}\) such multiples, so \(\phi(p^k) = p^k - p^{k-1}\). \(\square\)

Proof. By CRT, \(\mathbb{Z}/mn\mathbb{Z} \cong \mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}\). Under this isomorphism, \([a]_{mn}\) is a unit iff \([a]_m\) and \([a]_n\) are both units. So \(\phi(mn) = \phi(m)\phi(n)\). \(\square\)

Fermat’s Little Theorem

Fermat’s Little Theorem is the foundation of almost all practical primality testing and public-key cryptography. Its proof rests on a beautiful “symmetry” argument: multiplying all nonzero residues modulo \(p\) by \(a\) permutes them.

Proof. Consider the \(p-1\) residues \(a, 2a, 3a, \ldots, (p-1)a\) modulo \(p\). We claim these are a permutation of \(\{1, 2, \ldots, p-1\}\). Indeed:

• None is \(\equiv 0\): since \(p \nmid a\) and \(p \nmid j\) for \(1 \leq j \leq p-1\), we have \(p \nmid ja\).
• They are distinct: if \(ia \equiv ja \pmod{p}\), then \(p \mid (i-j)a\), and since \(\gcd(a,p) = 1\) we get \(p \mid (i-j)\), forcing \(i = j\) in the range \(1, \ldots, p-1\).

\[(a)(2a)(3a)\cdots((p-1)a) \equiv 1 \cdot 2 \cdot 3 \cdots (p-1) \pmod{p},\]

i.e., \(a^{p-1} \cdot (p-1)! \equiv (p-1)! \pmod{p}\). Since \(\gcd((p-1)!, p) = 1\), we cancel to get \(a^{p-1} \equiv 1 \pmod{p}\). \(\square\)

Euler’s Theorem

Euler’s Theorem is the generalization of FLT to composite moduli: the exponent \(p-1\) is replaced by \(\phi(n)\).

\[(au_1)(au_2)\cdots(au_{\phi(n)}) \equiv u_1 u_2 \cdots u_{\phi(n)} \pmod{n},\]

so \(a^{\phi(n)} \cdot U \equiv U \pmod{n}\) where \(U = u_1 \cdots u_{\phi(n)}\). Since \(U\) is a product of units, \(\gcd(U,n) = 1\), and we cancel to obtain \(a^{\phi(n)} \equiv 1 \pmod{n}\). \(\square\)

Wilson’s Theorem

Wilson’s Theorem gives an elegant necessary and sufficient condition for primality in terms of factorials. Unlike Fermat’s test, it is an exact characterization — but it is computationally expensive, making it a theoretical rather than practical primality test.

Proof. (\(\Leftarrow\)) If \(p\) is composite, say \(p = ab\) with \(1 < a < p\), then \(a \mid (p-1)!\) but \(a \nmid (-1)\) since \(a > 1\). So \((p-1)! \not\equiv -1 \pmod{p}\) when \(p\) is composite (the only edge case is \(p = 4\): \(3! = 6 \equiv 2 \not\equiv -1 \pmod{4}\)).

(\(\Rightarrow\)) Let \(p\) be prime. In \(\mathbb{Z}/p\mathbb{Z}\), every nonzero element has a unique inverse. The equation \(x^2 \equiv 1 \pmod{p}\) means \(p \mid (x-1)(x+1)\), so \(x \equiv \pm 1 \pmod{p}\). Hence the only elements equal to their own inverse are \(1\) and \(p-1 \equiv -1\).

\[(p-1)! = 1 \cdot \underbrace{(2 \cdot 3 \cdots (p-2))}_{\text{pairs multiply to } 1} \cdot (p-1) \equiv 1 \cdot 1 \cdot (-1) = -1 \pmod{p}.\]

\(\square\)

Primitive Roots

The group \((\mathbb{Z}/n\mathbb{Z})^*\) is a finite abelian group. A natural question is whether it is cyclic — generated by a single element. When \(n = p\) is prime, the answer is always yes.

Proof. Let \(k = \text{ord}_n(a)\) and write \(\phi(n) = qk + r\) with \(0 \leq r < k\). Then \(a^{\phi(n)} = (a^k)^q \cdot a^r \equiv a^r \equiv 1 \pmod{n}\). If \(r > 0\), then \(r < k\) and \(a^r \equiv 1\), contradicting the minimality of \(k\). So \(r = 0\). The general statement follows similarly. \(\square\)

Proof (sketch). The key lemma is that for a prime \(p\), the polynomial \(x^d - 1 \equiv 0 \pmod{p}\) has at most \(d\) roots in \(\mathbb{Z}/p\mathbb{Z}\) (since \(\mathbb{Z}/p\mathbb{Z}\) is a field). Let \(\psi(d)\) denote the number of elements of order exactly \(d\) in \((\mathbb{Z}/p\mathbb{Z})^*\). For each divisor \(d\) of \(p-1\), if any element has order \(d\), then its powers \(1, a, a^2, \ldots, a^{d-1}\) are all \(d\) roots of \(x^d \equiv 1\), and each has order dividing \(d\). One shows by an Euler-\(\phi\) counting argument that \(\psi(d) = \phi(d)\) for each divisor \(d\) of \(p-1\), so in particular \(\psi(p-1) = \phi(p-1) \geq 1\). \(\square\)

Quadratic Residues and Euler’s Criterion

Proof. The map \(a \mapsto a^2\) on \(\{1, \ldots, p-1\}\) is two-to-one: \(a^2 \equiv (-a)^2 \pmod p\), and since \(a \not\equiv -a\) (as \(p\) is odd), each square has exactly two preimages. So there are \((p-1)/2\) distinct squares. \(\square\)

Proof. By FLT, \(a^{p-1} \equiv 1\), so \((a^{(p-1)/2})^2 \equiv 1\), meaning \(a^{(p-1)/2} \equiv \pm 1\). If \(a = b^2\) is a QR, then \(a^{(p-1)/2} = b^{p-1} \equiv 1\). If \(a\) is a QNR, then \(a^{(p-1)/2} \not\equiv 1\) (since the only solutions to \(x^{(p-1)/2} \equiv 1\) are the \((p-1)/2\) QRs), so \(a^{(p-1)/2} \equiv -1\). \(\square\)

Proof. By Euler’s criterion, both sides equal \((ab)^{(p-1)/2} = a^{(p-1)/2} \cdot b^{(p-1)/2} \pmod p\). \(\square\)

---

Chapter 8: Cryptography and RSA

The classical problem of secure communication is: how can two parties exchange a secret over an insecure channel, without having first shared a key? For most of human history this seemed impossible. In 1976, Diffie and Hellman introduced the concept of public-key cryptography; in 1977, Rivest, Shamir, and Adleman discovered RSA, the first practical implementation. Its correctness is an elegant application of Euler’s Theorem and the Chinese Remainder Theorem.

Public-Key Cryptography

The idea is asymmetric: a public key is shared openly and used to encrypt; a private key is kept secret and used to decrypt. Anyone can send a message to Bob by encrypting with his public key, but only Bob can read it. The security rests on a trapdoor function: one that is easy to compute but hard to invert without secret information.

The RSA Algorithm

Proof. We must show \(M^{ed} \equiv M \pmod{n}\). Since \(ed \equiv 1 \pmod{(p-1)(q-1)}\), write \(ed = 1 + k(p-1)(q-1)\) for some integer \(k\).

\[M^{ed} = M^{1 + k(p-1)(q-1)} = M \cdot (M^{p-1})^{k(q-1)} \equiv M \cdot 1 = M \pmod{p}.\]

Case 2: \(p \mid M\). Then \(M^{ed} \equiv 0 \equiv M \pmod{p}\).

In both cases, \(M^{ed} \equiv M \pmod{p}\). By the same argument with \(p\) and \(q\) swapped, \(M^{ed} \equiv M \pmod{q}\). Since \(\gcd(p,q) = 1\) and both divide \(M^{ed} - M\), we have \(pq \mid M^{ed} - M\), i.e., \(M^{ed} \equiv M \pmod{n}\). \(\square\)

---

Appendix: Key Theorems Reference

For convenience, the major theorems of the course and their interdependencies:

• Division Algorithm (Theorem 3.5) — existence and uniqueness of quotient and remainder; proved using WOP.
• GCD WR (Proposition 3.7) — the key invariant behind the Euclidean Algorithm.
• Bézout’s Identity (Theorem 3.9) — GCD as smallest positive integer combination; proved using WOP.
• CAD (Proposition 3.12) — coprimeness and divisibility; follows from Bézout.
• Euclid’s Lemma (Lemma 4.2) — \(p \mid ab \Rightarrow p \mid a\) or \(p \mid b\); follows from CAD.
• FTA (Theorem 4.5) — unique prime factorization; existence by POSI, uniqueness by Euclid’s Lemma.
• LDET 1 & 2 (Theorems 5.2, 5.3) — existence and form of LDE solutions; follow from Bézout and LDET 1 respectively.
• LCT (Theorem 6.10) — linear congruences; follows from LDE theory.
• CRT (Theorem 6.11) — simultaneous congruences; follows from LCT plus coprimeness.
• FLT (Theorem 7.4) — \(a^{p-1} \equiv 1\) mod prime \(p\); proved by permutation argument.
• Euler’s Theorem (Theorem 7.6) — generalization of FLT to \(\phi(n)\); proved by same permutation argument.
• Wilson’s Theorem (Theorem 7.7) — \((p-1)! \equiv -1\) iff \(p\) prime; proved by self-pairing of inverses.
• RSA Correctness (Theorem 8.2) — \(M^{ed} \equiv M \pmod{n}\); proved from FLT + CRT.