Exercises¶
Problem 1
Write a function named gcd() that accepts two integers \(a\) and \(b\), not both zero.
Compute the greatest common divisor of \(a\) and \(b\) with the Euclidean algorithm: for \(a, b \ge 0\), not both zero,
Use the property \(\operatorname{GCD}(a, b) = \operatorname{GCD}(|a|, |b|)\) to account for cases where \(a\) and/or \(b\) are negative.
Hint: Use either a loop or recursion.
Test Cases
print(gcd(21, 0))
print(gcd(0, 21))
print(gcd(252, 105))
print(gcd(105, 252))
print(gcd(252, -105))
21
21
21
21
21
print(gcd(12345, 67890))
print(gcd(-56, 98))
print(gcd(112233, 445566))
15
14
33
Problem 2
Write a function named lcm() that accepts two integers \(a\) and \(b\), not both zero.
Use the formula \(\operatorname{LCM}(a, b) = |ab| / \operatorname{GCD}(a, b)\) and the gcd() function from Problem 1.
Use integer division so the least common multiple is returned as an integer.
Test Cases
print(lcm(0, 6))
print(lcm(4, 6))
print(lcm(-12, 18))
print(lcm(123456789, 987654321))
0
12
36
13548070123626141
Problem 3
Write a function named xgcd() that accepts two integers \(a\) and \(b\), not both zero.
Run the extended Euclidean algorithm recursively.
In each case (the base case with \(a > 0\) or \(a < 0\), and the recursive case) return three integers: \(d = \operatorname{GCD}(a, b)\), \(x\), and \(y\) such that \(d = ax + by\).
Test Cases
print(xgcd(15, 26))
print(xgcd(112233, 445566))
print(xgcd(12, -53))
print(xgcd(-12, -53))
print(xgcd(-7, 0))
(1, 7, -4)
(33, -4633, 1167)
(1, -22, -5)
(1, 22, -5)
(7, -1, 0)
Problem 4
Write a function named sl2mat() that accepts two relatively prime integers \(a\) and \(b\), that is, \(\operatorname{GCD}(a, b) = 1\).
Return a NumPy array
such that \(c\) and \(d\) are integers and \(\det(A) = ad - bc = 1\).
Test Cases
print(sl2mat(1, 7))
print(sl2mat(17, -89))
A = sl2mat(5, 151)
print(np.linalg.det(A)) # Equal to 1, up to floating-point roundoff.
[[1 7]
[0 1]]
[[ 17 -89]
[ -4 21]]
1.0000000000000082