# Number Theory Ideals

Let $n \in \mathbb Z$. In the ring of integers, the ideal $(n, 2n+1)$ is principal. (i.e. $(n, 2n+1) = (d)$ for some integer $d$. What are the possible values for $d$? Prove your solution.

-
$(2n,2n+1)=1\implies (n,2n+1)=1$ – lab bhattacharjee Sep 22 '12 at 18:57

Let $a=n$ and $b=2n+1$. Let $I=(a,b)$ the ideal generated by $a$ and $b$. Then $1=b-2a\in I$, which implies that $I=\mathbb Z=(1)=(-1)$. This means that $d=\pm 1$.

-

There are two results you can use (and they hold for any Principal Ideal Domain):

1. For any pair of integers $a,b\in\mathbb Z$, we have $$(a,b)=(\gcd(a,b)).$$
2. If $(a)=(b)$, then there exists a unit $u$ such that $a=ub$ (for this particular result, all you need is the fact that you are in an integral domain).

Using 1, we see that $(n,2n+1)=(1)=\mathbb Z$, since $\gcd(n,2n+1)=1$. There are several ways to see this. As Baby Dragon mentionned below, if a positive integer $d$ divides both $n$ and $2n+1$, then it divides $-2(n)+1(2n+1)=1$. Therefore, the $\gcd$ is $1$. Also, it is easy to see that $\gcd(2n,2n+1)=1$ (again, the $\gcd$ has to divide $2n+1-2n=1$). On the other hand, if we write $\gcd(n,2n+1)=d$, then $d$ divides $2n$, and so it divides $\gcd(2n,2n+1)=1$. Therefore, $d=1$ (this is what lab bhattacharjee wrote above in the comments).

Finally, since the units of $\mathbb Z$ are $\pm 1$, we know that the only generators are $\pm1$.

-
This helps, but does that fully prove the solution? How would I prove that 1 is the gcd? – Skippydo Sep 22 '12 at 19:41
If $d|n,m$, then $d|k_1n+k_2m$ for all integers, $K_i,i=1,2$. Set $m=2n+1, k_1=-2,k_2=1$. The result when you compute $k_1n+k_2m$ is $1$. Now the largest number that divides 1 is 1. – Baby Dragon Sep 22 '12 at 20:09
@Skippydo I added two proofs of this statement. – M Turgeon Sep 23 '12 at 12:18

Hint $\rm\,\ (\color{#C00}n,\,\color{#0A0}{an\!+\!1})\,\ni\, \color{#0A0}{an\!+\!1} - a\,\color{#C00}n = 1$

Generally $\rm\:(n,k) = (n,\, k\ mod\ n),\$ hence $\rm\:(n,k) = (gcd(n,k)),\:$ which is simply Bezout's Identity expressed in ideal-theoretic language.

Hence $\rm\: (n, f(n))\, =\, (n, f(0))\$ for all polynomials $\rm\ f(x)\in \Bbb Z[x].\:$ Yours is a special case: $\rm\,f\,$ is linear.

Generally, in any ring $\rm\,R\!:\ (a,b) = (c)\:\Rightarrow\: c = gcd(a,b),\$ since $\rm\:(c)\ni a,b\:\Rightarrow\:c\:|\:a,b,\:$ and, conversely, $\rm\:c\in (a,b)\:\Rightarrow\:c = r\,a+s\,b\:$ so $\rm\:d\:|\:a,b\:\Rightarrow\:d\:|\:c.\:$ Thus $\rm\:c = gcd(a,b),\:$ being a common divisor of $\rm\:a,b\:$ divisible by every common divisor $\rm\:d.\:$ For a more conceptual proof, one may apply universal properties of gcds and sums to $\rm\:c\:|\:a,b \iff\rm (c)\supset (a,b).$

The domains $\rm\,R\,$ where the converse holds, i.e. where $\rm\:gcd(a,b)\:$ always exists and it is an $\rm\,R$-linear combination of $\rm\:a,b,\:$ are called Bezout domains, being domains where Bezout's identity holds true. This is equivalent to all two-generated ideals being principal or, equivalently, all finitely generated ideals being principal. This includes all Euclidean domains that, like $\Bbb Z,$ enjoy a Division Algorithm, since the extended Euclidean algorithm yields the Bezout Identity, just like in $\Bbb Z.$

Note that, generally, gcds are defined only up to unit scalings. In general rings there need not be any way to choose a canonical representative (such as in $\Bbb Z,\,$ where we normalize gcds $\ge 0)$.

-
That's somewhat more than a hint, isn't it? – Hurkyl Sep 23 '12 at 17:58