**Module leader**: Sam Chow. --- # 1. Divisibility and congruences ### 1.0 Basics **Example 1.0.1.** 2 | 6 and 0 | 0. **Lemma 1.0.2.** [[Division with remainder for integers]]. **Example 1.0.3.** 42 is not a multiple of 10. **Example 1.0.4.** "Grothendieck prime", $57 = 3 \times 19$, is an example of a *composite* integer. **Theorem 1.0.6.** [[Infinitude of primes]]. ### 1.1 Euclid’s algorithm We define GCD of integers that are **not both zero** and introduce [[Euclid's Algorithm]]. **Example 1.1.1–2.** Find $\gcd(12,20)$ and $\gcd(2024,70)$. **Example 1.1.3.** Write $\gcd(2024,70)$ as a linear combination of $2024$ and $70$. **Lemma 1.1.4**. [[Bézout's lemma]]. **Corollary 1.1.5.** The common divisors (of integers that are not both zero) are the divisors of the GCD. ### 1.2 Prime factorisation **Lemma 1.2.1.** [[Euclid's lemma]]. **Theorem 1.2.2.** [[Fundamental theorem of arithmetic]]. **Lemma 1.2.3.** [[GCD and LCM from prime factorisation]]. **Corollary 1.2.4.** [[Product of LCM and GCD]]. One can use the FTA or Bézout's lemma to prove the following results. **Lemma 1.2.5.** If $(a,m) = (b,m) = 1$, then $(ab,m) = 1$. **Lemma 1.2.6.** General Euclid lemma: if $d\mid xy$ and $\gcd(x,d)=1$ then $d\mid y$. ### 1.3 Fermat/Mersenne primes, perfect numbers We define [[Fermat numbers]] (and primes), [[Mersenne primes]] and [[Perfect numbers]] using [[Divisor function]]. **Example 1.3.1.** $6$ is perfect. **Lemma 1.3.2.** [[Divisor function is multiplicative]]. **Example 1.3.3.** Euclid showed in the $4$th century that Mersenne primes can be used to construct even perfect numbers. **Theorem 1.3.4.** [[Euclid–Euler theorem]]. ### 1.4 Congruences **Example 1.4.1.** $17 \equiv 5 \pmod{12}$. **Lemma 1.4.3.** [[Modular arithmetic|Modular arithmetic is well-defined]]. **Lemma 1.4.4.** We restate the general Euclid's lemma, which states that if $(a,n)=1$ and $n\mid ab$ then $n\mid b$, in terms of congruences. 1. In terms of congruences, this means that $ax\equiv 0 \mod{n}$ and $(a,n)=1$ implies that $x\equiv 0 \mod n$. So $ax \equiv ay \mod n$ with $a,n$ coprime implies that $a(x-y)\equiv 0 \mod{n}$ so $x\equiv y \mod n$. 2. Also, if $ax\equiv 0 \mod n$ and $a\mid n$ then $x\equiv 0 \mod n$: if $n = ak$ for some $k \in \mathbb{Z}$ then $ak \mid ax \implies k \mid x$ yields $x \equiv 0 \mod k = \frac{n}{a}$. Similarly, this means that $ax\equiv ay \mod n$ and $a\mid n$ implies that $x\equiv y\mod \frac{n}{a}$. This is generalised by lemma 1.5.8. **Example 1.4.5.** $4x \equiv 4y \pmod 6 \iff 2x \equiv 2y \pmod 3 \iff x\equiv y \pmod 3$. The remaining results of this section demonstrate some modular obstructions to the solubility of diophantine equations. **Lemma 1.4.6.** Squares are $0$ or $1 \mod 4$. **Corollary 1.4.7.** $2023$ is not a sum of two squares. **Lemma 1.4.8.** We prove by induction on $k$ that integers of the form $4^k(8b + 7)$ where $k\geq 0$ and $b\in \mathbb{Z}$ are not sum of 3 squares (an example of **infinite descent**). ### 1.5 Linear congruences** Verify that $\mathbb{Z}/n\mathbb{Z}$ is a commutative ring. **Example 1.5.1.** Verifies the associativity of modular multiplication. We study its unit group, denoted $(\mathbb{Z}/n\mathbb{Z})^\times$. **Lemma 1.5.2.** [[Unit modulo n iff coprime to n]]. **Example 1.5.3.** $(\mathbb{Z}/6\mathbb{Z})^\times = \{1, 5\}$ so $\varphi(6) = 2$. **Lemma 1.5.5.** [[Integers modulo prime is a field and integers modulo composite is not]]. **Lemma 1.5.8.** [[Solutions to linear congruence]]. **Example 1.5.9.** Solve $9x \equiv 13 \mod 41$ using the extended Euclidean algorithm. **Theorem 1.5.10/14.** [[Chinese remainder theorem]]. **Corollary 1.5.15.** [[Euler's totient function is multiplicative]]. **Lemma 1.5.16.** [[Euler's totient function from prime factorisation]]: for $n \in \mathbb{N}$, $\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$. **Lemma 1.5.18.** [[Sum of Euler totient function of divisors]]. ### 1.6 Standard congruences** **Example 1.6.1.** Fast powering: computing $2^{200} \mod 13$ **Theorem 1.6.2.** [[Euler's theorem (Number Theory)]]. **Example 1.6.3.** Use CRT and Euler's theorem to find $2^{40}$ modulo $100$. **Corollary 1.6.4.** [[Fermat's little theorem]]. **Example 1.6.5/7.** $561$ is a [[Carmichael Numbers|Carmichael number]]. **Theorem 1.6.6.** [[Korselt’s criterion]]. We require some information about roots of polynomials to prove Wilson's theorem. **Lemma 1.6.8.** [[General roots lemma]]. **Lemma 1.6.10.** [[Subrings of a field is are integral domains]]. **Example 1.6.11.** General roots lemma does not hold for polynomials over non-integral domains. **Theorem 1.6.12.** [[Wilson's theorem]]. ### 1.7 Primitive roots* **Lemma 1.7.1.** (a) [[Power of Group Element is Identity only If Order divides]] (b) [[Lagrange's theorem (on Finite Groups)]] (c) [[Order of power of group element]]. It follows from the following result that there are primitive roots, modulo $p$ for any prime $p$, i.e. $(\mathbb{Z}/p\mathbb{Z})^\times$ is a _cyclic_ group of order $p-1$. Once you have a cyclic of order $N$, group theory tells you that the number of generators of a cyclic group of order $N$ is $\varphi(N)$ (see [[Subgroups of cyclic group]]). **Theorem 1.7.2.** [[Number of primitive roots modulo prime]]. **Example 1.7.3.** Use the above theorem to prove Wilson's theorem. **Conjecture 1.7.5.** Artin’s conjecture. We already know that we there exists a generator of $\mathbb{Z}/p\mathbb{Z}$, $g$. The following result uses this $g$ to build generators of $\mathbb{Z}/p^{k}\mathbb{Z}$ when $p$ is an odd prime. **Theorem 1.7.10.** [[Lifting primitive roots to prime powers]]. **Example 1.7.11.** **Theorem 1.7.12.** $\mathbb{Z}/2^{k}\mathbb{Z}$ is not cyclic for $k\geq 3$. **Theorem 1.7.14.** [[Classification of moduli with primitive roots]]. ### 1.8 Quadratic residues** **Lemma 1.8.1.** [[Quadratic residues modulo prime]]. **Example 1.8.2.** Compute the [[Legendre symbol]] $\left( \frac{x}{5} \right)$ for $0\leq x\leq 4$. **Theorem 1.8.4.** [[Euler’s criterion]]. **Corollary 1.8.5.** [[Legendre symbol is completely multiplicative]]. **Corollary 1.8.6.** [[Legendre symbol of -1]]. **Lemma 1.8.7.** [[Gauss’s lemma (number theory)]]. **Corollary 1.8.8.** [[Legendre symbol of 2]]. **Lemma 1.8.10.** Odd variant of Gauss’s lemma. **Theorem 1.8.11.** [[Law of quadratic reciprocity]]. **Lemma 1.8.13.** nth power residue criterion --- # 2. Diophantine Equations ### 2.1 The geometry of numbers **Lemma 2.1.3.** [[Determinant of a lattice in real n-space is independent of choice of basis]]. **Theorem 2.1.5/6.** [[Minkowski's theorem]]. **Remark 2.1.7.** Shortest vector problem: Using the Gram–Schmidt process, one can bound the length of the shortest non-zero vector in a lattice from below by the minimum length of the orthogonalised basis vectors. ### 2.2 Sums of squares* **Theorem 2.2.1.** [[Prime that is 1 modulo 4 is a sum of two squares]]. **Theorem 2.2.2.3/4/5.** [[Sum of two squares theorem]]. **Theorem 2.2.6.** [[Sum of three squares theorem]]. **Theorem 2.2.8/9.** [[Sum of four squares theorem]]. ### 2.3 Gaussian primes** Recall the definition of the [[Gaussian integers]] $\mathbb{Z}[i]$ and their **norm** $N:\mathbb{Z}[i] \to \mathbb{N}$. **Lemma 2.3.1.** Norm is totally multiplicative. **Lemma 2.3.2.** [[Unit group of ring of Gaussian integers]]. **Lemma 2.3.3.** [[Ring of Gaussian Integers is a Euclidean Domain]]. **Lemma 2.3.5.** Bézout's lemma for Gaussian integers. **Lemma 2.3.7.** Gaussian prime iff irreducible. **Lemma 2.3.8.** Unit multiples of Gaussian primes are Gaussian primes. **Lemma 2.3.9.** Norm is prime implies Gaussian prime. **Lemma 2.3.12.** Prime in $\mathbb{Z}$ that $3$ modulo $4$ is a Gaussian prime. **Theorem 2.3.13.** [[Gaussian integers form unique factorisation domain]]. **Theorem 2.3.14.** [[Classification of Gaussian primes]]. ### 2.4 Pythagorean triples **Theorem 2.4.2.** [[Parametrisation of Pythagorean triples]]. ### 2.5 Ternary quadratic equations **Theorem 2.5.1.** [[Quadratic-residue-based criterion for solubility of ternary quadratic equations]]. ### 2.6 Hensel’s lemma **Lemma 2.6.1.** [[Hensel's lemma]]. ### 2.7 Waring’s problem **Definition.** For $k \in \mathbb{N}$, define $g(k)$ as the smallest $s \in \mathbb{N}$ such that every $n \in \mathbb{N}$ can be written as the sum of s non-negative $k$th powers. **Theorem 2.7.1 (Refinement of Liouville, 1859).** $g(4) \leq 50$. **Example 2.7.2.** Lower bound: $g(k) \ge 2^k + \left\lfloor \left(\frac{3}{2} \right)^k \right\rfloor - 2$. **Theorem 2.7.3 (Siksek, 2016).** Every integer gt; 454$ is a sum of seven non-negative cubes. **Theorem 2.7.4.** For $k \ge 2$, we have $G(k) \ge k + 1$. ### 2.8 Diophantine approximation (unlikely to be examined) **Lemma 2.8.1.** For all $\alpha \in \mathbb{R}$, there exists $a \in \mathbb{Z}$, $q \in \mathbb{N}$ such that $\left| \alpha - \frac{a}{q} \right| \le \frac{1}{2q}$. **Theorem 2.8.2 (Dirichlet’s Approximation Theorem).** For $\alpha \in \mathbb{R}$ and $Q \in \mathbb{N}$, there exist a, $q \in \mathbb{Z}$ with $1 \le q \le Q$ such that $\left| \alpha - \frac{a}{q} \right| < \frac{1}{qQ}$ **Corollary 2.8.3.** If $\alpha \in \mathbb{R} \setminus \mathbb{Q}$, then there are infinitely many reduced fractions $\frac{a}{q}$ such that $\left| \alpha - \frac{a}{q} \right| < \frac{1}{q^2}$ **Theorem 2.8.4 (Hurwitz, 1891).** If $\alpha \in \mathbb{R} \setminus \mathbb{Q}$, then there are infinitely many reduced fractions $\frac{a}{q}$ such that $\left| \alpha - \frac{a}{q} \right| < \frac{1}{\sqrt{5}q^2}$ **Theorem 2.8.5 (Liouville, 1844).** If $\alpha \in \mathbb{R}$ is algebraic of degree $n \ge 2$, then there exists $c > 0$ such that for all $a \in \mathbb{Z}$, $q \in \mathbb{N}$, $\left| \alpha - \frac{a}{q} \right| > \frac{c}{q^n}$ **Theorem 2.8.6 (Roth, 1955).** If $\alpha \in \mathbb{R} \setminus \mathbb{Q}$ is algebraic and $\varepsilon > 0$, then there exists $c = c(\alpha, \varepsilon) > 0$ such that $\left| \alpha - \frac{a}{q} \right| > \frac{c}{q^{2+\varepsilon}}$. ### 2.9 Pell’s equation (non-examinable) **Example 2.9.1.** **Lemma 2.9.2.** Multiplicativity of Pell solutions **Corollary 2.9.3.** **Theorem 2.9.4.** (Lagrange, 1768) **Corollary 2.9.5.** Infinitely many positive solutions **Lemma 2.9.6.** **Lemma 2.9.7.**