Number Theory Basics

Take the number 60. You can break it into 2 \times 30, then 2 \times 2 \times 15, then 2 \times 2 \times 3 \times 5. Those four factors — 2, 2, 3, 5 — are all prime, and no matter how you split 60 apart, you always end up with the same primes in the same quantities. Try it: start with 60 = 6 \times 10 = (2 \times 3) \times (2 \times 5) = 2 \times 2 \times 3 \times 5. Same answer. Or 60 = 4 \times 15 = (2 \times 2) \times (3 \times 5) = 2 \times 2 \times 3 \times 5. Same answer again.

This is not a coincidence. It is a theorem — the Fundamental Theorem of Arithmetic — and it says that the primes are the atoms of the integers. Every integer greater than 1 is either prime itself or built from primes in a unique way. The entire subject of number theory grows from this one fact: that the integers have a hidden atomic structure, and that structure is rigid.

Number theory is one of the oldest branches of mathematics. Indian mathematicians — Aryabhata, Brahmagupta, Bhaskara II — studied divisibility, primes, and the relationships between integers centuries before the subject had a formal name. The tools are elementary — you need nothing beyond multiplication, division, and careful reasoning — but the results are deep. Many of the hardest unsolved problems in mathematics are number theory problems stated in language a school student can understand.

This article covers the foundations: divisibility, primes and composites, the Fundamental Theorem, the GCD and LCM (including the Euclidean algorithm for computing them), and co-prime numbers.

Divisibility

The most basic relation in number theory is divisibility. An integer a divides an integer b — written a \mid b — if there exists an integer k such that b = ak. The notation a \mid b is read "a divides b" or "b is divisible by a" or "a is a factor of b" or "b is a multiple of a." All four phrases mean the same thing.

Some examples: 3 \mid 12 because 12 = 3 \times 4. 7 \mid 49 because 49 = 7 \times 7. 5 \nmid 13 because no integer k satisfies 13 = 5k. And 1 \mid n for every integer n, because n = 1 \times n.

Three properties of divisibility that you will use constantly:

• Transitivity. If a \mid b and b \mid c, then a \mid c. Proof: b = ak_1 and c = bk_2, so c = a(k_1 k_2).
• Linearity. If a \mid b and a \mid c, then a \mid (bx + cy) for any integers x, y. Proof: b = ak_1 and c = ak_2, so bx + cy = a(k_1 x + k_2 y).
• Comparison. If a \mid b and b \neq 0, then |a| \leq |b|. This follows because |b| = |a| \cdot |k| \geq |a| \cdot 1 = |a|.

Primes and composites

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 — it has at least one positive divisor other than 1 and n.

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

Notice that 2 is the only even prime. Every other even number is divisible by 2 (and by itself and 1), so it has at least three positive divisors and is therefore composite. Also notice that 1 is neither prime nor composite — by convention, primality starts at 2.

How do you check whether a number is prime? For a number n, you only need to test divisors up to \sqrt{n}. The reason: if n = a \times b with a \leq b, then a \leq \sqrt{n} (because if both a and b exceeded \sqrt{n}, their product would exceed n). So if n has no prime divisor \leq \sqrt{n}, it is prime.

For example, is 97 prime? \sqrt{97} \approx 9.85, so you only need to check the primes up to 9: those are 2, 3, 5, 7. Is 97 divisible by 2? No (it is odd). By 3? 9 + 7 = 16, not divisible by 3. By 5? Does not end in 0 or 5. By 7? 97 = 7 \times 13 + 6, so no. Therefore 97 is prime.

Are there infinitely many primes? Yes. The proof, one of the most elegant in all of mathematics, goes like this. Suppose there are only finitely many primes: p_1, p_2, \dots, p_r. Form N = p_1 \cdot p_2 \cdots p_r + 1. This number N is not divisible by any of p_1, \dots, p_r (dividing by any p_i leaves a remainder of 1). But N > 1, so it must have a prime factor — and that prime factor is none of p_1, \dots, p_r. This contradicts the assumption that the list was complete. Therefore the primes are infinite. (This is a proof by contradiction.)

The Fundamental Theorem of Arithmetic

The theorem has two parts: existence (every integer \geq 2 can be factored into primes) and uniqueness (the factorisation is the only one). Existence is proved by strong induction: if n is prime, it is its own factorisation; if n is composite, n = ab with 2 \leq a, b < n, and both a and b factor into primes by the inductive hypothesis, so n does too. Uniqueness is harder and relies on a key property of primes: if p \mid ab, then p \mid a or p \mid b (or both). This property — called Euclid's lemma — is what separates primes from other numbers and makes the factorisation rigid.

Some prime factorisations:

The number 2310 is special — it is the product of the first five primes, each appearing exactly once. Such numbers are called primorial products.

GCD and LCM

Given two positive integers a and b, their greatest common divisor \gcd(a, b) is the largest positive integer that divides both a and b. Their least common multiple \operatorname{lcm}(a, b) is the smallest positive integer that is a multiple of both a and b.

Using prime factorisations, both are easy to compute. Write:

(where the exponents are \geq 0). Then:

The GCD takes the minimum exponent at each prime (the overlap), and the LCM takes the maximum (the union). A beautiful consequence:

This identity holds for all positive integers a, b, and it follows from \min(x, y) + \max(x, y) = x + y applied to each prime exponent.

The Euclidean algorithm

Factoring large numbers into primes is hard. The Euclidean algorithm computes \gcd(a, b) without factoring — it uses only repeated division with remainder.

The key insight: \gcd(a, b) = \gcd(b, a \bmod b), where a \bmod b is the remainder when a is divided by b. Since the remainder is always smaller than b, the numbers shrink at every step, and the process terminates when the remainder hits 0. At that point, the last non-zero remainder is the GCD.

Example: \gcd(252, 105).

The last non-zero remainder is 21, so \gcd(252, 105) = 21.

Check by factoring: 252 = 2^2 \times 3^2 \times 7 and 105 = 3 \times 5 \times 7. The common primes are 3^1 and 7^1, so \gcd = 3 \times 7 = 21. The algorithm gives the same answer, but it never needed the factorisations.

The Euclidean algorithm is ancient — it appears in Aryabhata's Aryabhatiya (499 CE) in the context of solving linear equations, and the method of successive remainders was well known to Indian mathematicians long before it received its European name.

Co-prime numbers

Two integers a and b are co-prime (also called relatively prime) if \gcd(a, b) = 1 — that is, they share no common factor other than 1.

Examples: 8 and 15 are co-prime (\gcd(8, 15) = 1, since 8 = 2^3 and 15 = 3 \times 5 share no prime factors). 12 and 35 are co-prime (12 = 2^2 \times 3, 35 = 5 \times 7). But 12 and 18 are not co-prime (\gcd(12, 18) = 6).

Co-primality does not require either number to be prime. The numbers 8 and 9 are both composite, but they are co-prime because 8 = 2^3 and 9 = 3^2 share no prime factors.

A key property: if a and b are co-prime and a \mid bc, then a \mid c. This is because the prime factors of a cannot come from b (since a and b share none), so they must all come from c. This property is used constantly in modular arithmetic and throughout number theory.

When you write a fraction \frac{p}{q} in lowest terms, you are requiring \gcd(p, q) = 1 — that is, p and q are co-prime. The irrationality proofs in proof by contradiction rely on this: assuming \sqrt{2} = p/q in lowest terms and then showing \gcd(p, q) \geq 2 produces the contradiction.

Two worked examples

Common confusions

• "1 is a prime number." It is not. By convention, primes must be greater than 1. The reason is not arbitrary: if 1 were prime, the Fundamental Theorem of Arithmetic would lose its uniqueness, because you could always throw in extra factors of 1 (12 = 2^2 \times 3 = 1 \times 2^2 \times 3 = 1 \times 1 \times 2^2 \times 3 \times \dots). Excluding 1 makes the theorem clean.

• "a \mid b means a divided by b." The notation a \mid b means "a divides b" — that is, b is a multiple of a. It does not mean the fraction a/b. The vertical bar is a relation (true or false), not an operation (producing a number).

• "Two numbers are co-prime only if at least one is prime." No — 8 and 9 are both composite, but \gcd(8, 9) = 1, so they are co-prime. Co-primality is about shared factors, not about whether either number is itself prime.

• "The GCD of two numbers can be larger than both." No — the GCD divides both numbers, so it cannot exceed either one. In fact \gcd(a, b) \leq \min(a, b) for positive a, b.

• "LCM is always a \times b." Only when a and b are co-prime. In general, \operatorname{lcm}(a, b) = \frac{a \times b}{\gcd(a, b)}, which is less than a \times b whenever \gcd(a,b) > 1.

• "Every even number greater than 2 is composite." This one is actually true — 2 is the only even prime. But students sometimes confuse this with "every odd number is prime," which is very false (9 = 3 \times 3, 15 = 3 \times 5, 21 = 3 \times 7, etc.).

Going deeper

The distribution of primes

The primes thin out as numbers get larger, but they never stop. The Prime Number Theorem gives a precise estimate: the number of primes up to N, written \pi(N), is approximately N / \ln N for large N. So among the first million integers, roughly 1{,}000{,}000 / \ln(1{,}000{,}000) \approx 72{,}382 are prime. The actual count is 78{,}498 — the approximation is imperfect but captures the right order of magnitude. The theorem says primes become rarer at a rate governed by the natural logarithm.

The Goldbach conjecture

One of the most famous unsolved problems in mathematics: every even integer greater than 2 can be written as the sum of two primes. For example, 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 5 + 7. The conjecture has been verified computationally up to 4 \times 10^{18} (four billion billion), and no one has found a counterexample. But no one has proved it either. It has been open since 1742 — nearly three centuries.

Bezout's identity

The Euclidean algorithm does more than compute the GCD — it can express the GCD as a linear combination of a and b. That is, for any positive integers a, b, there exist integers x, y (possibly negative) such that:

This is Bezout's identity, and the integers x, y can be found by running the Euclidean algorithm backwards (the "extended" Euclidean algorithm). Aryabhata described this technique — which he called kuttaka ("the pulveriser") — for solving indeterminate linear equations, and it remains one of the most useful algorithms in all of number theory.

For example, \gcd(252, 105) = 21, and indeed 21 = 252 \times 1 + 105 \times (-2): check 252 - 210 = 42... let's be more careful. From the algorithm: 42 = 252 - 2 \times 105 and 21 = 105 - 2 \times 42 = 105 - 2(252 - 2 \times 105) = 5 \times 105 - 2 \times 252. So 21 = (-2) \times 252 + 5 \times 105. The GCD is a linear combination of the two original numbers.

Where this leads next

Number theory is the foundation for several important topics ahead.

• Modular Arithmetic — the next chapter, where you study remainders as a number system of their own, with addition and multiplication that "wrap around."
• Mathematical Induction — the proof technique that establishes many number theory results, including the existence part of the Fundamental Theorem.
• Mathematical Proof — Direct Proof — the framework for the divisibility proofs and Euclidean algorithm arguments in this article.
• Number Systems — where the integers \mathbb{Z} sit inside the hierarchy \mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R}, and number theory is the study of \mathbb{Z}'s internal structure.
• Fractions and Decimals — where lowest terms, GCD, and LCM appear in everyday computation with fractions.