Revision history [back]

There is indeed an issue since the _floordiv_ method of the elements thinks that ZI is a field, see:

sage: a._floordiv_?
Docstring:     
   Return the quotient of self and other. Since these are field
   elements, the floor division is exactly the same as usual division.

That said, you can write the integer division yourself: just replace

q = r0 // r1

with

q = ZI(real(r0/r1).round() + I*imag(r0/r1).round())

and you will get:

The GCD of 47*I - 87 and 43*I - 90 is 1
Its Bézout coefficients are -8*I - 39 and 6*I + 39

There is indeed an issue since the _floordiv_ method of the elements thinks that ZI is a field, see:

sage: a._floordiv_?
Docstring:     
   Return the quotient of self and other. Since these are field
   elements, the floor division is exactly the same as usual division.

That said, you can write the integer division yourself: just replace

q = r0 // r1

with

q = ZI(real(r0/r1).round() + I*imag(r0/r1).round())

and you will get:

The GCD of 47*I - 87 and 43*I - 90 is 1
Its Bézout coefficients are -8*I - 39 and 6*I + 39

EDIT Regarding the comments, you can add the quotient function as the parameter of your function, which defaults to the // function as follows:

# Extended Euclides Algorithm
def extended_euclides(a,b,quo=lambda a,b:a//b):
    r0 = a; r1 = b
    s0 = 1; s1 = 0
    t0 = 0; t1 = 1
    while r1 != 0: 
        q = quo(r0,r1)
        r0, r1 = r1, r0 - q * r1
        s0, s1 = s1, s0 - q * s1
        t0, t1 = t1, t0 - q * t1
    return r0, s0, t0

So that you can do:

sage: extended_euclides(7,2)
(1, 1, -3)

but also

sage: ZI = QuadraticField(-1, 'I').ring_of_integers()
....: a = ZI(-87 + 47*I); b = ZI(-90 + 43*I)

sage: extended_euclides(a,b,quo=lambda a,b: ZI(real(a/b).round() + I*imag(a/b).round()))
(1, -8*I - 39, 6*I + 39)