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

Question

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<d$ 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.

Answer 1

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

Answer 2

• 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$.

Answer 3

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<n$. 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)$.

Answer 4

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<d$ 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.