Number theory Study Guide

📖 Core Concepts Number Theory – study of integers, primes, and arithmetic functions. Prime Number – integer > 1 with no positive divisors except 1 and itself. Greatest Common Divisor (gcd) – largest integer dividing two numbers; computed by the Euclidean algorithm (repeated division). Fundamental Theorem of Arithmetic – every integer > 1 factors uniquely into primes (order ignored). Modular Arithmetic – arithmetic “mod $m$”; $a \equiv b \pmod m$ means $m\mid (a-b)$. Euler’s Totient $\varphi(n)$ – count of integers $1\le k\le n$ with $\gcd(k,n)=1$. Fermat’s Little Theorem – if $p$ is prime and $p\nmid a$, then $a^{p-1}\equiv1\pmod p$. Euler’s Theorem – if $\gcd(a,n)=1$, then $a^{\varphi(n)}\equiv1\pmod n$. Prime Number Theorem – $\displaystyle \pi(x)\sim\frac{x}{\log x}$ as $x\to\infty$. Riemann Zeta Function – $\displaystyle \zeta(s)=\sum{n=1}^{\infty}\frac{1}{n^{s}}$, convergent for $\operatorname{Re}(s)>1$. Euler Product – $\displaystyle \zeta(s)=\prod{p\ \text{prime}}\frac{1}{1-p^{-s}}$, linking $\zeta$ to primes. Sieve of Eratosthenes – iterative elimination of multiples to list all primes ≤ $N$. Quadratic Reciprocity – law describing solvability of $x^{2}\equiv p\pmod q$ vs $x^{2}\equiv q\pmod p$ (Gauss). Galois Group – set of field automorphisms of an extension $L/K$ fixing $K$. Solvability by Radicals – a polynomial is solvable by radicals ⇔ its Galois group is a solvable group. Genus of a Plane Curve – for a nonsingular curve of degree $d$, $g=\frac{(d-1)(d-2)}{2}$ (number of “holes”). --- 📌 Must Remember Euclidean Algorithm: repeatedly replace $(a,b)$ with $(b, a\bmod b)$ until remainder = 0; last non‑zero remainder = $\gcd(a,b)$. Euclid’s Proof of Infinite Primes: assume finitely many primes $p1,\dots,pk$, consider $N=p1p2\cdots pk+1$ → $N$ has a new prime factor. Fundamental Theorem of Arithmetic – uniqueness of prime factorization. Fermat’s Little Theorem: $a^{p-1}\equiv1\pmod p$ for prime $p$, $p\nmid a$. Euler’s Theorem: $a^{\varphi(n)}\equiv1\pmod n$ when $\gcd(a,n)=1$. Prime Number Theorem: $\pi(x)\approx x/\log x$ for large $x$. Euler Product: $\displaystyle \zeta(s)=\prod{p}\frac{1}{1-p^{-s}}$. Quadratic Reciprocity (Gauss) – central theorem of algebraic number theory. RSA Security: relies on difficulty of factoring $N=pq$ (large primes). Genus Formula: $g=\frac{(d-1)(d-2)}{2}$ for a nonsingular plane curve of degree $d$. --- 🔄 Key Processes | Process | Steps | |--------|-------| | Euclidean Algorithm | 1. Given $a,b$ with $a>b$, compute $r = a \bmod b$. <br>2. Replace $(a,b)\leftarrow(b,r)$. <br>3. Repeat until $r=0$. <br>4. $\gcd$ = last non‑zero $b$. | | Sieve of Eratosthenes | 1. List numbers $2\ldots N$. <br>2. Starting at the smallest remaining number $p$, mark all multiples $p\cdot k$ ($k\ge2$). <br>3. Move to next unmarked number and repeat. <br>4. Unmarked numbers are primes. | | Applying Fermat’s Little Theorem | 1. Verify $p$ is prime and $p\nmid a$. <br>2. Reduce exponent $e$ modulo $p-1$: $a^{e}\equiv a^{\,e \bmod (p-1)}\pmod p$. | | Using Euler’s Theorem | 1. Compute $\varphi(n)$. <br>2. Reduce exponent $e$ modulo $\varphi(n)$ when $\gcd(a,n)=1$: $a^{e}\equiv a^{\,e \bmod \varphi(n)}\pmod n$. | | Prime Number Theorem Approximation | 1. For large $x$, estimate $\pi(x)\approx x/\log x$. | | Genus Computation (plane curve) | 1. Identify degree $d$ of the curve. <br>2. Plug into $g=\frac{(d-1)(d-2)}{2}$. | --- 🔍 Key Comparisons Euclidean Algorithm vs. Sieve of Eratosthenes Goal: gcd computation vs. prime list generation. Method: repeated division vs. elimination of multiples. Fermat’s Little Theorem vs. Euler’s Theorem Modulus: prime $p$ vs. any $n$ coprime to $a$. Exponent: $p-1$ vs. $\varphi(n)$. Analytic vs. Algebraic Number Theory Tools: real/complex analysis vs. field/ring theory. Typical Topics: prime‑counting functions vs. ideal theory, Galois groups. Combinatorial Sieves vs. Large Sieves Approach: elementary inclusion–exclusion (e.g., Brun) vs. harmonic/functional analysis techniques. Prime vs. Composite Modulus in Modular Exponentiation Fermat’s theorem works only for prime moduli; Euler’s theorem works for any modulus with coprime base. --- ⚠️ Common Misunderstandings “$a\equiv b\pmod m$ means $a=b$.” It only means $m$ divides $a-b$, not equality. Fermat’s Little Theorem works for any modulus. It requires the modulus to be prime and $a$ not divisible by it. Unique factorization holds in every number field. It fails in many; ideals restore a form of uniqueness. RSA is broken because factoring is “hard”. Hardness is assumed; no polynomial‑time algorithm is known, but it isn’t proved impossible. Genus formula applies to any curve. It is valid only for nonsingular plane curves. Sieve of Eratosthenes finds primes beyond $\sqrt N$ automatically. You must still test remaining numbers; the sieve only guarantees removal of composites up to $\sqrt N$. --- 🧠 Mental Models / Intuition Primes as “atoms” of the integers – every integer is a unique “molecule” built from them. Modular arithmetic = clock arithmetic – think of numbers wrapping around at $m$. Totient $\varphi(n)$ = “phi‑count” of numbers that are “friendly” (coprime) to $n$. Euler product: the zeta function is a “prime fingerprint” – multiplying $(1-p^{-s})^{-1}$ over all primes builds the whole series. Galois group = symmetry group of roots – solvable groups = “nice” symmetries that can be untangled step by step (radicals). Genus = number of holes – visualize a surface; genus 0 = sphere, genus 1 = torus. --- 🚩 Exceptions & Edge Cases Euler’s theorem requires $\gcd(a,n)=1$; if not coprime, the congruence may fail. Fermat’s theorem fails when $a$ is a multiple of $p$. Unique factorization fails in rings like $\mathbb{Z}[\sqrt{-5}]$; need ideals. Quadratic reciprocity includes a sign factor $(-1)^{\frac{(p-1)(q-1)}{4}}$ for odd primes $p,q$. RSA decryption works only when the private exponent $d$ satisfies $ed\equiv1\pmod{\varphi(N)}$. Genus formula does not apply to singular curves or curves in higher dimensions. --- 📍 When to Use Which Compute $\gcd$ → Euclidean algorithm (fast, works for any integers). List all primes ≤ $N$ → Sieve of Eratosthenes (small/medium $N$). Reduce exponent modulo a prime modulus → Fermat’s little theorem. Reduce exponent modulo a composite modulus → Euler’s theorem (after checking coprime). Estimate number of primes up to $x$ → Prime Number Theorem approximation. Relate sums over integers to products over primes → Euler product (analytic proofs). Determine solvability of a polynomial by radicals → Examine its Galois group for solvability. Classify a nonsingular plane curve → Use genus formula $g=\frac{(d-1)(d-2)}{2}$. Choose a sieve method → Use combinatorial (Brun) for elementary twin‑prime estimates; use large sieve for density results requiring harmonic analysis. --- 👀 Patterns to Recognize Congruence patterns: $a^{p-1}\equiv1\pmod p$ suggests applying Fermat’s theorem. Prime‑counting: $\pi(x)$ grows like $x/\log x$ – expect fewer primes as numbers get larger. Euler product: Whenever a sum over $n^{-s}$ appears, look for a product over primes. Quadratic reciprocity signs: Both $p$ and $q$ odd → sign $(-1)^{\frac{(p-1)(q-1)}{4}}$. Sieve elimination: Multiples of $p$ start at $p^2$ (no need to cross‑out $2p,3p,\dots$ if already crossed by smaller primes). Galois‑solvability: Small degree (≤ 4) polynomials often have solvable groups; higher degree may not. --- 🗂️ Exam Traps Choosing $a^{p-1}\equiv1\pmod p$ when $p$ is composite – a common “Fermat” distractor. Assuming $\varphi(n)=n-1$ for any $n$ – only true for prime $n$. Reading “prime” as “odd” – 2 is prime and even; some statements forget it. Applying genus formula to a curve with a cusp or node – answer will be wrong because the curve isn’t nonsingular. Confusing Euclidean algorithm steps with division algorithm lemma – the lemma justifies the step; the algorithm is the iterative process. Believing the sieve of Eratosthenes automatically proves infinitude of primes – the sieve is finite; Euclid’s proof is needed. Mistaking “solvable by radicals” for “has rational roots” – solvability is about expressing roots using nested radicals, not about rationality. Choosing the large sieve when only elementary counting is required – adds unnecessary complexity and may lead to mis‑applied harmonic analysis. ---