It works with rationals and Gaussian rationals too. In the case of rationals, the integer quotient is an integer and the remainder is a rational. In the case of Gaussian rationals, the Gaussian integer quotient is a Gaussian integer and the remainder is a Gaussian rational. For example: gcd(6/5, 15/17) = 3/85 with: (6/5) / (3/85) = 34 (15/17) / (3/85) = 25 and: gcd((-21/5)+(69/10)*i, (-25/18)+(5/3)*i) = (1/30)+(2/45)*i with: ((-21/5)+(69/10)*i) / ((1/30)+(2/45)*i) = 54+135*i ((-25/18)+(5/3)*i) / ((1/30)+(2/45)*i) = 9+38*i The unique factorization domain property is useful. Prime factorization works for rationals and Gaussian rationals as well. You just end up with negative exponents for some of the prime factors. For example, the prime factorization of: (6/35)+(10/21)*i is: (1+i)^3 * (2+i)^-1 * (1+2*i)^-1 * 3^-1 * 7^-1 * (17+8*i) Tom Gareth McCaughan writes:
On 23/10/2020 04:48, Tom Karzes wrote:
As I mentioned in my earlier mail, the Euclidean algorithm works perfectly well with Gaussian integers, provided you have the proper remainder function. Here's the core of the Python code for my Gaussian GCD method: [etc.]
The way I think it's usually expressed by fancypants algebraists is: a ring (actually, it had better be an integral domain) is "euclidean" if there's a function f mapping its nonzero elements to the non-negative integers (think of this as being like the absolute value) such that for any a,b in the ring either b=0 or else you can write a = qb+r with r=0 or f(r) < f(b).
Then you define "remainder" to be the operation that takes a,b and gives you r (any such r). And then your GCD algorithm repeatedly replaces a,b with b,r until you have b=0.
This works in the ordinary integers, of course. It works in the Gaussian integers, taking f(x) = |x| and (e.g.) picking q = nearest Gaussian integer to a/b. It works in Q[X], the polynomials with rational coefficients, picking f(p) = degree(p). (But not in Z[X], where you can't always reduce the degree that way; consider trying to divide X by 2.)
The theorem beloved of those fancypants algebraists is that if your ring is euclidean then it's a "principal ideal domain", which in turn means that it's a "unique factorization domain", meaning that everything factors essentially-uniquely into irreducibles and units.
-- g