Exercise 3: Does 6 Have a Modular Inverse mod 15? — Possible Solution
====================================================================

STEP 1: APPLY THE EXISTENCE CONDITION (WITHOUT RUNNING THE ALGORITHM)
------------------------------
Per this chapter's own existence condition, a modular inverse of a
mod n exists if and only if gcd(a, n) = 1.

gcd(6, 15): both 6 and 15 are divisible by 3 (6 = 3*2, 15 = 3*5),
so gcd(6, 15) = 3, not 1.

Since gcd(6, 15) = 3 != 1, this chapter's own existence condition
says directly that NO modular inverse of 6 mod 15 exists - no
extended Euclidean algorithm run is needed to reach this
conclusion.

STEP 2: CONFIRM BY CHECKING EVERY POSSIBLE x FROM 0 TO 14
------------------------------
x=0: 6*0 mod 15 = 0      x=8:  6*8 mod 15 = 3
x=1: 6*1 mod 15 = 6      x=9:  6*9 mod 15 = 9
x=2: 6*2 mod 15 = 12     x=10: 6*10 mod 15 = 0
x=3: 6*3 mod 15 = 3      x=11: 6*11 mod 15 = 6
x=4: 6*4 mod 15 = 9      x=12: 6*12 mod 15 = 12
x=5: 6*5 mod 15 = 0      x=13: 6*13 mod 15 = 3
x=6: 6*6 mod 15 = 6      x=14: 6*14 mod 15 = 9
x=7: 6*7 mod 15 = 12

Across all 15 possible values of x, 6x mod 15 only ever produces
one of {0, 3, 6, 9, 12} - every result is itself a multiple of 3
(matching gcd(6,15)=3) - and 1 never appears anywhere in the list.

RESULT
------------------------------
No, 6 does not have a modular inverse mod 15 - confirmed both by
the existence condition (gcd != 1) and by direct, exhaustive
checking of every candidate.

WHY THIS WORKS AS AN ANSWER
------------------------------
The existence condition is applied first, correctly reaching the
answer without needing the full algorithm, and the exhaustive check
afterward doesn't just confirm "no 1 appears" but also notices the
underlying pattern (every result is a multiple of gcd(6,15)=3),
tying the confirmation back to the same GCD value used in the
existence check rather than treating the two as unrelated.