Exercise 2: Modular Inverse of 7 mod 26 — Possible Solution
====================================================================

GIVEN
------------------------------
a = 7, n = 26. Since a < n, the extended Euclidean algorithm's
first step effectively swaps them (a quotient of 0), which is
normal and doesn't affect correctness.

STEP-BY-STEP TRACE (tracking q, r, s, t)
------------------------------
q=0: r=26, s=0,  t=1
q=3: r=7,  s=1,  t=0
q=1: r=5,  s=-3, t=1
q=2: r=2,  s=4,  t=-1
q=2: r=1,  s=-11, t=3

The remainder reaches 1, confirming gcd(7, 26) = 1 - so a modular
inverse exists (per this chapter's own existence condition).

RESULT
------------------------------
gcd = 1, x = -11 (the coefficient of 7)

Reducing into the range [0, 26): -11 mod 26 = 15

Modular inverse of 7 mod 26 = 15

CHECK: 7 * 15 = 105. 105 mod 26 = 1 (since 105 = 26*4 + 1).
Confirmed: 7 * 15 ≡ 1 (mod 26).

WHY THIS WORKS AS AN ANSWER
------------------------------
The full trace is shown including the initial swap step (rather
than skipped over as if it didn't happen), the coefficient
corresponding to a=7 is correctly identified and reduced into the
valid [0,26) range, and the final answer is verified directly by
computing 7*15 mod 26 rather than just trusting the algorithm's
output.