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?

  • $\begingroup$ Euclidean algorithm. But the ring must be an Euclidean ring - division with remainder must exist. $\endgroup$ – Wuestenfux Jun 1 at 12:36
  • $\begingroup$ 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). $\endgroup$ – Arturo Magidin Jun 1 at 13:02
  • $\begingroup$ @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. $\endgroup$ – Arturo Magidin Jun 1 at 15:03
  • $\begingroup$ 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. $\endgroup$ – Maths Jun 1 at 18:14
  • $\begingroup$ @Maths Generally we can use the Extended Euclidean Algorithm. 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). $\endgroup$ – Bill Dubuque Jun 1 at 19:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.