Number Theory Cheat Sheet

Updated 2026-04-28

Next Topic: Numerical Methods for Computing Cheat Sheet

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.

Table 1: Divisibility FundamentalsTable 2: Prime Number TheoryTable 3: Modular ArithmeticTable 4: Fundamental TheoremsTable 5: Multiplicative FunctionsTable 6: Special Integer ClassesTable 7: Diophantine EquationsTable 8: Quadratic ResiduesTable 9: Continued FractionsTable 10: Partitions and Generating FunctionsTable 11: Primitive Roots and OrderTable 12: Algebraic Number TheoryTable 13: Fibonacci and Recurrence RelationsTable 14: Cryptographic Applications

Table 1: Divisibility Fundamentals

Concept	Example	Description
Divisibility	$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.
Division algorithm	$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$ .
Greatest common divisor (GCD)	$\gcd(48, 18) = 6$	• Largest positive integer dividing both $a$ and $b$ • if $\gcd(a,b)=1$ the numbers are coprime.
Euclidean algorithm	$\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.
Extended Euclidean algorithm	$6 = 48(-1) + 18(3)$	• Finds integers $x, y$ such that $ax + by = \gcd(a,b)$ (Bézout coefficients) • essential for modular inverses.

Table 1: Divisibility Fundamentals

Concept	Example	Description
Divisibility	$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.
Division algorithm	$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$ .
Greatest common divisor (GCD)	$\gcd(48, 18) = 6$	• Largest positive integer dividing both $a$ and $b$ • if $\gcd(a,b)=1$ the numbers are coprime.
Euclidean algorithm	$\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.
Extended Euclidean algorithm	$6 = 48(-1) + 18(3)$	• Finds integers $x, y$ such that $ax + by = \gcd(a,b)$ (Bézout coefficients) • essential for modular inverses.