Mathematics → Number Theory

Number Theory

Number theory studies the integers and their properties — divisibility, primes, and modular arithmetic. Gauss called it "the queen of mathematics," and its applications range from cryptography to coding theory.

Divisibility

Definition — Divisibility

An integer

a

divides

b

, written

a \mid b

, if there exists an integer

k

such that

b = ak

. We say

a

is a divisor (or factor) of

b

3 \mid 12 \quad \text{since} \quad 12 = 3 \cdot 4 \qquad\qquad 5 \nmid 13 \quad \text{since no integer } k \text{ satisfies } 13 = 5k

Division Algorithm

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

a = bq + r

Example: dividing 17 by 5 gives $17 = 5 \cdot 3 + 2$ , so $q=3$ , $r=2$ .

Prime Numbers

Definition — Prime

An integer

p > 1

is prime if its only positive divisors are 1 and

p

itself. An integer

n > 1

that is not prime is composite.

The first few primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, …

There are infinitely many primes — Euclid's proof by contradiction: assume finitely many primes $p_1, p_2, \ldots, p_n$ , then $N = p_1 p_2 \cdots p_n + 1$ is divisible by none of them, contradicting the assumption.

Sieve of Eratosthenes

To find all primes up to $n$ : list integers from 2 to $n$ , then repeatedly cross out multiples of each unmarked number. The survivors are prime. To check primality of $n$ , you only need to test divisors up to $\sqrt{n}$ .

GCD and LCM

Definition — GCD

The greatest common divisor

\gcd(a,b)

is the largest positive integer dividing both

a

and

b

. If

\gcd(a,b) = 1

, the integers are called coprime (or relatively prime).

Definition — LCM

The least common multiple

\text{lcm}(a,b)

is the smallest positive integer divisible by both

a

and

b

GCD and LCM are related by:

\gcd(a,b) \cdot \text{lcm}(a,b) = |a \cdot b|

Example: $\gcd(12,18)=6$ , $\text{lcm}(12,18)=36$ , and $6 \cdot 36 = 216 = 12 \cdot 18$ .

The Euclidean Algorithm

The Euclidean algorithm computes $\gcd(a,b)$ efficiently using repeated division. It relies on the observation:

\gcd(a,b) = \gcd(b,\, a \bmod b)

Applying this repeatedly until the remainder is zero:

\gcd(48, 18) = \gcd(18, 12) = \gcd(12, 6) = \gcd(6, 0) = 6

The algorithm runs in $O(\log \min(a,b))$ steps — extremely efficient even for very large integers. It is the foundation of RSA and other public-key cryptosystems.

Modular Arithmetic

Definition — Congruence

Integers

a

and

b

are congruent modulo

n

, written

a \equiv b \pmod{n}

, if

n \mid (a - b)

17 \equiv 2 \pmod{5} \qquad \text{since } 5 \mid (17 - 2)

Congruence is an equivalence relation. Arithmetic operations respect it:

a \equiv b \pmod{n} \;\text{ and }\; c \equiv d \pmod{n} \;\Rightarrow

a + c \equiv b + d \pmod{n}, \qquad ac \equiv bd \pmod{n}

Modular arithmetic is the mathematics of clocks: on a 12-hour clock, $10 + 5 = 3$ because $15 \equiv 3 \pmod{12}$ .

Fermat's Little Theorem

Theorem — Fermat's Little Theorem

p

is prime and

\gcd(a, p) = 1

, then:

a^{p-1} \equiv 1 \pmod{p}

Equivalently, for any integer

a

a^p \equiv a \pmod{p}

This theorem is the cornerstone of RSA encryption. It also gives a fast way to compute modular inverses: since $a^{p-1} \equiv 1$ , the inverse of $a$ modulo $p$ is $a^{p-2} \bmod p$ .

Example: $p = 7,\ a = 3$ . Then $3^6 = 729 = 7 \cdot 104 + 1$ , so $3^6 \equiv 1 \pmod 7$ . ✓

Fundamental Theorem of Arithmetic

Theorem — Fundamental Theorem of Arithmetic

Every integer

n > 1

can be written as a product of primes in exactly one way, up to ordering:

n = p_1^{e_1}\, p_2^{e_2} \cdots p_k^{e_k}

where

p_1 < p_2 < \cdots < p_k

are primes and

e_i \geq 1

360 = 2^3 \cdot 3^2 \cdot 5^1 \qquad 1001 = 7 \cdot 11 \cdot 13

This uniqueness is what makes primes the "atoms" of number theory. From the prime factorizations of $a$ and $b$ , one can directly read off $\gcd$ and $\text{lcm}$ : take the minimum (or maximum) exponent for each prime.

Next: Calculus →

On this page

Divisibility

Prime Numbers

GCD and LCM

Euclidean Algorithm

Modular Arithmetic

Fermat's Little Theorem

Fundamental Theorem