math/extended_euclidean_algorithm cannot properly handle negative numbers

[pikulet]

Think there is a mistake in the algorithm implemented.
By definition, gcd (a,b) = gcd (a,-b) = gcd (-a,b) = gcd (-a,-b)

So for a = 1, b = 4, the gcd is 1.

eqn1: 0(4) + 1(1) = 1 (correct)
eqn2: 0(4) + 1(-1) = -1 (sign incorrect)
eqn3: -1(1) + 1(-4) = -5 (sign and value incorrect)
eqn4: 1(-1) + 0(-4) = -1 (sign incorrect)

[dhruvmanila]

Hey, thank you for pointing this out. It also seems that the Euclidean algorithm for GCD is not able to handle negative numbers as well:

$ python greatest_common_divisor.py
Enter two integers separated by comma (,): -3,9
greatest_common_divisor(-3, 9) = -3
By iterative gcd(-3, 9) = 3

$ python greatest_common_divisor.py
Enter two integers separated by comma (,): 3,-9
greatest_common_divisor(3, -9) = 3
By iterative gcd(3, -9) = -3

$ python greatest_common_divisor.py
Enter two integers separated by comma (,): -3,-9
greatest_common_divisor(-3, -9) = -3
By iterative gcd(-3, -9) = -3

$ python greatest_common_divisor.py
Enter two integers separated by comma (,): 3,9
greatest_common_divisor(3, 9) = 3
By iterative gcd(3, 9) = 3

Can you make two separate PRs to correct the algorithms?