Number Theory: A Complete Summary of Definitions, Theorems, and Proofs

A single-article survey of undergraduate number theory. Covers divisibility, congruences, the Euclidean algorithm, primes, quadratic residues, arithmetic functions, continued fractions, p-adic valuations, and algebraic integers, together with all key algorithms and a dependency diagram.

Folio Official

March 1, 2026

1. Introduction: How to Use This Article

This article provides a single-page panoramic view of undergraduate number theory. For each topic, we present the key definitions, major theorems, and algorithms in concise form.

How to use this page:

Newcomers: read the sections in order to build a coherent picture of the subject.
Review or exam preparation: jump to any section from the table of contents.
Quick algorithm lookup: Section 14, “ Theorem and Algorithm Directory,”{} collects all the major results in one list.

The dependency diagram below shows how the main topics are interrelated.

graph TD
    A["Divisibility and Congruences"] --> B["GCD and the Euclidean Algorithm"]
    A --> C["Primes and the Fundamental Theorem of Arithmetic"]
    A --> D["Applications of Congruences and Group Structure"]
    B --> D
    C --> D
    D --> E["Primitive Roots and Discrete Logarithms"]
    B --> F["The Chinese Remainder Theorem"]
    D --> F
    D --> G["Quadratic Residues"]
    E --> G
    C --> H["Arithmetic Functions"]
    B --> I["Continued Fractions"]
    C --> J["Distribution of Primes"]
    C --> K["p-adic Valuations"]
    C --> L["Algebraic Integers"]

    style A fill:#f5f5f5,stroke:#333,color:#000
    style D fill:#f5f5f5,stroke:#333,color:#000
    style F fill:#f5f5f5,stroke:#333,color:#000
    style L fill:#f5f5f5,stroke:#333,color:#000

Remark 1.

This article is designed to accompany the “ Number Theory Textbook”{} series. Links at the end of each section point to the corresponding full-length chapter for detailed exposition and complete proofs.

2. Divisibility and Congruences

Definition 2 (Divisibility).

For integers

a, b

with

b \neq = 0

, we say

b

divides

a

(written

b ∣ a

) if there exists an integer

q

such that

a = b q

Theorem 3 (Division algorithm).

For any integer

a

and any positive integer

b

, there exist unique integers

q

and

r

satisfying

a = b q + r

with

0 \leq r < b

Definition 4 (Congruence).

For integers

a, b

and a positive integer

m

, we write

a \equiv b (mod m)

and say

a

is congruent to

b

modulo

m

m ∣ (a - b)

Theorem 5 (Basic properties of congruences).

Congruence modulo

m

is an equivalence relation that is compatible with addition and multiplication:

If $a \equiv b (mod m)$ and $c \equiv d (mod m)$ , then $a + c \equiv b + d (mod m)$ .
If $a \equiv b (mod m)$ and $c \equiv d (mod m)$ , then $a c \equiv b d (mod m)$ .

For more details:

https://interconnectd.app/articles/tl9PzBamVG1DClrnfPND

3. The Greatest Common Divisor and the Euclidean Algorithm

Definition 6 (Greatest common divisor).

The greatest common divisor of integers

a

and

b

, denoted

g cd (a, b)

, is the largest integer that divides both

a

and

b

. When

g cd (a, b) = 1

, we say

a

and

b

are coprime.

Theorem 7 (Euclidean algorithm).

For

a \geq b > 0

g cd (a, b) = g cd (b, a mod b)

. When

a mod b = 0

g cd (a, b) = b

Theorem 8 (Bézout's identity).

For any integers

a

and

b

, there exist integers

x

and

y

such that

g cd (a, b) = a x + b y

. These coefficients can be computed by the extended Euclidean algorithm.

Key algorithms:

Euclidean algorithm: computes $g cd (a, b)$ in $O (lo g (min (a, b)))$ time.
Extended Euclidean algorithm: simultaneously computes $g cd (a, b)$ and the Bézout coefficients $x, y$ in $O (lo g (min (a, b)))$ time.

For more details:

https://interconnectd.app/articles/i8B2T2slxyAs04RfZwii

4. Primes and the Fundamental Theorem of Arithmetic

Definition 9 (Prime number).

An integer

p \geq 2

is called prime if its only positive divisors are

1

and

p

. An integer

n \geq 2

that is not prime is called composite.

Theorem 10 (Fundamental theorem of arithmetic).

Every integer

n \geq 2

can be written as a product of primes, uniquely up to the order of the factors:

n = p_{1}^{e_{1}} p_{2}^{e_{2}} \dots p_{k}^{e_{k}}

Theorem 11 (Infinitude of primes).

There are infinitely many primes (Euclid).

Key algorithms:

Trial division: factors $n$ into primes in $O (n)$ time.
Sieve of Eratosthenes: enumerates all primes up to $n$ in $O (n lo g lo g n)$ time.
Miller–Rabin primality test: a probabilistic primality test running in $O (k lo g^{2} n)$ time ( $k$ iterations).

For more details:

https://interconnectd.app/articles/D4QlRLFTZ44RqYuw18Br

5. Applications of Congruences and the Group Structure of Residue Classes

Definition 12 (Residue class).

The equivalence classes of

Z

under congruence modulo

m

are called residue classes. The set of all residue classes is denoted

Z / m Z

Definition 13 (Group of units).

(Z / m Z)^{\times} = {a \in Z / m Z ∣ g cd (a, m) = 1}

forms a group under multiplication, called the group of units (or the multiplicative group of integers modulo

m

Definition 14 (Euler's totient function).

φ (m) = ∣ (Z / m Z)^{\times} ∣

, the number of integers from

1

m

that are coprime to

m

, is called Euler's totient function.

Theorem 15 (Euler's theorem).

g cd (a, m) = 1

, then

a^{φ (m)} \equiv 1 (mod m)

Theorem 16 (Fermat's little theorem).

p

is prime and

p ∤ a

, then

a^{p - 1} \equiv 1 (mod p)

Theorem 17 (Wilson's theorem).

An integer

p \geq 2

is prime if and only if

(p - 1)! \equiv - 1 (mod p)

Key algorithms:

Repeated squaring (binary exponentiation): computes $a^{n} mod m$ in $O (lo g n)$ time.
Modular inverse: when $g cd (a, m) = 1$ , computed via the extended Euclidean algorithm, or via Fermat's little theorem as $a^{p - 2} mod p$ when $m = p$ is prime.

For more details:

https://interconnectd.app/articles/lTZdM37Wgc5RIzEiJ2tN

6. Primitive Roots and Discrete Logarithms

Definition 18 (Multiplicative order).

When

g cd (a, m) = 1

, the smallest positive integer

k

satisfying

a^{k} \equiv 1 (mod m)

is called the multiplicative order of

a

modulo

m

, denoted

ord_{m} (a)

Definition 19 (Primitive root).

ord_{m} (a) = φ (m)

, then

a

is called a primitive root modulo

m

Theorem 20 (Existence of primitive roots).

A primitive root modulo

m

exists if and only if

m = 1, 2, 4, p^{k}

, or

2 p^{k}

, where

p

is an odd prime and

k \geq 1

Definition 21 (Discrete logarithm).

When

g

is a primitive root modulo

m

, the integer

x

satisfying

g^{x} \equiv a (mod m)

is called the discrete logarithm of

a

to the base

g

, written

ind_{g} a

Theorem 22 (Number of primitive roots).

When a primitive root modulo

m

exists, the total number of primitive roots modulo

m

φ (φ (m))

Key algorithms:

Baby-step giant-step: solves the discrete logarithm problem $g^{x} \equiv a (mod p)$ in $O (p)$ time and space.

For more details:

https://interconnectd.app/articles/cg1LJsuTDD1fAw6DMD4H

7. The Chinese Remainder Theorem and Applications

Theorem 23 (Chinese remainder theorem (CRT)).

m_{1}, m_{2}, \dots, m_{k}

are pairwise coprime (

g cd (m_{i}, m_{j}) = 1

for

i \neq = j

), then the system of simultaneous congruences

x \equiv a_{1} (mod m_{1}), x \equiv a_{2} (mod m_{2}), \dots, x \equiv a_{k} (mod m_{k})

has a unique solution modulo

M = m_{1} m_{2} \dots m_{k}

Theorem 24 (Ring isomorphism).

When

g cd (m_{i}, m_{j}) = 1

for all

i \neq = j

, there is a ring isomorphism

Z / M Z ≅ Z / m_{1} Z \times Z / m_{2} Z \times \dots \times Z / m_{k} Z

Key algorithms:

Constructive CRT: setting $M_{i} = M / m_{i}$ , the solution is $x \equiv \sum_{i = 1}^{k} a_{i} M_{i} (M_{i}^{- 1} mod m_{i}) (mod M)$ in $O (k lo g M)$ time.
Garner's algorithm: applies the CRT incrementally, avoiding overflow for large $M$ , in $O (k^{2})$ time.

For more details:

https://interconnectd.app/articles/cdLXHKAHUWG27KrVJ2wO

8. Quadratic Residues and Reciprocity

Definition 25 (Quadratic residue).

Let

p

be an odd prime. If

g cd (a, p) = 1

and the congruence

x^{2} \equiv a (mod p)

has a solution, then

a

is called a quadratic residue modulo

p

; otherwise,

a

is a quadratic nonresidue.

Definition 26 (Legendre symbol).

(\frac{a}{p}) = ⎩ ⎨ ⎧ 1 - 1 0 if a is a quadratic residue modulo p if a is a quadratic nonresidue modulo p if p ∣ a

Theorem 27 (Euler's criterion).

(\frac{a}{p}) \equiv a^{(p - 1) /2} (mod p)

Theorem 28 (Law of quadratic reciprocity (Gauss)).

For distinct odd primes

p

and

q

(\frac{p}{q}) (\frac{q}{p}) = (- 1)^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}}

Theorem 29 (First and second supplements).

(\frac{- 1}{p}) = (- 1)^{(p - 1) /2}, (\frac{2}{p}) = (- 1)^{(p^{2} - 1) /8}

Key algorithms:

Tonelli–Shanks algorithm: finds a solution to $x^{2} \equiv a (mod p)$ in $O (lo g^{2} p)$ time.

For more details:

https://interconnectd.app/articles/iVThwiqRtPK0X11EGjo5

9. Arithmetic Functions and Multiplicativity

Definition 30 (Arithmetic function).

A complex-valued function

f : Z_{> 0} \to C

defined on the positive integers is called an arithmetic function.

Definition 31 (Multiplicative function).

An arithmetic function

f

with

f (1) = 1

is called multiplicative if

f (mn) = f (m) f (n)

whenever

g cd (m, n) = 1

. It is called completely multiplicative if

f (mn) = f (m) f (n)

for all positive integers

m, n

Definition 32 (Important arithmetic functions).

Euler's totient function $φ (n)$ : the number of integers $k$ with $1 \leq k \leq n$ and $g cd (k, n) = 1$ .
Divisor function $σ_{k} (n) = \sum_{d ∣ n} d^{k}$ . In particular, $σ_{0} (n) = d (n)$ counts the number of divisors and $σ_{1} (n) = σ (n)$ gives the sum of divisors.
Möbius function $μ (n)$ : equals $1$ if $n = 1$ ; equals $(- 1)^{k}$ if $n$ is a product of $k$ distinct primes; equals $0$ otherwise (i.e., if $n$ has a squared prime factor).

Theorem 33 (Möbius inversion formula).

F (n) = \sum_{d ∣ n} f (d)

, then

f (n) = \sum_{d ∣ n} μ (n / d) F (d)

Definition 34 (Dirichlet convolution).

The Dirichlet convolution of two arithmetic functions

f

and

g

is defined by

(f * g) (n) = \sum_{d ∣ n} f (d) g (n / d)

. The Dirichlet convolution of two multiplicative functions is again multiplicative.

Key algorithms:

Computing $φ (n)$ : from the prime factorization, $φ (n) = n \prod_{p ∣ n} (1 - 1/ p)$ in $O (n)$ time.
Sieve-based batch computation: computes $φ (k)$ and $μ (k)$ for all $k \leq n$ in $O (n lo g lo g n)$ time.

For more details:

https://interconnectd.app/articles/2mHIeAkwmeJTGTXDnEuS

10. Continued Fractions and Diophantine Approximation

Definition 35 (Continued fraction expansion).

The (regular) continued fraction expansion of a real number

α

is a representation of the form

α = a_{0} + \frac{1}{a _{1} + \frac{1}{a _{2} + \frac{1}{⋱}}} = [a_{0}; a_{1}, a_{2}, \dots]

where

a_{0} \in Z

and

a_{i} \in Z_{> 0}

for

i \geq 1

. The expansion is finite if and only if

α

is rational.

Definition 36 (Convergents).

The rational number

[a_{0}; a_{1}, \dots, a_{n}] = p_{n} / q_{n}

is called the

n

-th convergent of

α

. The numerators and denominators satisfy the recurrence

p_{n} = a_{n} p_{n - 1} + p_{n - 2}, q_{n} = a_{n} q_{n - 1} + q_{n - 2} .

Theorem 37 (Best rational approximation).

The convergent

p_{n} / q_{n}

is the best rational approximation to

α

among all fractions whose denominator does not exceed

q_{n}

Theorem 38 (Lagrange's theorem).

A real number

α

is a quadratic irrational if and only if its continued fraction expansion is eventually periodic.

Theorem 39 (Pell's equation).

D

is a positive integer that is not a perfect square, the positive integer solutions of

x^{2} - D y^{2} = 1

can be obtained from the convergents of the continued fraction expansion of

D

For more details:

https://interconnectd.app/articles/JcTNQc7t9vXwAR9kqyOP

11. The Distribution of Primes

Definition 40 (Prime-counting function).

π (x) = # {p \leq x ∣ p is prime}

is called the prime-counting function.

Theorem 41 (Prime number theorem).

π (x) \sim \frac{x}{ln x} (x \to \infty)

That is,

lim_{x \to \infty} \frac{π ( x )}{x / l n x} = 1

Definition 42 (Chebyshev functions).

The Chebyshev functions are defined by

θ (x) = \sum_{p \leq x} ln p

and

ψ (x) = \sum_{p^{k} \leq x} ln p

Theorem 43 (Chebyshev's theorem).

There exist positive constants

c_{1}

and

c_{2}

such that, for all sufficiently large

x

c_{1} \frac{x}{ln x} \leq π (x) \leq c_{2} \frac{x}{ln x}

Theorem 44 (Dirichlet's theorem on primes in arithmetic progressions).

g cd (a, m) = 1

, then the arithmetic progression

a, a + m, a + 2 m, \dots

contains infinitely many primes.

Remark 45.

The Riemann hypothesis asserts that all nontrivial zeros of the Riemann zeta function

ζ (s) = \sum_{n = 1}^{\infty} n^{- s}

lie on the critical line

Re (s) = 1/2

. This remains one of the most important open problems in mathematics, intimately connected to the precise distribution of primes.

For more details:

https://interconnectd.app/articles/HIdN0m82xGJIRw6fKrx6

12. $p$ -adic Valuations and Local Methods

Definition 46 (

p

-adic valuation).

For a prime

p

and a nonzero integer

n

, the $p$ -adic valuation

v_{p} (n)

is the largest power of

p

dividing

n

. By convention,

v_{p} (0) = + \infty

Definition 47 (

p

-adic absolute value).

The $p$ -adic absolute value is defined by

∣ n ∣_{p} = p^{- v_{p} (n)}

for

n \neq = 0

, and

∣0 ∣_{p} = 0

Theorem 48 (Properties of the

p

-adic valuation).

$v_{p} (ab) = v_{p} (a) + v_{p} (b)$ .
$v_{p} (a + b) \geq min (v_{p} (a), v_{p} (b))$ (corresponding to the ultrametric inequality).
Equality condition: when $v_{p} (a) \neq = v_{p} (b)$ , $v_{p} (a + b) = min (v_{p} (a), v_{p} (b))$ .

Definition 49 (Ring of

p

-adic integers and the field of

p

-adic numbers).

The completion of

Q

with respect to the

p

-adic absolute value is the field of $p$ -adic numbers

Q_{p}

. The subring

Z_{p} = {x \in Q_{p} ∣ ∣ x ∣_{p} \leq 1}

is the ring of $p$ -adic integers.

Theorem 50 (Hensel's lemma).

Let

f (x) \in Z_{p} [x]

. If

f (a) \equiv 0 (mod p)

and

f^{'} (a) \neq \equiv 0 (mod p)

, then there exists

α \in Z_{p}

with

f (α) = 0

and

α \equiv a (mod p)

Theorem 51 (Connection with the Legendre symbol).

For an odd prime

p

with

g cd (a, p) = 1

, the congruence

x^{2} \equiv a (mod p)

has a solution if and only if

x^{2} = a

has a solution in

Q_{p}

(by lifting via Hensel's lemma).

For more details:

https://interconnectd.app/articles/ZA2dCEwFwQE9nq5a2lm6

13. Introduction to Algebraic Integers

Definition 52 (Algebraic integer).

An element

α \in C

is called an algebraic integer if it is a root of a monic polynomial with integer coefficients. The set of all algebraic integers forms a ring.

Definition 53 (Number field and ring of integers).

A finite extension

K

Q

is called a number field (or algebraic number field). The set of elements of

K

that are algebraic integers is denoted

O_{K}

and called the ring of integers of

K

Example 54 (Quadratic fields).

For

K = Q (d)

, where

d

is a squarefree integer,

O_{K} = {Z [d] Z [\frac{1 + d}{2}] if d \equiv 2, 3 (mod 4) if d \equiv 1 (mod 4)

Definition 55 (Ideal).

An ideal

a

O_{K}

is an additive subgroup satisfying

O_{K} \cdot a \subseteq a

Theorem 56 (Unique factorization of ideals).

Every nonzero ideal of

O_{K}

factors uniquely (up to order) as a product of prime ideals:

a = p_{1}^{e_{1}} p_{2}^{e_{2}} \dots p_{r}^{e_{r}}

This is a fundamental property of Dedekind domains.

Definition 57 (Class number).

The class number

h_{K}

is the order of the ideal class group

Cl (O_{K})

(the group of equivalence classes of fractional ideals). We have

h_{K} = 1

if and only if

O_{K}

is a unique factorization domain (UFD).

Theorem 58 (Minkowski's bound).

Every ideal class contains an ideal whose norm does not exceed the Minkowski bound:

M_{K} = \frac{n !}{n ^{n}} (\frac{4}{π})^{r_{2}} ∣ Δ_{K} ∣

where

n = [K : Q]

r_{2}

is the number of pairs of complex embeddings, and

Δ_{K}

is the discriminant.

For more details:

https://interconnectd.app/articles/GBReud95ZKuEOOK2VgnD

14. Theorem and Algorithm Directory

A one-line summary of the major theorems and algorithms encountered in undergraduate number theory and competitive programming.

Fundamental theorems:

Division algorithm: $a = b q + r$ with $0 \leq r < b$ , uniquely determined.
Fundamental theorem of arithmetic: every positive integer factors uniquely into primes.
Bézout's identity: there exist integers $x, y$ with $g cd (a, b) = a x + b y$ .
Fermat's little theorem: $p ∤ a \Rightarrow a^{p - 1} \equiv 1 (mod p)$ .
Euler's theorem: $g cd (a, m) = 1 \Rightarrow a^{φ (m)} \equiv 1 (mod m)$ .
Wilson's theorem: $p$ is prime $⟺ (p - 1)! \equiv - 1 (mod p)$ .
Chinese remainder theorem: a system of congruences with pairwise coprime moduli has a unique solution.
Existence of primitive roots: primitive roots exist modulo $m$ if and only if $m = 1, 2, 4, p^{k}, 2 p^{k}$ .
Law of quadratic reciprocity: $(\frac{p}{q}) (\frac{q}{p}) = (- 1)^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}}$ .
Möbius inversion formula: $F = f * 1 \Rightarrow f = F * μ$ .
Prime number theorem: $π (x) \sim x / ln x$ .
Dirichlet's theorem: if $g cd (a, m) = 1$ , then $a + km$ is prime for infinitely many $k$ .

Algebraic structure theorems:

CRT ring isomorphism: $Z / M Z ≅ \prod Z / m_{i} Z$ .
Hensel's lemma: a simple root modulo $p$ lifts to a root in $Z_{p}$ .
Unique factorization of ideals: prime ideal factorization is unique in Dedekind domains.
Lagrange's theorem (continued fractions): quadratic irrationals have eventually periodic continued fractions.

Key algorithms:

Euclidean algorithm (GCD): $O (lo g (min (a, b)))$
Extended Euclidean algorithm (GCD + Bézout coefficients): $O (lo g (min (a, b)))$
Sieve of Eratosthenes (prime enumeration): $O (n lo g lo g n)$
Trial division (prime factorization): $O (n)$
Miller–Rabin (primality testing): $O (k lo g^{2} n)$
Repeated squaring (modular exponentiation): $O (lo g n)$
Constructive CRT: $O (k lo g M)$
Garner's algorithm (CRT): $O (k^{2})$
Baby-step giant-step (discrete logarithm): $O (p)$
Tonelli–Shanks (square root $mod p$ ): $O (lo g^{2} p)$
Computing $φ (n)$ (via prime factorization): $O (n)$

Number Theory Algebra Summary Theorem Reference Algorithms Competitive Programming

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

Number Theory: A Complete Summary of Definitions, Theorems, and Proofs

Folio Official

March 1, 2026

1. Introduction: How to Use This Article

This article provides a single-page panoramic view of undergraduate number theory. For each topic, we present the key definitions, major theorems, and algorithms in concise form.

How to use this page:

Newcomers: read the sections in order to build a coherent picture of the subject.
Review or exam preparation: jump to any section from the table of contents.
Quick algorithm lookup: Section 14, “ Theorem and Algorithm Directory,”{} collects all the major results in one list.

The dependency diagram below shows how the main topics are interrelated.

graph TD
    A["Divisibility and Congruences"] --> B["GCD and the Euclidean Algorithm"]
    A --> C["Primes and the Fundamental Theorem of Arithmetic"]
    A --> D["Applications of Congruences and Group Structure"]
    B --> D
    C --> D
    D --> E["Primitive Roots and Discrete Logarithms"]
    B --> F["The Chinese Remainder Theorem"]
    D --> F
    D --> G["Quadratic Residues"]
    E --> G
    C --> H["Arithmetic Functions"]
    B --> I["Continued Fractions"]
    C --> J["Distribution of Primes"]
    C --> K["p-adic Valuations"]
    C --> L["Algebraic Integers"]

    style A fill:#f5f5f5,stroke:#333,color:#000
    style D fill:#f5f5f5,stroke:#333,color:#000
    style F fill:#f5f5f5,stroke:#333,color:#000
    style L fill:#f5f5f5,stroke:#333,color:#000

Remark 1.

2. Divisibility and Congruences

Definition 2 (Divisibility).

For integers

a, b

with

b \neq = 0

, we say

b

divides

a

(written

b ∣ a

) if there exists an integer

q

such that

a = b q

Theorem 3 (Division algorithm).

For any integer

a

and any positive integer

b

, there exist unique integers

q

and

r

satisfying

a = b q + r

with

0 \leq r < b

Definition 4 (Congruence).

For integers

a, b

and a positive integer

m

, we write

a \equiv b (mod m)

and say

a

is congruent to

b

modulo

m

m ∣ (a - b)

Theorem 5 (Basic properties of congruences).

Congruence modulo

m

is an equivalence relation that is compatible with addition and multiplication:

If $a \equiv b (mod m)$ and $c \equiv d (mod m)$ , then $a + c \equiv b + d (mod m)$ .
If $a \equiv b (mod m)$ and $c \equiv d (mod m)$ , then $a c \equiv b d (mod m)$ .

For more details:

https://interconnectd.app/articles/tl9PzBamVG1DClrnfPND

3. The Greatest Common Divisor and the Euclidean Algorithm

Definition 6 (Greatest common divisor).

The greatest common divisor of integers

a

and

b

, denoted

g cd (a, b)

, is the largest integer that divides both

a

and

b

. When

g cd (a, b) = 1

, we say

a

and

b

are coprime.

Theorem 7 (Euclidean algorithm).

For

a \geq b > 0

g cd (a, b) = g cd (b, a mod b)

. When

a mod b = 0

g cd (a, b) = b

Theorem 8 (Bézout's identity).

For any integers

a

and

b

, there exist integers

x

and

y

such that

g cd (a, b) = a x + b y

. These coefficients can be computed by the extended Euclidean algorithm.

Key algorithms:

Euclidean algorithm: computes $g cd (a, b)$ in $O (lo g (min (a, b)))$ time.
Extended Euclidean algorithm: simultaneously computes $g cd (a, b)$ and the Bézout coefficients $x, y$ in $O (lo g (min (a, b)))$ time.

For more details:

https://interconnectd.app/articles/i8B2T2slxyAs04RfZwii

4. Primes and the Fundamental Theorem of Arithmetic

Definition 9 (Prime number).

An integer

p \geq 2

is called prime if its only positive divisors are

1

and

p

. An integer

n \geq 2

that is not prime is called composite.

Theorem 10 (Fundamental theorem of arithmetic).

Every integer

n \geq 2

can be written as a product of primes, uniquely up to the order of the factors:

n = p_{1}^{e_{1}} p_{2}^{e_{2}} \dots p_{k}^{e_{k}}

Theorem 11 (Infinitude of primes).

There are infinitely many primes (Euclid).

Key algorithms:

Trial division: factors $n$ into primes in $O (n)$ time.
Sieve of Eratosthenes: enumerates all primes up to $n$ in $O (n lo g lo g n)$ time.
Miller–Rabin primality test: a probabilistic primality test running in $O (k lo g^{2} n)$ time ( $k$ iterations).

For more details:

https://interconnectd.app/articles/D4QlRLFTZ44RqYuw18Br

5. Applications of Congruences and the Group Structure of Residue Classes

Definition 12 (Residue class).

The equivalence classes of

Z

under congruence modulo

m

are called residue classes. The set of all residue classes is denoted

Z / m Z

Definition 13 (Group of units).

(Z / m Z)^{\times} = {a \in Z / m Z ∣ g cd (a, m) = 1}

forms a group under multiplication, called the group of units (or the multiplicative group of integers modulo

m

Definition 14 (Euler's totient function).

φ (m) = ∣ (Z / m Z)^{\times} ∣

, the number of integers from

1

m

that are coprime to

m

, is called Euler's totient function.

Theorem 15 (Euler's theorem).

g cd (a, m) = 1

, then

a^{φ (m)} \equiv 1 (mod m)

Theorem 16 (Fermat's little theorem).

p

is prime and

p ∤ a

, then

a^{p - 1} \equiv 1 (mod p)

Theorem 17 (Wilson's theorem).

An integer

p \geq 2

is prime if and only if

(p - 1)! \equiv - 1 (mod p)

Key algorithms:

Repeated squaring (binary exponentiation): computes $a^{n} mod m$ in $O (lo g n)$ time.
Modular inverse: when $g cd (a, m) = 1$ , computed via the extended Euclidean algorithm, or via Fermat's little theorem as $a^{p - 2} mod p$ when $m = p$ is prime.

For more details:

https://interconnectd.app/articles/lTZdM37Wgc5RIzEiJ2tN

6. Primitive Roots and Discrete Logarithms

Definition 18 (Multiplicative order).

When

g cd (a, m) = 1

, the smallest positive integer

k

satisfying

a^{k} \equiv 1 (mod m)

is called the multiplicative order of

a

modulo

m

, denoted

ord_{m} (a)

Definition 19 (Primitive root).

ord_{m} (a) = φ (m)

, then

a

is called a primitive root modulo

m

Theorem 20 (Existence of primitive roots).

A primitive root modulo

m

exists if and only if

m = 1, 2, 4, p^{k}

, or

2 p^{k}

, where

p

is an odd prime and

k \geq 1

Definition 21 (Discrete logarithm).

When

g

is a primitive root modulo

m

, the integer

x

satisfying

g^{x} \equiv a (mod m)

is called the discrete logarithm of

a

to the base

g

, written

ind_{g} a

Theorem 22 (Number of primitive roots).

When a primitive root modulo

m

exists, the total number of primitive roots modulo

m

φ (φ (m))

Key algorithms:

Baby-step giant-step: solves the discrete logarithm problem $g^{x} \equiv a (mod p)$ in $O (p)$ time and space.

For more details:

https://interconnectd.app/articles/cg1LJsuTDD1fAw6DMD4H

7. The Chinese Remainder Theorem and Applications

Theorem 23 (Chinese remainder theorem (CRT)).

m_{1}, m_{2}, \dots, m_{k}

are pairwise coprime (

g cd (m_{i}, m_{j}) = 1

for

i \neq = j

), then the system of simultaneous congruences

x \equiv a_{1} (mod m_{1}), x \equiv a_{2} (mod m_{2}), \dots, x \equiv a_{k} (mod m_{k})

has a unique solution modulo

M = m_{1} m_{2} \dots m_{k}

Theorem 24 (Ring isomorphism).

When

g cd (m_{i}, m_{j}) = 1

for all

i \neq = j

, there is a ring isomorphism

Z / M Z ≅ Z / m_{1} Z \times Z / m_{2} Z \times \dots \times Z / m_{k} Z

Key algorithms:

Constructive CRT: setting $M_{i} = M / m_{i}$ , the solution is $x \equiv \sum_{i = 1}^{k} a_{i} M_{i} (M_{i}^{- 1} mod m_{i}) (mod M)$ in $O (k lo g M)$ time.
Garner's algorithm: applies the CRT incrementally, avoiding overflow for large $M$ , in $O (k^{2})$ time.

For more details:

https://interconnectd.app/articles/cdLXHKAHUWG27KrVJ2wO

8. Quadratic Residues and Reciprocity

Definition 25 (Quadratic residue).

Let

p

be an odd prime. If

g cd (a, p) = 1

and the congruence

x^{2} \equiv a (mod p)

has a solution, then

a

is called a quadratic residue modulo

p

; otherwise,

a

is a quadratic nonresidue.

Definition 26 (Legendre symbol).

(\frac{a}{p}) = ⎩ ⎨ ⎧ 1 - 1 0 if a is a quadratic residue modulo p if a is a quadratic nonresidue modulo p if p ∣ a

Theorem 27 (Euler's criterion).

(\frac{a}{p}) \equiv a^{(p - 1) /2} (mod p)

Theorem 28 (Law of quadratic reciprocity (Gauss)).

For distinct odd primes

p

and

q

(\frac{p}{q}) (\frac{q}{p}) = (- 1)^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}}

Theorem 29 (First and second supplements).

(\frac{- 1}{p}) = (- 1)^{(p - 1) /2}, (\frac{2}{p}) = (- 1)^{(p^{2} - 1) /8}

Key algorithms:

Tonelli–Shanks algorithm: finds a solution to $x^{2} \equiv a (mod p)$ in $O (lo g^{2} p)$ time.

For more details:

https://interconnectd.app/articles/iVThwiqRtPK0X11EGjo5

9. Arithmetic Functions and Multiplicativity

Definition 30 (Arithmetic function).

A complex-valued function

f : Z_{> 0} \to C

defined on the positive integers is called an arithmetic function.

Definition 31 (Multiplicative function).

An arithmetic function

f

with

f (1) = 1

is called multiplicative if

f (mn) = f (m) f (n)

whenever

g cd (m, n) = 1

. It is called completely multiplicative if

f (mn) = f (m) f (n)

for all positive integers

m, n

Definition 32 (Important arithmetic functions).

Euler's totient function $φ (n)$ : the number of integers $k$ with $1 \leq k \leq n$ and $g cd (k, n) = 1$ .
Divisor function $σ_{k} (n) = \sum_{d ∣ n} d^{k}$ . In particular, $σ_{0} (n) = d (n)$ counts the number of divisors and $σ_{1} (n) = σ (n)$ gives the sum of divisors.
Möbius function $μ (n)$ : equals $1$ if $n = 1$ ; equals $(- 1)^{k}$ if $n$ is a product of $k$ distinct primes; equals $0$ otherwise (i.e., if $n$ has a squared prime factor).

Theorem 33 (Möbius inversion formula).

F (n) = \sum_{d ∣ n} f (d)

, then

f (n) = \sum_{d ∣ n} μ (n / d) F (d)

Definition 34 (Dirichlet convolution).

The Dirichlet convolution of two arithmetic functions

f

and

g

is defined by

(f * g) (n) = \sum_{d ∣ n} f (d) g (n / d)

. The Dirichlet convolution of two multiplicative functions is again multiplicative.

Key algorithms:

Computing $φ (n)$ : from the prime factorization, $φ (n) = n \prod_{p ∣ n} (1 - 1/ p)$ in $O (n)$ time.
Sieve-based batch computation: computes $φ (k)$ and $μ (k)$ for all $k \leq n$ in $O (n lo g lo g n)$ time.

For more details:

https://interconnectd.app/articles/2mHIeAkwmeJTGTXDnEuS

10. Continued Fractions and Diophantine Approximation

Definition 35 (Continued fraction expansion).

The (regular) continued fraction expansion of a real number

α

is a representation of the form

α = a_{0} + \frac{1}{a _{1} + \frac{1}{a _{2} + \frac{1}{⋱}}} = [a_{0}; a_{1}, a_{2}, \dots]

where

a_{0} \in Z

and

a_{i} \in Z_{> 0}

for

i \geq 1

. The expansion is finite if and only if

α

is rational.

Definition 36 (Convergents).

The rational number

[a_{0}; a_{1}, \dots, a_{n}] = p_{n} / q_{n}

is called the

n

-th convergent of

α

. The numerators and denominators satisfy the recurrence

p_{n} = a_{n} p_{n - 1} + p_{n - 2}, q_{n} = a_{n} q_{n - 1} + q_{n - 2} .

Theorem 37 (Best rational approximation).

The convergent

p_{n} / q_{n}

is the best rational approximation to

α

among all fractions whose denominator does not exceed

q_{n}

Theorem 38 (Lagrange's theorem).

A real number

α

is a quadratic irrational if and only if its continued fraction expansion is eventually periodic.

Theorem 39 (Pell's equation).

D

is a positive integer that is not a perfect square, the positive integer solutions of

x^{2} - D y^{2} = 1

can be obtained from the convergents of the continued fraction expansion of

D

For more details:

https://interconnectd.app/articles/JcTNQc7t9vXwAR9kqyOP

11. The Distribution of Primes

Definition 40 (Prime-counting function).

π (x) = # {p \leq x ∣ p is prime}

is called the prime-counting function.

Theorem 41 (Prime number theorem).

π (x) \sim \frac{x}{ln x} (x \to \infty)

That is,

lim_{x \to \infty} \frac{π ( x )}{x / l n x} = 1

Definition 42 (Chebyshev functions).

The Chebyshev functions are defined by

θ (x) = \sum_{p \leq x} ln p

and

ψ (x) = \sum_{p^{k} \leq x} ln p

Theorem 43 (Chebyshev's theorem).

There exist positive constants

c_{1}

and

c_{2}

such that, for all sufficiently large

x

c_{1} \frac{x}{ln x} \leq π (x) \leq c_{2} \frac{x}{ln x}

Theorem 44 (Dirichlet's theorem on primes in arithmetic progressions).

g cd (a, m) = 1

, then the arithmetic progression

a, a + m, a + 2 m, \dots

contains infinitely many primes.

Remark 45.

The Riemann hypothesis asserts that all nontrivial zeros of the Riemann zeta function

ζ (s) = \sum_{n = 1}^{\infty} n^{- s}

lie on the critical line

Re (s) = 1/2

. This remains one of the most important open problems in mathematics, intimately connected to the precise distribution of primes.

For more details:

https://interconnectd.app/articles/HIdN0m82xGJIRw6fKrx6

12. $p$ -adic Valuations and Local Methods

Definition 46 (

p

-adic valuation).

For a prime

p

and a nonzero integer

n

, the $p$ -adic valuation

v_{p} (n)

is the largest power of

p

dividing

n

. By convention,

v_{p} (0) = + \infty

Definition 47 (

p

-adic absolute value).

The $p$ -adic absolute value is defined by

∣ n ∣_{p} = p^{- v_{p} (n)}

for

n \neq = 0

, and

∣0 ∣_{p} = 0

Theorem 48 (Properties of the

p

-adic valuation).

$v_{p} (ab) = v_{p} (a) + v_{p} (b)$ .
$v_{p} (a + b) \geq min (v_{p} (a), v_{p} (b))$ (corresponding to the ultrametric inequality).
Equality condition: when $v_{p} (a) \neq = v_{p} (b)$ , $v_{p} (a + b) = min (v_{p} (a), v_{p} (b))$ .

Definition 49 (Ring of

p

-adic integers and the field of

p

-adic numbers).

The completion of

Q

with respect to the

p

-adic absolute value is the field of $p$ -adic numbers

Q_{p}

. The subring

Z_{p} = {x \in Q_{p} ∣ ∣ x ∣_{p} \leq 1}

is the ring of $p$ -adic integers.

Theorem 50 (Hensel's lemma).

Let

f (x) \in Z_{p} [x]

. If

f (a) \equiv 0 (mod p)

and

f^{'} (a) \neq \equiv 0 (mod p)

, then there exists

α \in Z_{p}

with

f (α) = 0

and

α \equiv a (mod p)

Theorem 51 (Connection with the Legendre symbol).

For an odd prime

p

with

g cd (a, p) = 1

, the congruence

x^{2} \equiv a (mod p)

has a solution if and only if

x^{2} = a

has a solution in

Q_{p}

(by lifting via Hensel's lemma).

For more details:

https://interconnectd.app/articles/ZA2dCEwFwQE9nq5a2lm6

13. Introduction to Algebraic Integers

Definition 52 (Algebraic integer).

An element

α \in C

is called an algebraic integer if it is a root of a monic polynomial with integer coefficients. The set of all algebraic integers forms a ring.

Definition 53 (Number field and ring of integers).

A finite extension

K

Q

is called a number field (or algebraic number field). The set of elements of

K

that are algebraic integers is denoted

O_{K}

and called the ring of integers of

K

Example 54 (Quadratic fields).

For

K = Q (d)

, where

d

is a squarefree integer,

O_{K} = {Z [d] Z [\frac{1 + d}{2}] if d \equiv 2, 3 (mod 4) if d \equiv 1 (mod 4)

Definition 55 (Ideal).

An ideal

a

O_{K}

is an additive subgroup satisfying

O_{K} \cdot a \subseteq a

Theorem 56 (Unique factorization of ideals).

Every nonzero ideal of

O_{K}

factors uniquely (up to order) as a product of prime ideals:

a = p_{1}^{e_{1}} p_{2}^{e_{2}} \dots p_{r}^{e_{r}}

This is a fundamental property of Dedekind domains.

Definition 57 (Class number).

The class number

h_{K}

is the order of the ideal class group

Cl (O_{K})

(the group of equivalence classes of fractional ideals). We have

h_{K} = 1

if and only if

O_{K}

is a unique factorization domain (UFD).

Theorem 58 (Minkowski's bound).

Every ideal class contains an ideal whose norm does not exceed the Minkowski bound:

M_{K} = \frac{n !}{n ^{n}} (\frac{4}{π})^{r_{2}} ∣ Δ_{K} ∣

where

n = [K : Q]

r_{2}

is the number of pairs of complex embeddings, and

Δ_{K}

is the discriminant.

For more details:

https://interconnectd.app/articles/GBReud95ZKuEOOK2VgnD

14. Theorem and Algorithm Directory

A one-line summary of the major theorems and algorithms encountered in undergraduate number theory and competitive programming.

Fundamental theorems:

Division algorithm: $a = b q + r$ with $0 \leq r < b$ , uniquely determined.
Fundamental theorem of arithmetic: every positive integer factors uniquely into primes.
Bézout's identity: there exist integers $x, y$ with $g cd (a, b) = a x + b y$ .
Fermat's little theorem: $p ∤ a \Rightarrow a^{p - 1} \equiv 1 (mod p)$ .
Euler's theorem: $g cd (a, m) = 1 \Rightarrow a^{φ (m)} \equiv 1 (mod m)$ .
Wilson's theorem: $p$ is prime $⟺ (p - 1)! \equiv - 1 (mod p)$ .
Chinese remainder theorem: a system of congruences with pairwise coprime moduli has a unique solution.
Existence of primitive roots: primitive roots exist modulo $m$ if and only if $m = 1, 2, 4, p^{k}, 2 p^{k}$ .
Law of quadratic reciprocity: $(\frac{p}{q}) (\frac{q}{p}) = (- 1)^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}}$ .
Möbius inversion formula: $F = f * 1 \Rightarrow f = F * μ$ .
Prime number theorem: $π (x) \sim x / ln x$ .
Dirichlet's theorem: if $g cd (a, m) = 1$ , then $a + km$ is prime for infinitely many $k$ .

Algebraic structure theorems:

CRT ring isomorphism: $Z / M Z ≅ \prod Z / m_{i} Z$ .
Hensel's lemma: a simple root modulo $p$ lifts to a root in $Z_{p}$ .
Unique factorization of ideals: prime ideal factorization is unique in Dedekind domains.
Lagrange's theorem (continued fractions): quadratic irrationals have eventually periodic continued fractions.

Key algorithms:

Euclidean algorithm (GCD): $O (lo g (min (a, b)))$
Extended Euclidean algorithm (GCD + Bézout coefficients): $O (lo g (min (a, b)))$
Sieve of Eratosthenes (prime enumeration): $O (n lo g lo g n)$
Trial division (prime factorization): $O (n)$
Miller–Rabin (primality testing): $O (k lo g^{2} n)$
Repeated squaring (modular exponentiation): $O (lo g n)$
Constructive CRT: $O (k lo g M)$
Garner's algorithm (CRT): $O (k^{2})$
Baby-step giant-step (discrete logarithm): $O (p)$
Tonelli–Shanks (square root $mod p$ ): $O (lo g^{2} p)$
Computing $φ (n)$ (via prime factorization): $O (n)$

Number Theory Algebra Summary Theorem Reference Algorithms Competitive Programming

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

1. Introduction: How to Use This Article

2. Divisibility and Congruences

3. The Greatest Common Divisor and the Euclidean Algorithm

4. Primes and the Fundamental Theorem of Arithmetic

5. Applications of Congruences and the Group Structure of Residue Classes

6. Primitive Roots and Discrete Logarithms

7. The Chinese Remainder Theorem and Applications

8. Quadratic Residues and Reciprocity

9. Arithmetic Functions and Multiplicativity

10. Continued Fractions and Diophantine Approximation

11. The Distribution of Primes

12. p-adic Valuations and Local Methods

13. Introduction to Algebraic Integers

14. Theorem and Algorithm Directory

Share your expertise with the world

More from Folio Official

Combinatorics: A Complete Summary of Definitions, Theorems, and Proofs

Continued Fractions and Diophantine Approximation — The Theory of Rational Approximation

Primes and the Fundamental Theorem of Arithmetic — The Atomic Decomposition of Integers

Introduction to Algebraic Integers — Extending the Notion of Integer

1. Introduction: How to Use This Article

2. Divisibility and Congruences

3. The Greatest Common Divisor and the Euclidean Algorithm

4. Primes and the Fundamental Theorem of Arithmetic

5. Applications of Congruences and the Group Structure of Residue Classes

6. Primitive Roots and Discrete Logarithms

7. The Chinese Remainder Theorem and Applications

8. Quadratic Residues and Reciprocity

9. Arithmetic Functions and Multiplicativity

10. Continued Fractions and Diophantine Approximation

11. The Distribution of Primes

12. p-adic Valuations and Local Methods

13. Introduction to Algebraic Integers

14. Theorem and Algorithm Directory

Share your expertise with the world

More from Folio Official

Combinatorics: A Complete Summary of Definitions, Theorems, and Proofs

Continued Fractions and Diophantine Approximation — The Theory of Rational Approximation

Primes and the Fundamental Theorem of Arithmetic — The Atomic Decomposition of Integers

Introduction to Algebraic Integers — Extending the Notion of Integer

12. $p$ -adic Valuations and Local Methods

12. $p$ -adic Valuations and Local Methods