ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 12 Nov 2018 15:04:31 +0100Making a quotient with Gaussian elementshttps://ask.sagemath.org/question/44251/making-a-quotient-with-gaussian-elements/I want to implement the euclidean algorithm for arbitrary euclidean domains.
In particular, I want it to work with Gaussians.
# Extended Euclides Algorithm
def extended_euclides(a,b):
r0 = a; r1 = b
s0 = 1; s1 = 0
t0 = 0; t1 = 1
while r1 != 0:
q = r0 // r1
r0, r1 = r1, r0 - q * r1
s0, s1 = s1, s0 - q * s1
t0, t1 = t1, t0 - q * t1
return r0, s0, t0
When I run
# Gaussian integers example
ZI = QuadraticField(-1, 'I').ring_of_integers()
a = ZI(-87 + 47*I); b = ZI(-90 + 43*I)
r,s,t = extended_euclides(a,b)
print("The GCD of {} and {} is {}".format(a,b,r))
print("Its Bézout coefficients are {} and {}".format(s,t))
assert(r == s*a + t*b)
I get the output
The GCD of 47*I - 87 and 43*I - 90 is 43*I - 90
Its Bézout coefficients are 0 and 1
Which is wrong. My understading of what is happening is that the quotient `//` is not giving me the integer quotient, but promoting it to rational quotient.
How do I compute the gaussian integer quotient?JsevillamolMon, 12 Nov 2018 15:04:31 +0100https://ask.sagemath.org/question/44251/