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

1. Divisibility and division

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.

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). ∎

If n is not divisible by m, then any attempt to divide n things into m piles will leave some things left over.

The division algorithm yields for integers (which might or might not be natural numbers) n and m≠0 unique integers 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. The number m is called the divisor or (when we are mostly interested in remainders) the modulus.

The quotient is often written as ⌊n/m⌋, the floor of n/m, to make it clear that we want the integer version of the quotient and not some nasty fraction. The remainder is often written as (n mod m), pronounced "the remainder of n modulo m" when paid by the word but usually just "n mod m." Saying that n mod m = 0 is that same as saying that m divides n.

That a unique quotient and remainder exist can be proved any number of ways, e.g. by induction on |n|, but the easiest is probably this method taken from BiggsBook §8.2. Let's assume for the moment that n and m are both non-negative. Consider the set R = { r | r ≥ 0 and there exists some q such that n = qm+r }. Observe that R is non-empty since it contains n. Since this is a nonempty subset of the naturals, it has a least element—call it r. We already have r ≥ 0 by definition, and if r ≮ m we have r = n - qm implies the existence of r' = n-(q+1)m ≥ 0 with n = (q+1)m + r' and thus r is not the minimum (note we need m≠0 here so that r'≠r). So for the minimum r we have 0 ≤ r < m.

Note that this r is unique (since R only has one minimum), but we haven't proved that it's the only element of R less than m (BiggsBook cheats a bit on this point). To do so, consider any r' with r' ≥ r and corresponding quotient q' such that n = qm+r = q'm+r'. Then r' - r = m(q-q'). If q-q' = 0, r' = r and we are happy. If q-q' ≥ 1, then r' - r ≥ m and thus r' ≥ m + r ≥ m.

So far we have only proved the result when n and m are both non-negative. If m is negative, use the existence and uniqueness of q and r such that n = q(-m)+r with 0 ≤ r < -m to get n = (-q)(m) + r with 0 ≤ r < |m|. If n is negative, first compute -n = q'm + r' and then let either (a) q = -q' and r = 0 if r' = 0 or (b) q = -q'-1 and r = m-r' if r' > 0. In the first case we then have n = qm+r = (-q')m + 0 = -(q'm+r') as expected, and in the second we have n = qm+r = (-q'-1)m + (m-r') = -q'm - m + m - r' = -(q'm+r').

Note that quotients of negative numbers always round down. For example, ⌊(-3)/17⌋ = -1 even though -3 is much closer to 0 than -17. This is so that the remainder is always non-negative (14 in this case).

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

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

2.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 n' = 1 and m' = 0.

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

2.2.1. Example

Here's a computation of the gcd of 402 and 176, together with the extra coefficients:

• Finding gcd(402,176)
  • Finding gcd(176,50)
    • Finding gcd(50,26)
      • Finding gcd(26,24)
        • Finding gcd(24,2)
          • Finding gcd(2,0)
          • Base case!
          • Returning 1⋅2 + 0⋅0 = 2
        • Computing m' = a - b⌊n/m⌋ = 1 - 0⋅12 = 1
        • Returning 0⋅24 + 1⋅2 = 2
      • Computing m' = a - b⌊n/m⌋ = 0 - 1⋅1 = -1
      • Returning 1⋅26 + -1⋅24 = 2
    • Computing m' = a - b⌊n/m⌋ = 1 - -1⋅1 = 2
    • Returning -1⋅50 + 2⋅26 = 2
  • Computing m' = a - b⌊n/m⌋ = -1 - 2⋅3 = -7
  • Returning 2⋅176 + -7⋅50 = 2
• Computing m' = a - b⌊n/m⌋ = 2 - -7⋅2 = 16
• Returning -7⋅402 + 16⋅176 = 2

(Code that generated this: euclid.py.)

2.2.2. 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 and 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. ∎

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

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

4. Modular arithmetic and residue classes

From the division algorithm, we have that for each n, m there is a unique remainder r with 0≤r<m and n = qm+r for some q; this unique r is written as (n mod m). Define n ≡_m n' (read "n is congruent to n' mod m") if (n mod m) = (n' mod m) or equivalently if there is some q ∈ ℤ such that n = n' + qm. Because congruence is a relation defined by pulling equality back through a function, it's an equivalence relation (see Relations), and we can partition the integers into equivalence classes (called residue classes, where residue is an old synonym for remainder) [0]_m, [1]_m, [2]_m, ..., [m-1]_m. These equivalence classes ℤ/≡_m form the integers mod m, written as ℤ_m. Usually we will drop the brackets and just write 0, 1, 2, ..., m-1; sometimes a (mod m) will be tacked on the end of any equation we write to remind ourselves that we are working in ℤ_m.

The most well-known instance of ℤ_m is ℤ₂, the integers mod 2: the class [0]₂ is known as the even numbers and the class [1]₂ as the odd numbers.

4.1. Arithmetic on residue classes

We can define arithmetic operations on residue classes in ℤ_m just as we defined arithmetic operations on integers (defined as equivalence classes of pairs of naturals). Given residue classes [x]_m and [y]_m, define [x]_m + [y]_m = [x+y]_m, where the addition in the RHS is the usual integer addition in ℤ. So, for example, in ℤ₂ we have 0+0 = 0, 0+1 = 1, 1+0 = 1, and 1+1 = 0 (since 1+1 = 2 ∈ [0]_m). Note that as with the integers, we must verify that this definition of addition is well-defined: in particular, it doesn't matter which representatives x and y we pick.

Theorem

If x ≡_m x' and y ≡_m y', then x+y ≡_m x'+y'.

Proof

Choose q_x, q_x', r, q_y, q_y' and s such that x = q_xm+r, x' = q_x'm+r, y = q_ym+s, and y'=q_y'm+s. Then x+x' = (q_x+q_y)m+(r+s) and y+y'=(q_x'+q_y')m+(r+s). It follows that (x+y) mod m = (r+s) mod m = (x'+y') mod m and x+y ≡_m x'+y' as claimed. ∎

Similarly, we can define -[x]_m = [-x]_m and [x]_m×[y]_m = [x×y]_m. A similar argument to the proof above shows that these definitions also give well-defined operations on residue classes. All of the usual properties of addition, subtraction, and multiplication are inherited from ℤ: addition and multiplication are commutative and associative, the distributive law applies, etc.

For example, here is an addition table for ℤ₃:

and here is the multiplication table:

It may help to think of 2 as -1; so it's not surprising that 2×2 =4 ≡_m 1 = -1×-1.

Using these tables, we can do arbitrarily horrible calculations in ℤ₃ using the same rules as in ℤ, e.g. 2(1+2)-2 = 2(0)-2 = -2 = 1 (mod 2). Note we tack on the "(mod 2)" at then end so that the reader won't think we've gone nuts.

Comment: the fact that [x]_m + [y]_m = [x+y]_m and [x]_m × [y]_m = [xy]_m for all x and y means that the remainder operation x ↦ x mod m is a homomorphism from ℤ to ℤ_m: it preserves the operations + and × on ℤ. We'll see more examples of homomorphisms between sets with attached operations (called algebras) in AlgebraicStructures.

4.2. Structure of ℤm for composite m: the Chinese Remainder Theorem

The Chinese Remainder Theorem, in the form typically used today, says that if m₁ and m₂ are relatively prime (i.e. gcd(m₁,m₂) = 1), then for each pair of equations n mod m₁ = n₁, n mod m₂ = n₂, there is a unique solution n with 0≤n<m₁m₂. (Chinese Remainder Theorem gives more history of this result.)

Example: let m₁ = 3 and m₂ = 4. Then the integers m from 0 to 11 can be represented as pairs (m₁, m₂) as follows:

Proof: We will prove something stronger and show an isomorphism between ℤ_m and ℤ_m1×ℤ_m2, where ℤ_m1×ℤ_m2 is the set of pairs of elements (x,y) with addition defined by (x,y)+(x',y') = (x+x',y+y') and multiplication by (x,y)(x,y')=(xx',yy'). To go from ℤ_m to ℤ_m1×ℤ_m2, define f(n) = (n mod m₁, n mod m₂). Showing that f is an isomorphism requires showing it preserves addition and multiplication (i.e., that it is a homomorphism: f(a+b) = f(a)+f(b) and f(ab) = f(a)f(b)) and that it is bijective. For addition, observe that if a = k_am₁+a' and b = k_bm₁+b', then a+b mod m = a+b - xm for some x, which equals (k_a+k_b-xm/m₁)m₁+(a'+b')-xm=km₁+(a'+b' mod m) for some k; thus, a+b mod m = (a mod m) + (b mod m) mod m. By symmetry, the same holds if we replace m₁ by m₂. For multiplication, perform the similar calculation ab mod m = ab - xm for some x, which equals (k_am₁+a')(k_bm₁+b')-xm = m₁(k_ak_b+k_ab'+k_ba'-xm/m₁) + a'b' ≡_m1 a'b' (and similarly for m₂).

Now we must show that f is invertible. Let c₁ = m₂(m₂^-1 (mod m₁)) and c₂ = m₁(m₁^-1 (mod m₂)). (The inverses exist because gcd(m₁,m₂)=1.) These coefficients correspond to the pairs (1,0) and (0,1), because c₁ = m₂m₂^-1 = 1 (mod m₁) and c₁ = 0 (mod m₂), and similarly for c₁. So given (n₁,n₂), we can compute n = (n₁c₁+n₂c₂) mod m and have n mod m₁ = n₁*1 + n₂*0 = n₁ and n mod m₂ = n₁*0 + n₂*1 = n₂. We have just shown f is invertible, which implies it is an isomorphism. ∎

4.3. Division in ℤm

One thing we don't get general in ℤ_m is the ability to divide. This is not terribly surprising, since we don't get to divide (without remainders) in ℤ either. But for some values of x and some values of m we can in fact do division: for these x and m there exists a multiplicative inverse x^-1 (mod m) such that xx^-1 = 1 (mod m). We can see the winning x's for ℤ₉ by looking for ones in the multiplication table below:¹

Here we see that 1^-1 = 1, as we'd expect, but that we also have 2^-1 = 5, 4^-1 = 7, 5^-1 = 2, 7^-1 = 4, and 8^-1 = 8. There are no inverses for 0, 3, or 6.

What 1, 2, 4, 5, 7, and 8 have in common is that they are all relatively prime to 9. This is not an accident: when gcd(x,m) = 1 we can use the extended Euclidean algorithm (see NumberTheory) to find x^-1 (mod m). Observe that what we want is some x' such that xx' ≡_m 1, or equivalently such that x'x + qm = 1. But the extended Euclidean algorithm finds such an x' (and q) whenever 1 = gcd(x,m).

If gcd(x,m) ≠ 1, then x has no multiplicative inverse in ℤ_m. The reason is that if some d>1 divides both x and m, it continues to divide xx' and m for any x'≠0. So in particular xx' can't be congruent to 1 mod m since qm+1 and m don't share any common factors for any value of q.

The set of of residue classes [x]_m where gcd(x,m) = 1 is written as ℤ^*_m. For a prime p, ℤ^*_p includes all non-zero elements of ℤ_p, since gcd(x,p) = 1 for any x that is not 0 or a multiple of p.

4.3.1. The size of ℤ*m and Euler's Theorem

The size of ℤ^*_m, or equivalently the number of numbers less than m whose gcd with m is 1, is written φ(m) and is called Euler's totient function or just the totient of m. When p is prime, gcd(n,p) = 1 for all n with 0<n<p, so φ(p) = |ℤ^*_p| = p-1. For a prime power p^k, we similarly have gcd(n,p^k) = 1 unless p|n. There are exactly p^k-1 numbers less than p^k that are divisible by p (they are 0, p, 2p, ... (p^k-1)p), so φ(p^k) = p^k - p^k-1 = p^k-1(p-1). For composite numbers m that are not prime powers, finding the value of φ(m) is more complicated; but we can show using the ChineseRemainderTheorem that in general

One reason φ(m) is important is that it plays a central role in Euler's Theorem, which says that a^φ(m) = 1 (mod m) when gcd(a,m) = 1.

We can prove this using an argument adapted from the proof of BiggsBook Theorem 13.3.2: Let z₁, z₂, ..., z_φ(m) be the elements of ℤ^*_m. For any y ∈ ℤ^*_m, define yℤ^*_m = { yz₁, yz₂, ..., yz_φ(m) }. Since y has a multiplicative inverse mod m, the mapping z ↦ yz (mod m) is a bijection, and so yℤ^*_m = ℤ^*_m (mod m). It follows that ∏_i z_i = ∏_i yz_i = y^φ(m) ∏_i z_i (mod m). But now multiply both sides by (∏_i z_i)^-1 to get 1 = y^φ(m) (mod m) as claimed.

For the special case that m is a prime, Euler's Theorem is known as Fermat's Little Theorem, and says a^p-1 = 1 (mod p) for all primes p and all a such that p∤a.²

Euler's Theorem is popular in cryptography; for example, the RSA encryption system is based on the fact that (x^e)^d = x (mod m) when de = 1 (mod φ(m)). Here x is encrypted by raising it to the e-th power mod m, and decrypted by raising the result to the d-th power. It is widely believed that publishing e and m reveals no useful information about d provided e and m are chosen carefully.

4.4. Group structure of ℤm and ℤ*m

Assumes previous knowledge of GroupTheory.

The set of residue classes [x]_m where gcd(x,m) = 1 form an abelian group (see GroupTheory).

We will now show that ℤ^*_m = { x | 0 < x < m, gcd(x,m) } also forms an abelian group, whose operation is multiplication mod m (i.e. x*y = xy mod m), provided m is at least 2.

To show that ℤ^*_m is an abelian group, we need to show closure, commutativity, associativity, existence of an identity (1), and existence of inverses.

Closure

Let x and y be in ℤ^*_m so that gcd(x,m) = 1 and gcd(y,m) = 1. z = xy mod m = xy - km where k = ⌊xy/m⌋. Let p be any prime factor of m. If p|xy, then p|x or p|y; since x and y have no common factors with m, neither does xy. Subtracting km can't create a common factor with m, so gcd(z,m)=1. We also have 0≤z<m (true of all remainders), and z can't equal zero because gcd(0,m)=m≠0.

Commutativity

Trivial: xy mod m = yx mod m because xy = yx.

Associativity

The only tricky thing here is that taking mods in between multiplications might break associativity. We'll argue though that xyz mod m = (xy mod m) z mod m; by symmetry this will also show xyz mod m = (yz mod m) x mod m = (xy mod m) z mod m. To prove the claim, observe that xy = (xy mod m) + km for some k. Then xyz = (xy mod m) z + kzm, and xyz mod m = (xy mod m) z mod m + (kzm mod m) = (xy mod m) z mod m since kzm mod m = 0.

Identity

1.

Inverses

Let gcd(x,m) = 1. Then the extended Euclidean algorithm returns x',m' such that x'x+m'm=1. So (x'x + m'm) mod m = 1 mod m or x'x mod m = 1. So let x^-1 = x' mod m. We can easily show that x^-1 has gcd(x^-1,m)=1: if p divides m, then xx^-1 = km+1 = kk'p+1 which can't be divisible by p because it has remainder 1 when divided by p. But if p does not divide xx^-1, it can't divided either of x or x^-1, and so x^-1 in particular has no common factors with m.

Note that we could define the additive group ℤ_m as a quotient group of (ℤ,+) by the congruence x~y if x mod m = y mod m. This almost works for ℤ^*_m—but the problem is that ℤ with multiplication is not a group, because it doesn't have inverses. The best that we can do is construct the quotient monoid (ℤ,×)/~, which will contain at least one element with no inverse (0), and possibly many others.

---

CategoryMathNotes