# Proof that every ideal in $\mathbb{Z}$ can be generated be a single integer

I have a problem understanding a proof about ideals, which states that every ideal in the integers can be generated by a single integer. And with that I realized that I also don't really understand ideals in general and the intuition behind them.

So let me start by the definition of an ideal. For $$a, b \in \mathbb{Z}$$, the ideal generated by $$a$$ is the set $$(a) := \{ua : u \in \mathbb{Z}\}$$ while the ideal generated by $$a$$ and $$b$$ is the set $$(a, b) := \{ua + vb : u,v \in \mathbb{Z}\}$$. Here comes my first question: Are those "multiples" of the generators ($$u$$ and $$v$$) all possible integers? Or does this apply only to a specific amount of predefined integers?

And now comes the proof in question. I added the questions in parenthesis where I had problems following:

The lemma states that for $$a, b \in \mathbb{Z}$$ (not both 0), $$\exists d \in \mathbb{Z}: (a,b) = (d)$$. This means in my understanding that every ideal in the integers, no matter how many integers were used to generate it, can be generated only by a single integer.

Proof: The set $$(a,b)$$ must contain some positive numbers (why? The definition of the ideal doesn't state that). By the well-ordering principle, we know that those positive numbers must have a smallest positive number. Let $$d$$ be that number. Because $$d \in (a,b)$$, every multiple of $$d$$ must also be in $$(a,b)$$ (why? Is there any definition or lemma or theorem that states that?). Therefore, we have $$(d) \subseteq (a,b)$$. And now to prove the other side $$\supseteq$$: For any $$c \in (a,b)$$ , $$\exists q,r$$ (are those elements of the integers or of the set $$(a,b)$$? and do any restrictions apply to $$q$$?) where $$0 \leq r < d$$ such that $$c = qd + r$$ (as far as my understanding goes, this comes from the fact that any integer can be divided by another integer yielding a remainder). Since both $$c$$ and $$d$$ are in $$(a,b)$$, so is $$r=c−qd$$ . Since $$0≤r and $$d$$ is (by assumption) the smallest positive element in $$(a, b)$$, we must have $$r = 0$$. Thus $$c = qd ∈ (d)$$ (how did we conclude that last step?).

Thank you for the clarifications.

• Question 1): yes $u$ and $v$ run over all integers. Last question: $0=r=c-qd$ implies $c=qd$ and $qd \in (d)$ by definition of $(d)$. Proof of $r=0$: if $r>0$ then $r \in (a,b)$ and $0 <r<d$ contradicting the fact that $d$ is the smallest positive element of $(a,b)$. Jul 10, 2019 at 9:11
• $ua+vb$ are all multiples of $d=\gcd(a,b)$ Jul 10, 2019 at 10:02

An ideal $$I$$ of $$\Bbb{Z}$$ generated by $$a,b \in \Bbb{Z}$$ consists of all possible integer linear combinations of $$a$$ and $$b$$ (similar to the notion of a span in a vector space). As an example, $$a,b, a+2b, -a+3b, 5a-7b, \ldots \in \langle a,b\rangle$$. Thus, $$\langle a,b\rangle=\{ax+by \, | \, x,y \in \Bbb{Z}\}.$$

Q1). The reason $$\langle a,b\rangle$$ must contain a positive integer (assuming at least one of $$a$$ or $$b$$ is nonzero) is say if $$a\neq 0$$, then either $$a>0$$ or $$a<0$$. If $$a>0$$, then we already have $$a \in \langle a,b\rangle$$, otherwise $$-a \in \langle a,b\rangle$$ will give us a positive element.

Q2). If $$d \in \langle a,b\rangle$$, this means $$\exists x,y \in \Bbb{Z}$$ such that $$d=ax+by$$. Consequently $$nd=a(nx)+b(ny)$$, which is a linear combination of $$a$$ and $$b$$. Thus $$nd \in \langle a,b\rangle$$.

Q3). The division algorithm states that for $$c,d \in \Bbb{Z}$$ with $$d \neq 0$$, $$\exists$$ integers $$q$$ (quotient) and $$r$$ (remainder) such that $$c=dq+r$$ with $$0 \leq r < d$$. There are no other restrictions on $$q$$.

Q4). Since $$r=c-dq$$, we already have $$c,d \in \langle a,b\rangle$$ so by closure under ring operations $$r \in \langle a,b\rangle$$. If $$r>0$$, then we have a positive integer $$r \in \langle a,b\rangle$$ which is smaller than $$d$$. This violates the fact that $$d$$ was the least positive integer in $$\langle a,b\rangle$$. Thus the only possibility is that $$r=0$$. This means $$c=dq+0=dq$$. Since the ideal generated by $$d$$ contains all multiples of $$d$$, therefore $$c \in \langle d \rangle$$. This proves that $$\langle a,b\rangle \subseteq \langle d \rangle$$.

• great and thorough explanation, exactly what I was missing. One last question: Does this apply to all ideals created by more than two integers or only to those created by two integers? Jul 10, 2019 at 11:46
• @MarwanEzzat all ideals. Jul 10, 2019 at 18:04
• @MarwanEzzat Yes, I added an answer that will hopefully shed some conceptual insight on these matters (which, alas, is sorely lacking in many textbook presentations). Jul 10, 2019 at 19:36
• Yes, $$u$$ and $$v$$ are integers.
• No, the assertion “if $$a,b\in\mathbb Z$$, then there is a $$d\in\mathbb Z$$ such that $$(a,b)=(d)$$” does not mean that every ideal in the integers can be generated only by a single integer. It only means that every ideal in $$\mathbb Z$$ generated by two numbers can actually be generated by a single one.
• You know that $$a\in(a,b)$$ and that $$a\neq0$$. But then both $$a$$ and $$-a(=(-1)\times a)$$ belong to $$(a,b)$$ and at least one of them is positive.
• If $$d\in(a,b)$$, then, by the definition of ideal, $$k\times d\in(a,b)$$, for every integer $$k$$.
• Yes, $$q,r\in\mathbb Z$$. You are dealing only with integers here.
• Yes, $$c=dq+r$$ come from the fact that any integer can be divided by another (non-zero) integer yielding a remainder.
• Again, by the definition of ideal, $$k\times d\in(a,b)$$, for every integer $$k$$.
• But could the reasoning of this lemma analogously be applied to ideals created by more than two integers? Jul 10, 2019 at 12:15
• Yes. It applies to any ideal of $\mathbb Z$. Jul 10, 2019 at 12:16

Well, the proof is correct. What are the basic steps?

1. If $$I\ne \{0\}$$ is an ideal of $$\Bbb Z$$ and $$0\ne a\in I$$, then $$-a=(-1)a\in I$$ and so $$I$$ contains a positive integer.

2. By the well-ordering principle, $$I$$ contains a least positive number $$n$$.

3. Each number $$a\in I$$ is a multiple of $$n$$. Indeed, divide $$a$$ into $$n$$ with remainder: $$a=qn+r$$ where $$0\leq r. Then $$r = a-qn = a+(-q)n\in I$$. But $$n$$ is the smallest positive number in $$I$$ and so $$r=0$$. The claim follows.

4. By 3., the ideal $$I$$ equals $$(n)$$.

It seems you may be missing some arithmetical intuition on these ideas so we emphasize that below.

For $$a, b \in \mathbb{Z}$$, the ideal generated by $$a$$ is the set $$(a) := \{ua : u \in \mathbb{Z}\}$$ while the ideal generated by $$a$$ and $$b$$ is the set $$(a, b) := \{ua + vb : u,v \in \mathbb{Z}\}$$. Here comes my first question: Are those "multiples" of the generators ($$u$$ and $$v$$) all possible integers? Or does this apply only to a specific amount of predefined integers?

Yes, it means for all $$\,u,v\in R = \Bbb Z.\,$$ Ideals in $$R$$ generalize the set of all multiples of an element, or all common multiples of a set of elements. Such sets are closed under addition and also under multiplication by all elements of $$R$$, e.g. if $$\,a,b\,$$ are common multiples of $$\,c,d\,$$ then so too are $$\,ua+vb\,$$ for all $$\,u,v\in R.\,$$ In particular, if an ideal $$I$$ contains $$d$$ then it contains all multiples of $$d$$, therefore $$\, d\in I\iff (d)\subseteq I$$. Our goal below is to show that every ideal $$\,I\subseteq Z\,$$ has this form, i.e. it is the set of (common) multiples of a single (vs. multiple) element(s).

We do so by observing that ideals are further closed under remainder (mod), which yields a descent: given $$\,d < c\in I\,$$ if $$\,c\,$$ isn't divisible by $$\,d\,$$ then it leaves a nonzero remainder $$\,c\bmod d = c-qd\in I$$ which is smaller then $$d$$. Iterating this yields a descending sequence of positive elements eventually terminating in the least positive $$d\in I,\,$$ which must divide every $$\,c\in I,\,$$ else $$\,c\bmod d\,$$ would be smaller than $$d$$. Let's consider your questions with these ideas in mind.

The lemma states that for $$a, b \in \mathbb{Z}$$ (not both 0), $$\exists d \in \mathbb{Z}: (a,b) = (d)$$. This means in my understanding that every ideal in the integers, no matter how many integers were used to generate it, can be generated only by a single integer.

The lemma only claims the case for ideals $$\,(a,b)$$, but the proof works for any ideal $$(0)\neq I\subseteq \Bbb Z$$.

Proof: The set $$(a,b)$$ must contain some positive numbers (why? The definition of the ideal doesn't state that).

By hypothesis $$I$$ contains an element $$\,i\neq 0,\,$$ thus $$\,i\,$$ or $$(-1)i\,$$ is positive, and $$(-1)i\in I$$ since $$I$$ contains all multiples of $$\,i$$.

By the well-ordering principle, we know that those positive numbers must have a smallest positive number. Let $$d$$ be that number. Because $$d \in (a,b)$$, every multiple of $$d$$ must also be in $$(a,b)$$ (why? Is there any definition or lemma or theorem that states that?). Therefore, we have $$(d) \subseteq (a,b)$$.

Because, again $$\,d\in I\,\Rightarrow\, (d)\subset I,\,$$ i.e. $$I$$ contains all multiples of $$d$$.

And now to prove the other side $$\supseteq$$: For any $$c \in (a,b)$$ , $$\exists q,r$$ (are those elements of the integers or of the set $$(a,b)$$? and do any restrictions apply to $$q$$?) where $$0 \leq r < d$$ such that $$c = qd + r$$ (as far as my understanding goes, this comes from the fact that any integer can be divided by another integer yielding a remainder).

Yes, we apply the (Euclidean) integer division algorithm to divide $$\,c\,$$ by $$\,d,\,$$ with remainder $$\,r$$.

Since both $$c$$ and $$d$$ are in $$(a,b)$$, so is $$r=c−qd$$ . Since $$0≤r and $$d$$ is (by assumption) the smallest positive element in $$(a, b)$$, we must have $$r = 0$$. Thus $$c = qd ∈ (d)$$ (how did we conclude that last step?).

Since $$\,d\in I\,$$ so it its multiple $$\,-qd,\,$$ so $$\,c\in I\,\Rightarrow\, c-qd\in I\,$$ since ideals are closed under addition.

The remainder $$r < d$$ can't be positive since that contradicts the definition of $$d$$ as the least positive integer in $$I.\,$$ Thus $$\, 0 = r\, [= c-qd\,]\,$$ so $$\,c = qd,\,$$ i.e. every $$\,c\in I\,$$ is a multiple $$\,d,\,$$ so $$\,I\subseteq (d)$$. Combined with above we have $$\,(d)\subseteq I \subseteq (d)\,$$ so $$\,I = (d)$$.

Remark  In fact a nonzero subset of $$\,\Bbb Z\,$$ is an ideal $$\iff I$$ is close under subtraction, and we can use this to simplify the proof, e.g. see here for this viewpoint and further conceptual insight.

• Can you expand on your explanation of the descent? Jul 11, 2019 at 8:09
• @MarwanEzzat The point was to give some intuition behind the method used in the proof. Given any two elements of the ideal, say $\,0< d < c\,$ then if $\,d\,$ doesn't divide $c$ then the remainder $\, c\bmod d\,$ is a smaller nonzero element of the ideal. Iterating this generates a strictly descending sequence of positive ideal elements $\,d_1 > d_2 > d_3 \cdots$. Eventually it must terminate in the case where $\,d_k\,$ divides every element of the ideal so, necessarily, $d_k$ is the least positive element of the ideal. Jul 11, 2019 at 20:33