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.
Best Answer
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}$.