Different implementations for Extended Euclidean algorithm yield different results?

Question

I'm trying to implement the RSA algorithm. I have been reading about the Extended Euclidean Algorithm, and tried to implement the code on different websites. It didn't give me the correct results for some of my decryptions, so I have been debugging and I noticed that different implementations of the algorithm yield different results. The first is from Brilliant.org, and the second is from https://www.rookieslab.com/posts/extended-euclid-algorithm-to-find-gcd-bezouts-coefficients-python-cpp-code.

def egcd(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q, r = b//a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
    gcd = b
    return gcd, x, y


def extended_euclid_gcd(a, b):
"""
Returns a list `result` of size 3 where:
Referring to the equation ax + by = gcd(a, b)
    result[0] is gcd(a, b)
    result[1] is x
    result[2] is y
"""
    s = 0; old_s = 1
    t = 1; old_t = 0
    r = b; old_r = a
    while r != 0:
        quotient = old_r/r
        old_r, r = r, old_r - quotient*r
        old_s, s = s, old_s - quotient*s
        old_t, t = t, old_t - quotient*t
    return old_r, old_s, old_t

For a = 3, b = 25456, (following from the slightly less simple example at https://www.di-mgt.com.au/rsa_alg.html) I have these results for the two implementations, respectively:

gcd:  1 x:  -8485 y:  1
gcd:  25456 x:  0 y:  1

Why are these different? Why for the second implementation is the gcd not 1 at all? A follow up question is since I'm trying to follow the example at the link, is that I got a negative value for the x. Their answer was 16971. I read here https://math.stackexchange.com/questions/1001199/uniqueness-of-extended-euclidean-algorithm that the Extended Euclidean algorithm finds the answer that is closest to the origin. Is there any way to specify closest to the origin, and positive?

Answer 1

Author of the post linking to Rookie's Lab here.

James K Polk is right, the code was indeed written in Python 2 and is not compatible with Python 3.

We have to update quotient = old_r/r to quotient = old_r//r to make it compatible with Python 3.

I'll update the original post to reflect this finding. Thank you Lo Ran.