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,

\[\begin{split} \operatorname{GCD}(a, b) = \begin{cases} a & \text{if}~b = 0, \\ \operatorname{GCD}(b,\ a \bmod b) & \text{if}~b > 0. \end{cases} \end{split}\]

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

\[\begin{split} A = \left[\begin{array}{rr} a & b \\ c & d \end{array}\right] \end{split}\]

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