I have a ring $R$ which is known to be a Dedekind domain, but not necessarily a Euclidian domain, and a nonzero ideal generated by one or two elements in this ring. How can I check if this ideal is a prime ideal?
For ideals generated by one element, this is equivalent to being a prime element in the ring. I programmed a clone of the Erathosthenes sieve for my ring, but this only shows me which elements are irreducible, which does not necessarily imply primality.
To be more concrete, my ring $R$ is the ring of integers in an imaginary quadratic number field $\mathbb{Q}(d)$ (for $d$ a negative squarefree integer).
These rings are of the form $R = \mathbb{Z}[\sqrt{-d}]$ or $R = \mathbb{Z}[\frac{1+\sqrt{-d}}{2}]$, depending on $d$. These are Dedekind domains, and every ideal there is generated by either one or two elements.
For some $d$ (like $-1$, $-2$, $-3$), these are Euclidean domains, where I can use the division with remainder to find the greatest common divisor of two numbers, meaning that each ideal is generated by one element.
For others (like $d = -7$), there is no division with remainder, and we can't use the Euclidean algorithm.
But even here it is not yet clear for me: how do I distinguish irreducible from prime elements? The most famous example: for $d = -5$ we have $R = \mathbb{Z}[\sqrt{-5}]$, and the element $2$ is not prime here, since $2 \cdot 3 = 6 = (1+\sqrt{-5})\cdot(1-\sqrt{-5})$ and 2 is not a factor of either term on the right side.
By testing multiples, I can find numbers with different decompositions, and then know that those factors can't be prime. But when can I stop searching, if I don't find any?
In this particular ring, the first elements not yet shown as either units, irreducible-not-prime or composite (after checking all elements until about $\pm 50 \pm 50i$) are $\pm \sqrt{-5}$, $\pm 4 \pm 2\sqrt{-5}$, $\pm 6 \pm \sqrt{-5}$. Could I be sure here that there really are prime?
Another example, $d = -7$, $R = \mathbb{Z}[\frac{1+\sqrt{-7}}{2}] = \mathbb{Z}[X]/(X^2+X+2)$: Here I find lots of irreducible-non-prime elements, and the only small "irreducible and not yet shown as non-prime" are $\pm \frac{1-\sqrt{-7}}{2}$. (The principal ideal generated by these elements look quite same as the one created by $\frac{1+\sqrt{-7}}{2}$, though – I think there is simply a glitch in my program.)
This ring is non-Euclidean, and I suppose most (if not all but the zero ideal) prime ideals are generated by two elements here. If I have a candidate pair of elements, how do I find out if it is really a nonzero prime (= maximal) ideal?
Any ideas here would helpful, since I'm a bit stuck here. (Most literature about computational ideal theory I found only works in polynomial rings over fields (and makes heavy use of this fact), thus it does not really help here.)
(I'm writing a program which should then be able to work on any of these rings $R$ (and any ideals there), thus facts that are only valid in a small number of those rings are less helpful. But feel free to mention them nevertheless, maybe some of them can be generalized.)
Best Answer
$\newcommand{\Z}{\mathbb{Z}}$
This works for principal ideals pretty well, and it was how I was shown to compute the class group. Let me see if I remember this right...
One way is to translate the problem. You are looking to see if the ideal $I$ is prime in an imaginary quadratic ring. For $d \equiv 1,2$ modulo $4$, this is $\frac{\Z[x]}{x^2+d}$; for $d \equiv 3$ modulo $4$, it's $\frac{\Z[x]}{x^2 + x + \frac{d+1}{4}}$.
The ideal $I$ is prime if $R/I$ is an integral domain (no zero divisors). The trick then is to interchange the quotients of the rings. So for example, in $d=5$, say you're checking to see if $I=(2)$ is prime. Then $R=\frac{\Z[x]}{x^2+5}$. Now by interchanging the quotients this is equivalent to seeing whether $(x^2+5)=(x^2+1)$ is prime in $\frac{\Z[x]}{2}$. In this case it is not, since $(x^2+1) = (x+1)^2$. If you translate this back, since $x$ "represents" $\sqrt{-5}$, you get that the ideal $(2) = (1+\sqrt{-5})^2$.