将egcd公式转换为python

试图将这个egcd方程转换成python。

egcd(a, b) = (1, 0), if b = 0
= (t, s - q * t), otherwise, where
q = a / b (note: integer division)
r = a mod b
(s, t) = egcd(b, r)

我使用的测试是egcd(5,37),它应该返回(15,-2),但是返回(19.5,-5.135135135135)

我的代码是:

def egcd(a, b):
    if b == 0:
        return (1, 0)
    else:
        q = a / b # Calculate q
        r = a % b # Calculate r
        (s,t) = egcd(b,r) # Calculate (s, t) by calling egcd(b, r)
        return (t,s-q*t) # Return (t, s-q*t)