Number Theory Basics

⚡ Key Takeaways

Number theory is the study of the integers $\mathbb{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).

💡 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 $\mathbb{Z}/n\mathbb{Z}$ ).

DefinitionDivisibility

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

1

\quad b = a\,k, \qquad k \in \mathbb{Z}

Derivation hint: This is a definition; the symbol $a\mid b$ asserts existence of the integer quotient $k=b/a$ . If no such integer exists, write $a \nmid b$ . Here $a$ is a divisor (or factor) of $b$ , and $b$ is a multiple of $a$ . Basic properties: $a\mid a$ (reflexive on nonzero $a$ ); if $a\mid b$ and $b\mid c$ then $a\mid c$ (transitive); if $a\mid b$ and $a\mid c$ then $a\mid (mb+nc)$ for all $m,n\in\mathbb{Z}$ (linearity).

DefinitionPrime 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.

TheoremDivision Algorithm

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

2

\quad a = b\,q + r, \qquad 0 \le r < b

Derivation hint: Take $q = \lfloor a/b\rfloor$ , the greatest integer not exceeding $a/b$ ; then $r = a - bq$ automatically satisfies $0\le r<b$ . Uniqueness follows from comparing two such representations.

TheoremFundamental 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:

3

\quad n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}, \qquad p_1 < p_2 < \cdots < p_k,\ \ a_i \ge 1

Derivation hint: Existence is by strong induction (split any composite into smaller factors). Uniqueness rests on Euclid's Lemma: if a prime $p\mid ab$ then $p\mid a$ or $p\mid b$ .

DefinitionGreatest Common Divisor and Bézout's Identity

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

4

\quad \gcd(a,b) = a\,x + b\,y

Derivation hint: $\gcd(a,b)$ is the smallest positive value of the set $\{ax+by : x,y\in\mathbb{Z}\}$ ; minimality plus the division algorithm forces it to divide both $a$ and $b$ . Two integers are coprime (relatively prime) if $\gcd(a,b)=1$ .

DefinitionCongruence Modulo n

For a positive integer $n$ , integers $a$ and $b$ are congruent modulo $n$ , written $a \equiv b \pmod{n}$ , if:

5

\quad n \mid (a - b)

Derivation hint: 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 $\mathbb{Z}$ into $n$ residue classes forming the ring $\mathbb{Z}/n\mathbb{Z}$ .

TheoremFermat's Little Theorem

If $p$ is prime and $\gcd(a,p)=1$ , then:

6

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

Derivation hint: 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$ .

TheoremEuler's Theorem

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

7

\quad \varphi(n) = n \prod_{p \mid n}\left(1 - \frac{1}{p}\right)

Derivation hint: The product runs over distinct primes dividing $n$ ; it follows from $\varphi$ being multiplicative and $\varphi(p^k)=p^k-p^{k-1}$ . The theorem generalizes Fermat's by replacing $p-1$ with $\varphi(n)$ .

TheoremChinese Remainder Theorem

If $n_1, n_2, \dots, n_k$ are pairwise coprime, the system $x \equiv a_i \pmod{n_i}$ has a unique solution modulo the product:

8

\quad x \equiv \sum_{i=1}^{k} a_i\, N_i\, M_i \pmod{N}, \qquad N = \prod_i n_i,\ \ N_i = N/n_i,\ \ M_i \equiv N_i^{-1} \pmod{n_i}

Derivation hint: Each term $a_iN_iM_i$ equals $a_i$ mod $n_i$ (since $N_iM_i\equiv1$ ) and vanishes mod every other $n_j$ (since $n_j\mid N_i$ ). Summing gives the full solution.

ProofEuclid's Theorem: Infinitely Many Primes

We show no finite list of primes is complete. 1. Suppose, for contradiction, that there are only finitely many primes: $p_1, p_2, \dots, p_n$ . 2. Form the integer $N = p_1 p_2 \cdots p_n + 1$ . 3. By the Fundamental Theorem of Arithmetic, $N>1$ has at least one prime divisor $q$ . 4. If $q$ were one of the listed primes $p_i$ , then $q \mid (N - p_1\cdots p_n) = 1$ , which is impossible since no prime divides $1$ . 5. Therefore $q$ is a prime not in our list — contradicting the assumption that the list was complete. 6. Hence the set of primes is infinite. $\blacksquare$

∎

ProofEuclidean Algorithm computes the GCD

The algorithm repeatedly applies the division algorithm to find $\gcd(a,b)$ . 1. Given $a \ge b > 0$ , write $a = bq + r$ with $0 \le r < b$ (equation [2]). 2. Key lemma: $\gcd(a,b) = \gcd(b,r)$ . Proof: any common divisor of $a,b$ divides $r=a-bq$ ; any common divisor of $b,r$ divides $a=bq+r$ . The two pairs share the same divisors, hence the same greatest one. 3. Replace $(a,b)$ by $(b,r)$ and repeat. The remainders strictly decrease: $b > r_1 > r_2 > \cdots \ge 0$ . 4. Since a strictly decreasing sequence of nonnegative integers must terminate, some remainder reaches $0$ . 5. When $r_k = 0$ , we have $\gcd(\dots) = \gcd(r_{k-1}, 0) = r_{k-1}$ , the last nonzero remainder. $\blacksquare$

∎

CF

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\pmod 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 $\pi(x)\approx x/\ln x$ as a teenager.

🧠 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\mid b$ then means $a$ 's coordinates are all $\le 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 \pmod{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$ .

Figure

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

ExampleSolving a Linear Congruence with the Extended Euclidean Algorithm

Given: Solve $17x \equiv 5 \pmod{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 $\gcd(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 \pmod{43}$ , giving $17^{-1} \equiv -5 \equiv 38 \pmod{43}$ .

Step 3 — Multiply both sides by the inverse:

x \equiv 38\cdot 5 = 190 \equiv 190 - 4\cdot 43 = 190 - 172 = 18 \pmod{43}.

Check: $17\cdot 18 = 306 = 7\cdot 43 + 5 = 301 + 5$ , so $17\cdot 18 \equiv 5$ . ✓

\boxed{x \equiv 18 \pmod{43}}

ExampleFast Modular Exponentiation via Fermat's Little Theorem

Given: Compute $7^{222} \bmod 11$ .

Step 1 — Apply Fermat's Little Theorem (equation [6]). Since $11$ is prime and $\gcd(7,11)=1$ :

7^{10} \equiv 1 \pmod{11}.

Step 2 — Reduce the exponent modulo 10:

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

Step 3 — Evaluate the residual power:

7^2 = 49 = 4\cdot 11 + 5 \equiv 5 \pmod{11}.

\boxed{7^{222} \equiv 5 \pmod{11}}

⚠️ Common mistake

"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.

⚠️ Common mistake

" $a \equiv b \pmod n$ lets you always cancel a common factor." Cancellation is only valid when the factor is coprime to the modulus. From $6 \equiv 6 \pmod 4$ , you may not divide by $2$ to conclude $3\equiv 3\pmod 4$ via $\frac{6}{2}\equiv\frac{6}{2}\pmod{\frac42}$ carelessly. The correct rule: if $ca\equiv cb\pmod n$ then $a\equiv b\pmod{n/\gcd(c,n)}$ .

Counterexample

The converse of Fermat's Little Theorem fails. One might hope that $a^{n-1}\equiv 1\pmod n$ for some $a$ guarantees $n$ is prime. But $n = 341 = 11\cdot 31$ is composite, yet $2^{340}\equiv 1 \pmod{341}$ . Such $n$ are called Fermat pseudoprimes (base 2). Worse, Carmichael numbers like $561 = 3\cdot 11\cdot 17$ satisfy $a^{560}\equiv 1\pmod{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.

connection

Number theory sits at a crossroads of mathematics. The ring $\mathbb{Z}/n\mathbb{Z}$ and the group of units $(\mathbb{Z}/n\mathbb{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 $\pi(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.

🔬 Where this appears

⏳ History

- 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

\varphi(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+2d,\dots

with

\gcd(a,d)=1

, launching analytic number theory.

- 1859 — Riemann's eight-page memoir connects

\pi(x)

to the zeros of

\zeta(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.

open-problem

Many of number theory's most natural questions remain open. The Riemann Hypothesis — that all nontrivial zeros of $\zeta(s)$ have real part $\tfrac12$ — 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 $\le 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.

Formal Statement

Why It Holds

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also