# Ideal generated by two univariate, coprime, integer polynomials

Let $f(x)$, $g(x)$ be two univariate, coprime, integer polynomials and let $I=\big(f(x),g(x)\big)$ the ideal of $\mathbb{Z}[x]$ generated by $f, g$. Let $I \cap \mathbb{Z}$, that is, the elements of $\mathbb{Z}$ which can be expressed as linear combinations of $f(x), g(x)$ with coefficients in $\mathbb{Z}[x]$. $I \cap \mathbb{Z}$ is clearly an ideal in $\mathbb{Z}$. The following argument shows that, given two coprime integer polynomials $f,g$, the ideal $I \cap \mathbb{Z}$ of $\mathbb{Z}$ has always non zero elements:

If $f,g$ are considered as elements of $\mathbb{Q}[x]$, Bezout's identity tells us that there exists a pair of unique rational polynomials $U(x)$, $V(x)$ with $\deg U<\deg g$, $\deg V<\deg f$ such that $$U(x)f(x)+V(x)g(x)=1$$ Thus, clearing denominators in the above identity, we get that there exists a pair of unique integer polynomials $u(x)$, $v(x)$ with $\deg u<\deg g$, $\deg v<\deg f$ such that $$u(x)f(x)+v(x)g(x)=c$$ where $c$ is the $lcm$ of the denominators of $U,V$ and: $u=cU$, $v=cV$. Thus: $0 \neq c\in I \cap \mathbb{Z}$.

Question $1$: Can we determine a sufficient and necessary condition such that: $\mathbb{Z}\subset I \cap \mathbb{Z}$?

Question $2$: Is there a general method for determining the least positive generator of $I \cap \mathbb{Z}$ ?

References:

P.S.: The second question above, is actually part of the question posted in the first of the references above. However, it is posted here rather as a problem of commutative algebra than a problem of number theory.

• Crossposted from math.SE: math.stackexchange.com/q/1907770/264 Commented Aug 29, 2016 at 20:31
• The answer to question 2 is yes, there is a general method. First, find $c$ as in your post. After passing to the quotient ring, where we mod out by the ideal $(c)$, you are working in a finite ring $(\mathbb{Z}/c\mathbb{Z})[x]/(\overline{f}(x),\overline{g}(x))$. It is then a finite computation to figure out the additive order of $1$ in that ring. Commented Aug 29, 2016 at 20:48
• @Pace Nielsen: thank you for the idea. So, I guess in the example cited in the first reference, $f(x)=2x+1$, $g(x)=2x+17$, it would have been: $\mathbb{Z}_{16}[x]/\big(2x+1\big)$, right? Commented Aug 30, 2016 at 14:32
• @KonKan Yes, and then in that ring we get $1=-2x$, and so $1=(1)^4=(-2x)^4=16x^4=0$ modulo 16. Thus $1$ belongs to your ideal. Commented Aug 30, 2016 at 14:39
• yes I see. But, you mean $1=0$ modulo $16(2x+1)$ right? Thus, the ring $\mathbb{Z}_{16}[x]/\big(2x+1\big)$ is zero, so $(2x+1)=\mathbb{Z}_{16}[x]$. But in the general case, I mean for higher degree polynomials, we should resort to the use of Gröbner basis techniques, shouldn't we? Commented Aug 31, 2016 at 2:21

For question 2, compute a Gröbner basis over $\mathbb{Z}$ for the ideal generated by $f(x)$ and $g(x)$, which gives the required generator. You can do this easily in SageMathCloud (available free to use). The algorithm behind this computation is exactly what you would be doing by hand to find the generator. This also answers question 1, if you allow an algorithm to provide a necessary and sufficient condition.
• thank you very much for the idea. I had this somewhere in the back of my mind but I was hoping to .. avoid it ;) I am not very familiar with Gröbner bases and as far as I remember, the initiall algorithm of Buchberger deals with polynomials over a field. Where can I find smt on how it works in $\mathbb{Z}[x]$? P.S.: thanks for mentioning SageMathCloud. I did not knew it. Commented Aug 31, 2016 at 11:41
• It is a property of Gröbner bases that the contraction of an ideal $I$ to $\mathbb{Z}$ is generated by those elements in the Gröbner basis which are in $\mathbb{Z}$, and this is one of the main features. This becomes clearer in several variables. If you have an ideal $J\subset\mathbb{Z}[x,y,z]$ and you want to compute the contraction ideal $K = J\cap\mathbb{Z}[x,y]$, all you do is compute a Gröbner basis for $J$ using the lex ordering $x<y<z$, and then $K$ is generated by the elements in the Gröbner basis that are polynomials in just $x$ and $y$. See the book by Cox, Little, and O'Shea. Commented Aug 31, 2016 at 22:02
• No, they only consider coefficients in a field, since their main focus is algebraic geometry. In fact, they generally consider algebraically close fields, although the Gröbner basis algorithms don't use this. It's relatively straightforward to adapt these ideas to $\mathbb{Z}$ coefficients, you just have to replace the division algorithm with cancelling leading terms up to the GCD of the leading coefficients. Roughly speaking, $\mathbb{Z}$ and $k[x]$ are UFDs of dimension 1 (both are PIDs), and so $\mathbb{Z}[x]$ and $k[x,y]=k[x][y]$ work roughly the same. [CLO] is an amazing book! Commented Sep 2, 2016 at 2:07