Number theory is the branch of pure mathematics devoted to the study of integers and integer-valued functions, often called the "queen of mathematics" for its fundamental role across mathematical disciplines. At its core, number theory investigates divisibility, prime numbers, and modular arithmetic—concepts that power modern cryptography, computer science, and countless mathematical proofs. The field combines elementary techniques accessible to beginners with some of mathematics' deepest unsolved problems, making it both foundational and frontier-level. When exploring number theory, remember that most results stem from the interplay between multiplicative structure (primes, factorization) and additive structure (partitions, sums)—a duality that reveals patterns invisible to either lens alone.
What This Cheat Sheet Covers
This topic spans 14 focused tables and 107 indexed concepts. Below is a complete table-by-table outline of this topic, spanning foundational concepts through advanced details.
A jump-to index of every table row in this cheat sheet.
An interactive map of every table and concept in this topic.
Table 1: Divisibility Fundamentals
Everything in number theory grows from a single question: when does one integer divide another evenly? These concepts—the division algorithm, GCD and LCM, the Euclidean algorithm, and the notion of a prime—are the vocabulary the rest of the field is written in. The Fundamental Theorem of Arithmetic, that every integer factors uniquely into primes, is the keystone the whole subject rests on.
| Concept | Example | Description |
|---|---|---|
$7 \mid 35$ means $35 = 7 \cdot 5$ | • Integer $a$ divides $b$ (written $a \mid b$) if $b = ka$ for some integer $k$ • the remainder is zero. | |
$47 = 5 \cdot 9 + 2$ | For integers $a, b$ ($b > 0$), there exist unique $q, r$ with $a = bq + r$ and $0 \le r < b$. | |
$\gcd(48, 18) = 6$ | • Largest positive integer dividing both $a$ and $b$ • if $\gcd(a,b)=1$ the numbers are coprime. | |
$\gcd(48,18)$: $48=2(18)+12$, $18=1(12)+6$, $12=2(6)+0$ | • Efficient GCD computation by repeated division • terminates when remainder is zero. | |
$6 = 48(-1) + 18(3)$ | • Finds integers $x, y$ such that $ax + by = \gcd(a,b)$ (Bézout coefficients) • essential for modular inverses. |