1

Having found a gcd, $d=\gcd(a,b)$ of two ring elements, $a$ and $b$, in $\mathbb{Z}[\sqrt{d}]$, what is the process to express the gcd, $d$ as $d=ax+by$, where $x, y$ are also ring elements?

Arturo Magidin
  • 377,499
  • 55
  • 788
  • 1,104
Maths
  • 43
  • 4
  • Euclidean algorithm. But the ring must be an Euclidean ring - division with remainder must exist. – Wuestenfux Jun 01 '19 at 12:36
  • It may be impossible to do. For example, in $\mathbb{Z}[\sqrt{-5}]$, the only common divisors of $2$ and $1+\sqrt{-5}$ are $1$ and $-1$, hence the gcd is $1$, but it cannot be expressed as a linear combination (because the two elements are not relatively prime in the ring of all algebraic integers). – Arturo Magidin Jun 01 '19 at 13:02
  • @Wuestenfux: The expression may exist even if the ring is not Euclidean, though finding it then may prove difficult. E.g., in the ring of all algebraic integers any two elements have a GCD that can be expressed in the for $xa+yb$, but the ring is not Euclidean. – Arturo Magidin Jun 01 '19 at 15:03
  • Thank you. If the ring is a Euclidean ring, what are the general steps to work backwards and write the gcd(a,b) as xa+yb. Thank you for your help in advance. – Maths Jun 01 '19 at 18:14
  • @Maths Generally we can use the [Extended Euclidean Algorithm.](https://math.stackexchange.com/a/85841/242) The method I describe there is especially convenient for hand computation since it propagates the linear relaitons more naturally in the *forward* (vs. *backward*) direction so it less error prone. You can find *many* worked examples in the $142$ threads linked to that question (both for numbers and polynomials). – Bill Dubuque Jun 01 '19 at 19:13

0 Answers0