def div_euc(a, b): q = 0 if a > 0 and b > 0: while a >= b: a -= b q += 1 return (q, a) else: temp_a = a temp_b = b if temp_a < 0: temp_a = - temp_a if temp_b < 0: temp_b = - temp_b while temp_a >= temp_b: temp_a -= temp_b q += 1 if temp_a != 0: q += 1 temp_a = temp_b - temp_a if a < 0 and b < 0: return(q, temp_a) elif (a < 0 and not b < 0) or (b<0 and not a < 0): return(-q, temp_a) else: return(-q, temp_a)