Implement the Euclidean algorithm for gcd(a, b) using only the modulo operator and a loop. Explain why it terminates in O(log min(a, b)) steps.

Examples

Example 1:

Input: a = 48, b = 18
Output: 6
Explanation: gcd(a, b) = gcd(b, a mod b) with gcd(a, 0) = a. Steps: gcd(48, 18) -> gcd(18, 12) -> gcd(12, 6) -> gcd(6, 0) = 6.

Example 2:

Input: a = 100, b = 75
Output: 25
Explanation: gcd(100, 75) -> gcd(75, 25) -> gcd(25, 0) = 25.

Compute lcm(12, 18) and explain the identity that lets you derive lcm from gcd in O(log n) time without factorizing either number.

What is (7 * 13) mod 5, computed without ever forming the full product 91? State the modular multiplication identity you used.

Implement fast modular exponentiation powMod(base, exp, mod) in O(log exp). Use it to compute 3^200 mod 13.

Examples

Example 1:

Input: base = 3, exp = 200, mod = 13
Output: 9
Explanation: Square-and-multiply walks the binary expansion of exp: square base each step, multiply into result when the current bit is set, reduce mod m after each operation. O(log exp).