# Greatest common divisor of algebraic integers

I have several questions concerning some properties of algebraic numbers. The first concerns the folowing statement:

Given algebraic integers $\alpha$ and $\beta$ they have a unique greatest common divisor modulo asociates. ie there is an algebraic integer $\delta$ with $\delta \vert \alpha$ and $\delta \vert \beta$ and such that for any other integer $\gamma$ such that $\gamma \vert \alpha$ and $\gamma \vert \beta$ we also have $\gamma \vert \delta$; any other algebraic integer with the same properties is an associate of $\delta$.

This result has a simple proof using class field theory, ie if $H$ is the Hilbert class field of $\mathbb{Q}[\alpha,\beta]$, then by the principal ideal theorem, the ideal $(\alpha,\beta)$ becomes principal in $H$ say $\alpha {\mathcal O}_H + \beta {\mathcal O}_H = \delta {\mathcal O}_H$.

I have been looking for a simpler proof in several books in the subject, the nearest I found is theorem 98 in Hecke's Lectures ..., but I think it is not enough: it finds an integer $A$ such that the set of multiples of $A$ in $\mathbb Q[\alpha,\beta]$ coincides with the ideal $(\alpha,\beta)$ but it does not follow that the same is true in the bigger field $\mathbb Q[\alpha,\beta,A]$. So my question is:

Is there a proof of the statement not using class field theory?

My "ideal" proof will only use elementary properties of algebraic numbers so the statement could be proved just after the introduction of algebraic integers and units in a classical introduction to the subject, but I fear I'm asking too much.

-
I don't see what your problem with Hecke's proof is; the ideal generated by $\alpha$ and $\beta$ in the extension is $(A)$, and intersecting it with the base field shows that the ideal downstairs consists of all multiples of $A$ lying in $K$. –  Franz Lemmermeyer Feb 17 '11 at 16:41
Maybe it's worth to add that such a $\delta$ needs not exist among the integers of the field $\mathbb{Q}(\alpha, \beta)$. –  Albertas May 29 at 11:12

I give a proof of this result -- actually the stronger result that the GCD of any two algebraic integers may be expressed as a linear combination -- in $\S 23.4$ of these commutative algebra notes.

The required input from algebraic number theory is nontrivial -- namely that the ideal class group of (the ring of integers of) a number field is finite -- but is much less than that of class field theory.

Note though that one could get away with knowing that these ideal class groups are torsion abelian groups, which is, a priori, a more structural and thus possibly easier to prove result. I have been racking my brains trying to come up with a more fundamentally commutative algebraic proof of this fact, thus far without success.

-
Once one has a linear combination which is a common divisor, that is indubitably a greatest common divisor. Is there a reasonable algorithm which will produce such a linear combination? Perhaps one needs to appeal to theory to prove that the algorithm will always succeed. –  Aaron Meyerowitz Feb 17 '11 at 3:57
@Aaron: good question. Off the top of my head, I think I don't know: the proof I give does seem to give an algorithm to produce the GCD but does not seem to give an algorithm to express it as a linear combination of $a$ and $b$. Absent some kind of Euclidean property I can't think of what to do -- and it is not clear to me at the moment that there is some kind of Euclidean property here (the person to ask would be Franz Lemmermeyer). –  Pete L. Clark Feb 17 '11 at 4:10
@Pete, thanks for your answer but the link doesn't work. Can you fix it? –  Esteban Crespi Feb 17 '11 at 6:52
@Esteban: yes, I have done so. (These links may go down every once in a while, but I promise I will notice and rectify the situation within a day at the latest.) –  Pete L. Clark Feb 17 '11 at 6:55

The proofs of the statement more or less all go like this: let $A$ denote the ideal generated by $\alpha$ and $\beta$ in the ring of integers of a number field $K$, and set $A^h = (\mu)$, where the exponent $h$ of the ideal class of $A$ divides the class number of the field $K$. Then $A$ becomes principal in $L = K(\gamma)$ with $\gamma^h = \mu$ since $A {\mathcal O}_L = (\gamma)$.

As for solving the Bezout equation $\alpha \rho + \beta \sigma = \gamma$, dividing through by $\gamma$ shows that we have to solve $\alpha_1 \rho + \beta_1 \sigma = 1$ in ${\mathcal O}_L$. Over the rationals this is done by the Euclidean algorithm, which we do not have in general number fields. One option I can see is the following: factor $\beta_1$ into prime ideals and compute Euler's Phi function $m = \Phi(\beta_1)$; then $\rho = \alpha_1^{m-1}$ has the property that $\alpha_1\rho-1$ is divisibly by $\beta$. To keep the size of $\rho$ under control you can always reduce the coefficients of $\rho$ with respect to an integral basis by $N(\beta)$.

-
A different idea for the equation is as follows: if we already have the relation $a_0\alpha^h+a_1\alpha^{h-1}\beta+\ldots+a_h\beta^h=\mu$ coming from $A^h=(\mu)$, we can simply divide by $\gamma^{h-1}$ to get $\gamma = \alpha(a_0(\frac{\alpha}{\gamma})^{h-1} + a_1(\frac{\alpha}{\gamma})^{h-2}\frac{\beta}{\gamma}+\ldots+a_{h-1}(\frac{\beta}‌​{\gamma})^{h-1}) + \beta(a_n(\frac{\beta}{\gamma})^{h-1})$, where all fractions are algebraic integers in $O_L$. –  Dror Speiser Feb 17 '11 at 19:56
Thank both, my only problem with Hecke's theorem was that he states it for $K$ and not for $L$. I see now that it follows for $L$ very easily with the same argument. I'm acepting Pete's proof as it is esentially identical. –  Esteban Crespi Feb 17 '11 at 20:16