Number Theory — Foundations¶

Job: Establish divisibility, unique factorization, and prime distribution tools needed for modular arithmetic, crypto, and Diophantine analysis.

Core¶

Divisibility: $a\mid b$ iff $\exists q$, $b=aq$. GCD via Euclidean algorithm: $\gcd(a,b)=\gcd(b,a\bmod b)$; Bézout: $\gcd(a,b)=\min\{ax+by>0:x,y\in\mathbb{Z}\}$.

Primes / irreducibles in $\mathbb{Z}_{>1}$: $p$ prime $\Leftrightarrow$ ($p\mid ab\Rightarrow p\mid a$ or $p\mid b$). FTA: every $n>1$ factors uniquely as $\prod p_i^{k_i}$ up to order.

Euclid: infinitely many primes. Euler product for $\operatorname{Re}s>1$: $$ \zeta(s)=\sum_{n\ge1}n^{-s}=\prod_p(1-p^{-s})^{-1}. $$ Prime number theorem: $\pi(x)\sim x/\log x$ (Hadamard–de la Vallée Poussin; elementary proofs exist via Erdős–Selberg).

Dirichlet's theorem. If $\gcd(a,q)=1$, then $\{n:n\equiv a\pmod q\}$ contains infinitely many primes. Proof uses nonvanishing of $L(1,\chi)$ for Dirichlet characters $\chi\bmod q$.

Arithmetic functions: multiplicative if $f(mn)=f(m)f(n)$ for $\gcd(m,n)=1$. Euler $\varphi(n)=n\prod_{p\mid n}(1-1/p)$; Möbius $\mu$; $\sum_{d\mid n}\mu(d)=1_{n=1}$; Dirichlet convolution $(f*g)(n)=\sum_{d\mid n}f(d)g(n/d)$.

Diophantine sketch: linear $ax+by=c$ solvable iff $\gcd(a,b)\mid c$. Pell $x^2-dy^2=1$ ($d>0$ squarefree) has infinitely many solutions via units in $\mathbb{Z}[\sqrt d]$.

Local–global (Hasse principle one-liner). A homogeneous quadratic $Q(x_1,\ldots,x_n)=0$ has a nontrivial $\mathbb{Q}$-point iff it has nontrivial points over $\mathbb{R}$ and every $\mathbb{Q}_p$ (Hasse–Minkowski). Failure outside quadrics measures Brauer–Manin and related obstructions.

See it¶

Euclidean algorithm + Bézout $\Rightarrow$ modular inverses exist iff $\gcd(a,n)=1$. Explicitly: $17\cdot(-2)+35\cdot1=1\Rightarrow 17^{-1}\equiv-2\equiv33\pmod{35}$.

Check¶

Prove: if $p$ prime divides $ab$ then $p\mid a$ or $p\mid b$.

If $p\nmid a$ then $\gcd(p,a)=1$, so $1=px+ay$ and $b=pxb+ayb$ with $p\mid ab\Rightarrow p\mid b$.

Why doesn't Euclid's proof give the least prime $>N$?

$N!+1$ has some prime factor $>N$, but that factor need not be prime itself as written and need not be the next prime; the argument is purely infinitude.

Pitfalls¶

Unique factorization fails in many $\mathbb{Z}[\sqrt d]$ (e.g. $\mathbb{Z}[\sqrt{-5}]$); need Dedekind domains / ideal factorization.
$\varphi$ is multiplicative, not completely multiplicative for all $n$ in the strongest sense without coprimality — check definitions when multiplying.
Dirichlet density vs natural density: differ on subtle sets; Dirichlet's theorem is usually stated with natural (or Dirichlet) density $1/\varphi(q)$.

Refs¶

Ireland–Rosen; Serre, A Course in Arithmetic; Hardy–Wright; Davenport, Multiplicative Number Theory.

Next¶

Modular arithmetic · Index · Cryptography