Number Theory Basics

Number theory is the study of the integers

Z

and their arithmetic structure: divisibility, primes, congruences, and Diophantine equations. Key result: every integer

> 1

factors uniquely into primes (the Fundamental Theorem of Arithmetic). Applies to: cryptography, coding theory, computer science, and pure mathematics. Origins: Euclid (c. 300 BCE), systematized by Gauss in Disquisitiones Arithmeticae (1801).

Number theory begins with the deceptively simple set $Z = {\dots, - 2, - 1, 0, 1, 2, \dots}$ and asks deep questions about multiplicative and additive structure. At its foundation lie divisibility (when does one integer evenly divide another), prime numbers (the multiplicative atoms), and congruences (arithmetic "modulo $n$ "). It matters because the simplest-stated problems — e.g., "are there infinitely many twin primes?" — can resist solution for centuries, and because modular arithmetic underpins virtually all modern public-key cryptography. A surprising fact: although primes thin out among large integers, they never run out, and Euclid proved this with a one-line argument over two millennia ago.

The Core Insight

The integers form a structure where addition is simple but multiplication is profound. The primes are the indecomposable building blocks under multiplication, and the Fundamental Theorem of Arithmetic says every integer is uniquely assembled from them. Most of elementary number theory flows from two engines: the division algorithm (which controls divisibility and the GCD) and modular arithmetic (which packages divisibility relations into a clean algebraic system $Z / n Z$ ).

Formal Statement

Divisibility

For integers $a, b$ with $a \neq = 0$ , we say $a$ divides $b$ , written $a ∣ b$ , if there exists an integer $k$ such that:

b = a k, k \in Z

⟳This is a definition; the symbol

a ∣ b

asserts existence of the integer quotient

k = b / a

. If no such integer exists, write

a ∤ b

Here $a$ is a divisor (or factor) of $b$ , and $b$ is a multiple of $a$ . Basic properties: $a ∣ a$ (reflexive on nonzero $a$ ); if $a ∣ b$ and $b ∣ c$ then $a ∣ c$ (transitive); if $a ∣ b$ and $a ∣ c$ then $a ∣ (mb + n c)$ for all $m, n \in Z$ (linearity).

Prime and Composite

An integer $p > 1$ is prime if its only positive divisors are $1$ and $p$ . An integer $n > 1$ that is not prime is composite. The number $1$ is a unit and is neither prime nor composite.

Division Algorithm

For any integers $a$ and $b$ with $b > 0$ , there exist unique integers $q$ (quotient) and $r$ (remainder) such that:

a = b q + r, 0 \leq r < b

⟳Take

q = ⌊ a / b ⌋

, the greatest integer not exceeding

a / b

; then

r = a - b q

automatically satisfies

0 \leq r < b

. Uniqueness follows from comparing two such representations.

Fundamental Theorem of Arithmetic

Every integer $n > 1$ can be written as a product of primes, and this representation is unique up to the order of the factors:

n = p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{k}^{a_{k}}, p_{1} < p_{2} < \dots < p_{k}, a_{i} \geq 1

⟳Existence is by strong induction (split any composite into smaller factors). Uniqueness rests on Euclid's Lemma: if a prime

p ∣ ab

then

p ∣ a

p ∣ b

Greatest Common Divisor and Bézout's Identity

The greatest common divisor $g cd (a, b)$ is the largest positive integer dividing both $a$ and $b$ . Bézout's identity states there exist integers $x, y$ with:

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

⟳

g cd (a, b)

is the smallest positive value of the set

{a x + b y : x, y \in Z}

; minimality plus the division algorithm forces it to divide both

a

and

b

Two integers are coprime (relatively prime) if $g cd (a, b) = 1$ .

Congruence Modulo n

For a positive integer $n$ , integers $a$ and $b$ are congruent modulo $n$ , written $a \equiv b (mod n)$ , if:

n ∣ (a - b)

⟳Equivalently,

a

and

b

leave the same remainder when divided by

n

(apply the division algorithm to each).

Congruence is an equivalence relation that respects addition and multiplication, partitioning $Z$ into $n$ residue classes forming the ring $Z / n Z$ .

Fermat's Little Theorem

If $p$ is prime and $g cd (a, p) = 1$ , then:

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

⟳The nonzero residues

{1, 2, \dots, p - 1}

are permuted by multiplication by

a

; multiplying them all together and cancelling the common factor yields

a^{p - 1} \equiv 1

Euler's Theorem

If $g cd (a, n) = 1$ , then $a^{φ (n)} \equiv 1 (mod n)$ , where Euler's totient counts integers in $[1, n]$ coprime to $n$ :

φ (n) = n p ∣ n \prod (1 - \frac{1}{p})

⟳The product runs over distinct primes dividing

n

; it follows from

φ

being multiplicative and

φ (p^{k}) = p^{k} - p^{k - 1}

. The theorem generalizes Fermat's by replacing

p - 1

with

φ (n)

Chinese Remainder Theorem

If $n_{1}, n_{2}, \dots, n_{k}$ are pairwise coprime, the system $x \equiv a_{i} (mod n_{i})$ has a unique solution modulo the product:

x \equiv i = 1 \sum k a_{i} N_{i} M_{i} (mod N), N = i \prod n_{i}, N_{i} = N / n_{i}, M_{i} \equiv N_{i}^{- 1} (mod n_{i})

⟳Each term

a_{i} N_{i} M_{i}

equals

a_{i}

mod

n_{i}

(since

N_{i} M_{i} \equiv 1

) and vanishes mod every other

n_{j}

(since

n_{j} ∣ N_{i}

). Summing gives the full solution.

Why It Holds

Euclid's Theorem: Infinitely Many Primes

We show no finite list of primes is complete.

Suppose, for contradiction, that there are only finitely many primes: $p_{1}, p_{2}, \dots, p_{n}$ .
Form the integer $N = p_{1} p_{2} \dots p_{n} + 1$ .
By the Fundamental Theorem of Arithmetic, $N > 1$ has at least one prime divisor $q$ .
If $q$ were one of the listed primes $p_{i}$ , then $q ∣ (N - p_{1} \dots p_{n}) = 1$ , which is impossible since no prime divides $1$ .
Therefore $q$ is a prime not in our list — contradicting the assumption that the list was complete.
Hence the set of primes is infinite. $■$

Euclidean Algorithm computes the GCD

The algorithm repeatedly applies the division algorithm to find $g cd (a, b)$ .

Given $a \geq b > 0$ , write $a = b q + r$ with $0 \leq r < b$ (equation [2]).
Key lemma: $g cd (a, b) = g cd (b, r)$ . Proof: any common divisor of $a, b$ divides $r = a - b q$ ; any common divisor of $b, r$ divides $a = b q + r$ . The two pairs share the same divisors, hence the same greatest one.
Replace $(a, b)$ by $(b, r)$ and repeat. The remainders strictly decrease: $b > r_{1} > r_{2} > \dots \geq 0$ .
Since a strictly decreasing sequence of nonnegative integers must terminate, some remainder reaches $0$ .
When $r_{k} = 0$ , we have $g cd (\dots) = g cd (r_{k - 1}, 0) = r_{k - 1}$ , the last nonzero remainder. $■$

Carl Friedrich Gauss | 1777–1855

Gauss called mathematics "the queen of the sciences" and number theory "the queen of mathematics." At age 24 he published Disquisitiones Arithmeticae (1801), which introduced the congruence notation $a \equiv b (mod n)$ , systematized modular arithmetic, proved the law of quadratic reciprocity (which he called the aureum theorema, golden theorem, and proved in multiple ways throughout his life), and laid the foundations for algebraic number theory. His insistence on rigorous proof transformed number theory from a collection of clever observations into a coherent discipline. He reputedly remarked that he discovered the prime-counting estimate $π (x) \approx x / ln x$ as a teenager.

Building Intuition

Think of the primes as a periodic table of integers: every number is a unique molecule built from prime atoms. The exponents in the prime factorization [3] are coordinates locating each integer in an infinite-dimensional grid (one axis per prime). Divisibility $a ∣ b$ then means $a$ 's coordinates are all $\leq b$ 's, coordinate-by-coordinate — the GCD takes the minimum exponent in each slot, the LCM takes the maximum. Modular arithmetic, meanwhile, is just clock arithmetic: on a 12-hour clock, $9 + 5 = 2$ because $14 \equiv 2 (mod 12)$ . The Chinese Remainder Theorem says that knowing the time on several coprime clocks (mod 7, mod 11, mod 13) pins down the absolute "time" uniquely up to the product $7 \cdot 11 \cdot 13 = 1001$ .

The sieve of Eratosthenes: composites struck out as multiples of each prime, leaving primes (gold) standing.

Worked Examples

Solving a Linear Congruence with the Extended Euclidean Algorithm

Given: Solve

17 x \equiv 5 (mod 43)

. Step 1 — Find the inverse of 17 mod 43. Apply the Euclidean algorithm:

$43 = 2 \cdot 17 + 9$
$17 = 1 \cdot 9 + 8$
$9 = 1 \cdot 8 + 1$
$8 = 8 \cdot 1 + 0$ , so $g cd (17, 43) = 1$ (an inverse exists).

Step 2 — Back-substitute (Bézout, equation [4]):

$1 = 9 - 1 \cdot 8$
$= 9 - (17 - 9) = 2 \cdot 9 - 17$
$= 2 (43 - 2 \cdot 17) - 17 = 2 \cdot 43 - 5 \cdot 17$ .

So $- 5 \cdot 17 \equiv 1 (mod 43)$ , giving $1 7^{- 1} \equiv - 5 \equiv 38 (mod 43)$ .

Step 3 — Multiply both sides by the inverse:

x \equiv 38 \cdot 5 = 190 \equiv 190 - 4 \cdot 43 = 190 - 172 = 18 (mod 43) .

Check:

17 \cdot 18 = 306 = 7 \cdot 43 + 5 = 301 + 5

, so

17 \cdot 18 \equiv 5

. ✓

x \equiv 18 (mod 43)

Fast Modular Exponentiation via Fermat's Little Theorem

Given: Compute

7^{222} mod 11

. Step 1 — Apply Fermat's Little Theorem (equation [6]). Since

11

is prime and

g cd (7, 11) = 1

7^{10} \equiv 1 (mod 11) .

Step 2 — Reduce the exponent modulo 10:

222 = 22 \cdot 10 + 2, so 7^{222} = (7^{10})^{22} \cdot 7^{2} \equiv 1^{22} \cdot 7^{2} (mod 11) .

Step 3 — Evaluate the residual power:

7^{2} = 49 = 4 \cdot 11 + 5 \equiv 5 (mod 11) .

7^{222} \equiv 5 (mod 11)

Common Misconceptions

"The number 1 is prime." It is not. Declaring

1

prime would destroy the uniqueness in the Fundamental Theorem of Arithmetic ([3]), since you could append any number of factors of

1

(e.g.,

6 = 2 \cdot 3 = 1 \cdot 2 \cdot 3 = 1 \cdot 1 \cdot 2 \cdot 3

). The number

1

is a unit: it has a multiplicative inverse and is excluded from the primes precisely to preserve unique factorization. " $a \equiv b (mod n)$ lets you always cancel a common factor." Cancellation is only valid when the factor is coprime to the modulus. From

6 \equiv 6 (mod 4)

, you may not divide by

2

to conclude

3 \equiv 3 (mod 4)

via

\frac{6}{2} \equiv \frac{6}{2} (mod \frac{4}{2})

carelessly. The correct rule: if

c a \equiv c b (mod n)

then

a \equiv b (mod n / g cd (c, n))

. The converse of Fermat's Little Theorem fails. One might hope that

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

for some

a

guarantees

n

is prime. But

n = 341 = 11 \cdot 31

is composite, yet

2^{340} \equiv 1 (mod 341)

. Such

n

are called Fermat pseudoprimes (base 2). Worse, Carmichael numbers like

561 = 3 \cdot 11 \cdot 17

satisfy

a^{560} \equiv 1 (mod 561)

for every

a

coprime to

561

, fooling the Fermat test for all bases. This is why probabilistic primality tests use the stronger Miller–Rabin criterion.

Connections

Number theory sits at a crossroads of mathematics. The ring $Z / n Z$ and the group of units $(Z / n Z)^{\times}$ are the entry point to Abstract Algebra, where the GCD's Bézout identity reappears as the theory of ideals in Principal Ideal Domains. The distribution of primes, captured by the Prime Number Theorem $π (x) \sim x / ln x$ , links elementary number theory to Complex Analysis through the Riemann zeta function. Quadratic reciprocity opens into Algebraic Number Theory, where unique factorization is recovered for ideals when it fails for elements. Congruences and the Chinese Remainder Theorem are the computational heart of Cryptography and Coding Theory.

Real-World Applications

RSA public-key cryptography — security rests on the difficulty of factoring a product $N = pq$ of two large primes; decryption uses Euler's Theorem ([7]) with exponents reduced mod $φ (N)$ .
Diffie–Hellman key exchange — relies on modular exponentiation ([6]) and the hardness of the discrete logarithm in $(Z / p Z)^{\times}$ .
Error-correcting codes — Reed–Solomon codes (used in CDs, DVDs, QR codes, and deep-space communication) are built over finite fields $F_{q}$ , direct generalizations of $Z / p Z$ .
Hash tables and hashing — modular reduction $h (k) = k mod m$ with prime $m$ distributes keys uniformly and reduces clustering.
Check digits — the ISBN-10 checksum and credit-card Luhn algorithm use congruences mod 11 and mod 10 to detect transcription errors.
Cryptographic random number / primality — the Miller–Rabin test (built on Fermat's Little Theorem) certifies the large primes underlying TLS/HTTPS.
Computer arithmetic — the Chinese Remainder Theorem ([8]) accelerates large-integer multiplication by computing modulo several small coprime moduli in parallel.

Historical Development

c. 1800 BCE — Babylonian tablet Plimpton 322 lists Pythagorean triples, an early Diophantine table.
c. 300 BCE — Euclid's Elements (Books VII–IX) gives the Euclidean algorithm, the proof of infinitely many primes, and the link between primes and perfect numbers.
c. 250 CE — Diophantus of Alexandria writes Arithmetica, founding the study of integer/rational solutions of equations.
1640 — Pierre de Fermat states his "Little Theorem" and his famous "Last Theorem" margin note; corresponds prolifically on number theory.
1736 — Leonhard Euler proves Fermat's Little Theorem and introduces the totient function $φ (n)$ .
1801 — Gauss publishes Disquisitiones Arithmeticae, introducing congruence notation and proving quadratic reciprocity.
1837 — Dirichlet proves infinitely many primes in any arithmetic progression $a, a + d, a + 2 d, \dots$ with $g cd (a, d) = 1$ , launching analytic number theory.
1859 — Riemann's eight-page memoir connects $π (x)$ to the zeros of $ζ (s)$ , posing the Riemann Hypothesis.
1896 — Hadamard and de la Vallée Poussin independently prove the Prime Number Theorem.
1994 — Andrew Wiles proves Fermat's Last Theorem via modularity of elliptic curves, vindicating Fermat's 1637 claim.

Subtleties & Limits

Many of number theory's most natural questions remain open. The Riemann Hypothesis — that all nontrivial zeros of $ζ (s)$ have real part $\frac{1}{2}$ — controls the finest error term in the distribution of primes and is one of the seven Millennium Prize Problems. The Twin Prime Conjecture asserts infinitely many pairs $(p, p + 2)$ of primes; Yitang Zhang (2013) proved bounded gaps occur infinitely often, later sharpened by the Polymath project to gaps of size $\leq 246$ , but the gap of $2$ remains unproven. Goldbach's Conjecture (every even integer $> 2$ is a sum of two primes) is verified to enormous bounds but unproven. The abc conjecture, deciding the structure behind additive-multiplicative interactions, has a disputed claimed proof. These show that the integers, the simplest objects in mathematics, still harbor profound mysteries.