# Revision history [back]

### 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
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?

### 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?