Euclidean algorithm

1. Calculate 2¹⁶ mod 123.

2. Calculate 3¹⁴ mod 30.

3. Use the modular exponentiation algorithm to calculate 15¹⁹ mod 37.

4. Find gcd(143, 227), gcd(8, 182), gcd(125, 87) using Euclidean method.

5. Find the values of x₂ and y₂ from the given values (a, b) = (8, 182) by using extended Euclidean algorithm.