• NumberTheory

Number theory is the study of the natural numbers, particularly their divisibility properties. Throughout this page, when we say number, we mean an element of N.

A number m divides n, written m|n, if there is some number k such that km=n. In this case m is said to be a factor or divisor of n. A number greater than 1 whose only factors are 1 and itself is called prime. Non-primes that are greater than 1 are called composite. The remaining numbers 0 and 1 are by convention neither prime nor composite; this allows us to avoid writing "except 0 or 1" in a lot of places later.

The DivisionAlgorithm yields for any n and any m≠0 unique numbers q, r such that n = qm+r and 0≤r<m. The number q = ⌊n/m⌋ is called the quotient of n divided by m and r = n mod m is called the remainder of n divided by m. Saying that m|n when n≠0 is the same as saying that n mod m = 0.

Some useful facts about divisibility:

• If d|m and d|n, then d|(m+n). Proof: Let m = ad and n = bd, then (m+n) = (a+b)d.
• If d|n and n≠0, then d ≤ n. Proof: n = kd ≠ 0 implies k ≥ 1 implies n = kd ≥ d.
• d|0 for all d. Proof: 0d = 0.
• If p is prime, then p|ab if an only if p|a or p|b. Proof: follows from the extended Euclidean algorithm (see below).

1. Greatest common divisors

Let m and n be numbers, where at least one of m and n is nonzero, and let k be the largest number for which k|m and k|n. Then k is called the greatest common divisor of m and n, written gcd(m,n) or sometimes just (m,n). A similar concept is the least common multiple lcm(m,n), which is the smallest k such that m|k and n|k. If divisibility is considered as a partial order, the naturals form a lattice (see Relations), which is a partial order in which every pair of elements x and y has both a unique greatest element that is less than or equal to both (the meet x∧y, equal to gcd(x,y) in this case) and a unique smallest element that is greater than or equal to both (the join x∨y, equal to lcm(x,y) in this case). Two numbers m and n whose gcd is 1 are said to be relatively prime or coprime, or simply to have no common factors.

1.1. The Euclidean algorithm for computing gcd(m,n)

Euclid described 23 centuries ago what is now known as the Euclidean_algorithm for computing the gcd of two numbers (his original version was for finding the largest square you could use to tile a given rectangle, but the idea is the same). Euclid's algorithm is based on the recurrence

• gcd(0,n) = n. (This holds because k|0 for all k.)

• gcd(m,n) = gcd(n mod m, m), when m > 0. (If k divides both n and m, then k divides n mod m = n - ⌊n/m⌋m; and conversely if k divides m and n mod m, then k divides n = m + ⌊n/m⌋. So (m,n) and (n mod m, m) have the same set of common factors and the greatest of these is the same.)

The algorithm simply takes the remainder of the larger number by the smaller recursively until it gets a zero, and returns whatever number is left.

1.2. The extended Euclidean algorithm

The Extended_Euclidean_algorithm not only computes gcd(m,n), but also computes integer coefficients m' and n' such that

• m'm + n'n = gcd(m,n).

It has the same structure as the Euclidean algorithm, but keeps track of more information in the recurrence. Specifically:

• For m = 0, gcd(m,n) = n with m' = 0 and n'= 1.

• For m > 0, let r = n mod m and use the algorithm recursively to compute a and b such that ar+bm=gcd(r,m) =gcd(m,n). Substituting r = n - ⌊n/m⌋m gives an - a⌊n/m⌋m + bm = gcd(m,n); this can be rewritten as a⋅n + (b-a⌊n/m⌋)⋅m = gcd(m,n), giving both the gcd and the coefficients n' = a and m' = (b-a⌊n/m⌋).

1.3. Applications

• If gcd(n,m) = 1, then there is a number n' such that nn' + mm' = 1. This number n' is called the multiplicative inverse of n mod m and acts much like 1/n in ModularArithmetic.

• If p is prime p|ab, then either p|a or p|b. Proof: suppose p∤a; since p is prime we have gcd(p,a) = 1. So there exist r and s such that rp+sa=1. Multiply both sides by b to get rpb + sab = b. Observe that p|rpb and p|sab (the latter because p|ab), so p divides their sum and thus p|b.

2. The Fundamental Theorem of Arithmetic

Let n be a number greater than 0. Then there is a unique sequence of primes p₁≤p₂≤...≤p_k such that n = p₁p₂...p_k. This fact is known as the Fundamental Theorem of Arithmetic, and the sequence {p_i} is called the prime factorization of n.

Showing that there is at least one such sequence is an easy induction argument. If n=1, take the empty sequence; by convention, the product of the empty sequence is the multiplicative identity, i.e. 1. If n is prime, take p₁ = n; otherwise, let n = ab where a and b are both greater than 1. Then n = p₁...p_kq₁...q_m where the p_i are the prime factors of a and the q_i are the prime factors of b. Unfortunately, this simple argument does not guarantee uniqueness of the sequence: it may be that there is some n with two or more distinct prime factorizations.

We can show that the prime factorization is unique by an induction argument that uses the fact that p|ab implies p|a or p|b (which we proved using the extended Euclidean algorithm). If n=1, then any non-empty sequence of primes has a product greater than 1; it follows that the empty sequence is the unique factorization of 1. If n is prime, any factorization other than n alone would show that it isn't; this provides a base case of n=2 and n=3 as well as covering larger values of n that are prime. So suppose that n is composite, and that n = p₁...p_k = q₁...q_m, where {p_i} and {q_i} are nondecreasing sequences of primes. Suppose also (by the induction hypothesis) that any n' < n has a unique prime factorization.

If p₁ = q₁, then p₂...p_k = q₂...q_m and so the two sequences are identical by the induction hypothesis. Alternatively, suppose that p₁ < q₁; note that this also implies p₁ < q_i for all i, so that p₁ doesn't appear anywhere in the second factorization of n. But then p∤q₁...q_m = n, a contradiction.

2.1. Applications

Some consequences of unique factorization:

• We can compute gcd(a,b) by factoring both a and b and retaining all the common factors, which is the algorithm favored by grade school teachers who deal with small numbers. Without unique factorization, this wouldn't work: we might get unlucky and factor a or b the wrong way so that the common factors didn't line up. For very large numbers, computing prime factorizations becomes impractical, so Euclid's algorithm is a better choice.

• Similarly, for every a, b, there is a least common multiple lcm(a,b) with the property that a|lcm(a,b), b|lcm(a,b), and for any x with a|x and b|x, lcm(a,b)|x. The least common multiple is obtained by taking the maximum of the exponents on each prime that appears in the factorization of a or b. It can also be found by computing lcm(a,b) = ab/gcd(a,b).

• The natural numbers without zero, partially ordered by divisibility, form a lattice that is isomorphic to the lattice obtained by taking all infinite sequences of natural numbers whose sum is nonzero and finite, and letting x ≤ y if x_i ≤ y_i for all i. The isomorphism maps n to x where x_i is the exponent in the prime factorization of n on the i-th largest of all primes (e.g. 24 = 2³×3¹ → 3,1,0,0,0,...). If we throw in 0, it becomes a new element at the top of the lattice.

3. Modular arithmetic and residue classes

See ModularArithmetic.

CategoryMathNotes