Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 4 down vote accepted

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

share|cite|improve this answer
Thanks Zev, I've seen Bezout's Identity in number theory books, so that makes sense. – yunone May 30 '11 at 5:11
"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$.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.