MAT 3343, APPLIED ALGEBRA, FALL 2003

Handout 2: Ideals of Integers

(Supplement to Chapter 1.2)

Peter Selinger

1 Ideals of Integers

Recall that ℤ = {0, −1, 1, −2, 2, −3, 3, …} is the set of integers. If n ∈ ℤ is any integer, we write nℤ for the set

nℤ = {nx | x ∈ ℤ}.

So for example, 2ℤ is the set of even numbers, 3ℤ is the set of multiples of 3, and 0ℤ is the one-element set {0}. Notice that a ∈ nℤ if and only if n divides a. In particular, we have n ∈ nℤ and 0 ∈ nℤ, for all n. Remark 1.1. If nℤ = mℤ, then n = m or n = −m. To prove this, first notice that in this situation, n ∈ mℤ and m ∈ nℤ. Thus m|n and n|m. This implies that n = m or n = −m.

Notice that, as shown in examples in class, the intersection of two sets nℤ and mℤ is again of the form kℤ, for some k. For example:

\begin{aligned}4ℤ ∩ 6ℤ & = & 12ℤ \\ 4ℤ ∩ 5ℤ & = & 20ℤ \\ 0ℤ ∩ 5ℤ & = & 0ℤ. \end{aligned}

Also, if A and B are sets of integers, let us write A + B for the set

A + B = {a + b | a ∈ A and b ∈ B}.

So, for example, 4ℤ + 6ℤ is the set of all integers of the form 4x + 6y, where x, y ∈ ℤ. This happens to cover precisely the even integers, so we find that 4ℤ + 6ℤ = 2ℤ. Again, trying different examples, we find that the sum of two sets nℤ and mℤ always seems to be of the form dℤ, for some integer d. For example:

\begin{aligned}4ℤ + 6ℤ & = & 2ℤ \\ 4ℤ + 5ℤ & = & 1ℤ \\ 0ℤ + 5ℤ & = & 5ℤ. \end{aligned}

Our goal is to show that this always works. It will be useful to characterize the sets of the form nℤ a little more abstractly.

Definition. A subset I ⊆ ℤ is called an ideal if it satisfies the following three conditions:

(1) If a, b ∈ I, then a + b ∈ I.

(2) If a ∈ I and k ∈ ℤ, then ak ∈ I.

(3) 0 ∈ I.

The point is that, as we will show now, the ideals in ℤ are exactly the subsets of the form nℤ. In other words, the sets of the form nℤ are characterized by the three properties (1)–(3) in the definition. This is proved by the combination of Lemmas 1.2 and 1.3 below.

Lemma 1.2. Any set of the form nℤ is an ideal.

Proof. Let I = nℤ. We have to show I satisfies the three properties in the definition of an ideal.

(1) Take arbitrary elements a, b ∈ I. We have to show that a + b ∈ I. Because a ∈ nℤ, we know that a = nx for some x ∈ ℤ. Because b ∈ nℤ, we know that b = ny for some y ∈ ℤ. Then a + b = nx + ny = n(x + y) ∈ nℤ = I.

(2) Take arbitrary elements a ∈ I and k ∈ ℤ. We have to show that ak ∈ I. But a ∈ nℤ, hence we know that a = nx for some x ∈ ℤ. It follows that ak = (nx)k = n(xk) ∈ nℤ = I.

(3) We have to show that 0 ∈ I. But clearly, 0 = 0n, so it follows that 0 ∈ nℤ = I. □

Lemma 1.3. Any ideal I of integers is of the form nℤ, for some n ∈ ℤ.

The idea of the proof is simple: let n be the smallest positive element in I, and then prove (using the three properties of I) that I = nℤ.

The reason the real proof is a bit longer is that we have to worry about a number of details: for instance, we have to worry about what happens if there are no positive elements in I (in this case we can’t let n be such an element!).

The proof makes use of the following principle, which says that if there is a positive integer with a certain property, then there is a smallest such integer.

Principle 1.4 (Well-foundedness principle). If A is a non-empty set of positive integers, then A has a smallest element.

Proof of Lemma 1.3: We know, from property (3), that 0 ∈ I. In case I = {0}, we are done, because I = 0ℤ is of the desired form. Otherwise, there must be some non-zero element k ∈ I. Let A = {x ∈ I | x > 0}. Note that A is nonempty, because from property (2), −k ∈ I, and hence either k or −k is in A. By the well-foundedness principle, A has a smallest element. Let n be the smallest element in A.

Next, we want to show that I = nℤ. We do this by first showing than nℤ ⊆ I, then that I ⊆ nℤ.

To show that nℤ ⊆ I, take an arbitrary element a ∈ nℤ. By definition of nℤ, we know that a = nx, for some x ∈ ℤ. Then from n ∈ I and x ∈ ℤ, it follows by property (2) that nx ∈ I, thus a ∈ I. Since a was arbitrary, this shows that nℤ ⊆ I.

To show that I ⊆ nℤ, we use the method of contradiction. Thus, assume that I ⊈ nℤ. Then there exists some k ∈ I such that k ∉ nℤ. Note that k ∉ nℤ implies k ≠ 0. Let B = {x ∈ I | x > 0 and x ∉ nℤ}. From property (2), we know that −k ∈ I and −k ∉ nℤ, so either k ∈ B or −k ∈ B. Thus, B is non-empty, and by the well-foundedness principle, it has a least element, say a.

We distinguish three cases:

Case 1: Suppose a > n. Then a − n is positive. Also, from a ∈ I and n ∈ I, it follows by property (2) that −n ∈ I and by property (1) that a − n ∈ I. Also, since a ∉ nℤ, it follows that a−n ∉ nℤ. So a−n ∈ B, contradicting the fact that a is the smallest element of B.

Case 2: Suppose a = n. This contradicts the fact that a ∉ nℤ.

Case 3: Suppose a < n. But a ∈ I, therefore a ∈ A, contradicting the fact that n was the smallest element in A.

All three cases lead to a contradiction, which implies that our assumption that I ⊈ nℤ was false. Therefore I ⊆ nℤ. Together with nℤ ⊆ I, this implies that I = nℤ, which finishes the proof of the lemma. □

Now that we know that an ideal is exactly the same thing as a set of the form nℤ, we want to show that the intersection of two ideals is again an ideal, and similarly for sums.

Lemma 1.5. (a) If I and J are ideals, then so is I ∩ J.

(b) If I and J are ideals, then so is I + J.

In the following proof, only one of the six cases is given. The remaining cases are left as homework.

Proof. (a) Suppose I and J are ideals. To show that I ∩ J is an ideal, we must show that it satisfies the three properties in the definition of an ideal. We prove each property in turn.

(1) Suppose a, b ∈ I ∩ J. We want to show that a + b ∈ I ∩ J. By assumption, we know that a ∈ I and a ∈ J and b ∈ I and b ∈ J. By property (1) of I, we have a + b ∈ I. By property (1) of J, we have a + b ∈ J. It follows that a + b ∈ I + J.

(2) …

(3) …

(b) Suppose I and J are ideals. We need to show that I + J is an ideal.

(1) …

(2) …

(3) …

We have now proved what we stated in the beginning: any intersection or sum of two sets of the form nℤ and mℤ is again of the form kℤ. We summarize this result in the following theorem:

Theorem 1.6. If n, m ∈ ℤ, then there exist integers k and d such that

\begin{aligned}nℤ ∩ mℤ & = & kℤ, \\ nℤ + mℤ & = & dℤ. \end{aligned}

Proof. By Lemma 1.2, we know that nℤ and mℤ are ideals. By Lemma 1.5, we know that nℤ ∩ mℤ and nℤ + mℤ are also ideals. By Lemma 1.3, we know that they are of the form kℤ and dℤ, respectively. □

Also note that, by Remark 1.1, the numbers k and d in Theorem 1.6 are essentially unique: they are determined up to a sign.

2 Least common multiple, greatest common divisor

Let us compute some instances of Theorem 1.6. We compute k and d for various different values of n and m.

\begin{aligned}4ℤ ∩ 6ℤ & = & 12ℤ \\ 6ℤ ∩ 6ℤ & = & 6ℤ \\ 8ℤ ∩ 5ℤ & = & 40ℤ \\ 9ℤ ∩ 6ℤ & = & 18ℤ \\ 3ℤ ∩ 5ℤ & = & 15ℤ \end{aligned}  \begin{aligned}4ℤ + 6ℤ & = & 2ℤ \\ 6ℤ + 6ℤ & = & 6ℤ \\ 8ℤ + 5ℤ & = & 1ℤ \\ 9ℤ + 6ℤ & = & 3ℤ \\ 3ℤ + 5ℤ & = & 1ℤ \end{aligned}

We observe that the numbers in the first column appear to be greatest common divisors, and the number in the right column appear to be least common multiples.

Definition. A common divisor of two integers n and m is an integer d such that d|n and d|m. Further, d is called a greatest common divisor if, whenever e is another common divisor of n and m, then e|d.

Definition. A common multiple of two integers n and m is an integer k such that n|k and m|k. Further, k is called a least common multiple if, whenever e is another common multiple of n and m, then k|e.

The following lemma shows that the numbers d and k in Theorem 1.6 are indeed a greatest common divisor and a least common multiple.

Lemma 2.1. (a) aℤ ⊆ bℤ if and only if b|a.

(b) If nℤ + mℤ = dℤ, then d is a greatest common divisor of n and m.

(c) If nℤ ∩ mℤ = kℤ, then k is a least common multiple of n and m.

Proof. (a) Exercise.

(b) Suppose that nℤ + mℤ = dℤ. First, we need to show that d is a common divisor of n and m. But we have nℤ ⊆ dℤ and mℤ ⊆ dℤ. It follows from part (a) that d|n and d|m, hence d is a common divisor. Next, we need to show that it is a least common divisor. So suppose that e is another common divisor, i.e., that e|n and e|m. By part (a), we have nℤ ⊆ eℤ and mℤ ⊆ eℤ. Since eℤ is closed under addition, it follows that nℤ+mℤ ⊆ eℤ, and therefore dℤ ⊆ eℤ. Finally, by part (a) again, it follows that e|d. Thus, d is a greatest common divisor.

(c) Suppose that nℤ ∩ mℤ = kℤ. First, we show that k is a common multiple of n and m. But we have kℤ ⊆ nℤ and kℤ ⊆ mℤ. It follows from part (a) that n|k and m|k, so k is a common multiple. Now, suppose that e is another common multiple of n and m. then n|e and m|e. By part (a), we have eℤ ⊆ nℤ and eℤ ⊆ mℤ. It follows from set theory that eℤ ⊆ nℤ ∩ mℤ = kℤ, hence, again by part (a), we have k|e. Thus, k is a least common multiple. □

Corollary 2.2. Any pair of integers n, m have a greatest common divisor and a least common multiple.

Proof. Theorem 1.6 and Lemma 2.1. □

Greatest common divisors and least common multiples are unique up to a sign. For instance, if d and d′ are both greatest common divisors of n and m, then we must have d|d′ and d′|d, which implies d = d′ or d = −d′. When we speak of the greatest common divisor, we always mean the one that is not negative. It is also denoted as gcd(n, m). The situation is similar for least common multiples, and the unique non-negative least common multiple of n and m is often written as lcm(n, m).

Remark. In our definition of the greatest common divisor d of n and m, we have not actually required that d is greater than any other common divisor, but only that it is a multiple of any other common divisor. In this way, we do not have to make special arrangements in the case where n and/or m are 0. For instance, any integer is a common divisor of 0 and 0, but gcd(0, 0) = 0. The name “greatest” common divisor is actually bad terminology, but it is nevertheless standard. A similar remark applies to least common multiples.

Theorem 2.3. If d = gcd(n, m), then there exists integers a and b such that d = an + bm.

Proof. This follows directly from the fact that nℤ + mℤ = dℤ. Namely, we have d ∈ nℤ + mℤ, and thus, d = an + bm, for some a, b ∈ ℤ. □

In general, finding a and b such that d = an + bm is not as easy as it looks. For instance, we have gcd(89, 144) = 1. Therefore, there exist integers a and b such that 89a + 144b. Try to find them yourself! This can be quite a lot of work. We will later learn a method for finding a and b efficiently.

3 Exercises

Problem 1 Finish the proof of Lemma 1.5. Try to imitate the style used in the first part.

Problem 2 Prove that n|m and m|p implies n|p.

Problem 3 Prove Lemma 2.1(a). There are two directions to prove: aℤ ⊆ bℤ ⇒ b|a, and b|a ⇒ aℤ ⊆ bℤ.

Problem 4 Consider Principle 1.4, the well-foundedness principle. It states that any non-empty subset of positive integers has a least element. Answer the following questions. In each case, if the answer is “no”, give a counterexample (i.e., a set which does not have a least element).

(a) Is the principle still true if we drop the word “non-empty”?

(b) Is the principle still true if we drop the word “positive”?

(c) Is the principle still true if we replace the word “integer” by “rational number”?

(d) Is the principle still true if we replace the word “positive” by “non-negative”? Recall that a number x is positive if x > 0, and non-negative if x ⩾ 0.