# On proving every ideal of $\mathbb{Z}_n$ is principal

I was working on a problem in Robert Ash's Abstract Algebra, and didn't follow part of the solution. The problem states

Let $R$ be the ring of $\mathbb{Z}_n$ of integers modulo $n$, where $n$ may be prime or composite. Show that every ideal of $R$ is principal.

His provided solutions goes as

Since an ideal $I$ is a finite set in this case, it must have a finite set of generators $x_1,\ldots, x_k$. Let $d$ be the greatest common divisor of the $x_i$. Every element of $I$ is of the form $a_1x_1+\cdots+a_kx_k$, and hence a multiple of $d$. Thus $I\subseteq (d)$. But $d\in I$, because there are integers $a_i$ such that $\sum_{i=1}^k a_ix_i=d$. Consequently, $(d)\subseteq I$.

Why is "there are integers $a_i$ such that $\sum_i a_ix_i=d$ " obvious? I don't see this automatically, and would appreciate an explanation.

Also, does the proof using the division algorithm fall apart here? When solving it without looking at the answer, I said take $n$ to be the least congruence class in an ideal $I$, then for any $m\in I$, $m=qn+r$ for $0\leq r\lt n$, so $m-qn\in I$ as well, so $r\equiv 0$. So $I=(n)$. Does this not work, or did Ash just provide a different proof? Thank you.

-
Dear yunone, Your argument via the division algorith is fine, too. (Incidentally, the proof of the existence of the $a_i$ such that $\sum a_i x_i = d$ uses the division algorith, so the arguments are not so different. Yours is more direct, but Ash's involves some important general concepts, which gives it some merit too.) Regards, – Matt E May 30 '11 at 5:14
Thanks @Matt for your confirmation. – yunone May 30 '11 at 5:19

The existence of these $a_i$ is a slightly more general form of Bezout's identity. We are technically taking representatives $0\leq y_1,\ldots,y_k\leq n-1$ in $\mathbb{Z}$ for the $x_1,\ldots,x_k\in\mathbb{Z}_n$, letting $D=\gcd(y_1,\dots,y_k)$, using Bezout's identity for $\mathbb{Z}$ to show that there are $b_1,\ldots,b_k\in\mathbb{Z}$ such that $\sum_{i=1}^k b_iy_i=D$, then reducing mod $n$ to the equation $\sum_{i=1}^k a_ix_i=d$ where $a_i=b_i+n\mathbb{Z}$ and $d=D+n\mathbb{Z}$.
"Using Bezout's identity for $\bf Z$" is essentially the same as saying $\bf Z$ is a PID, isn't it? – Gerry Myerson May 30 '11 at 5:26
@Gerry, that's true. I felt the connection of yunone's question with the Bezout's identity formulation was slightly clearer, but the statement that $\mathbb{Z}$ is a PID is the ultimately the better, more abstract way of thinking about it. – Zev Chonoles May 30 '11 at 5:34
Presumably Ash has already proved that $\bf Z$ is a PID. Now $d$ is the gcd of the $x_i$ in $\bf Z$, which is a PID, so working in $\bf Z$ we have $\sum_ia_ix_i=d$ for some $a_i$.
Thanks Gerry, but Ash has not actually proven that. I'll take a look for myself in showing that $\mathbb{Z}$ is a PID. – yunone May 30 '11 at 5:08