Exercise 2: Rejecting e=6 and Choosing a Valid Key for p=7, q=13 — Possible Solution
====================================================================

GIVEN
------------------------------
p=7, q=13, so n=91 and phi(n)=(7-1)(13-1)=72. Proposed e=6.

WHY e=6 IS INVALID
------------------------------
Per this chapter's own step 4, e must satisfy gcd(e, phi(n)) = 1.
Checking: gcd(6, 72). Both 6 and 72 are divisible by 6 (72 = 6*12),
so gcd(6,72) = 6, not 1.

Since gcd(6,72) != 1, no modular inverse of 6 mod 72 exists at all
(per Chapter 5's own existence condition) - there would be no way
to compute a valid d, so key generation cannot proceed with this e.
This isn't a minor inefficiency; it's a hard failure.

CHOOSING A VALID e
------------------------------
Trying e=5: gcd(5, 72) = 1 (5 is prime and doesn't divide 72).
Valid choice.

COMPUTING d
------------------------------
Running the extended Euclidean algorithm on (5, 72) gives d = 29.

Check: 5*29 = 145. 145 mod 72 = 1 (since 145 = 72*2 + 1).
Confirmed: e*d ≡ 1 (mod 72).

ENCRYPT AND DECRYPT m=6
------------------------------
Public key: (n=91, e=5). Private key: (n=91, d=29).

Encrypt: c = 6^5 mod 91 = 41
Decrypt: m = 41^29 mod 91 = 6

RESULT
------------------------------
e=6 is correctly rejected because it shares a factor (6) with
phi(n)=72, making a modular inverse impossible. e=5 is valid,
d=29 is its correct inverse, and the encrypt/decrypt round trip on
m=6 confirms the corrected key pair works.

WHY THIS WORKS AS AN ANSWER
------------------------------
The rejection of e=6 is justified by name-checking this chapter's
own gcd requirement and explicitly tying the failure back to
Chapter 5's existence condition (no inverse exists at all, not just
a harder computation), rather than simply asserting e=6 "doesn't
work," and the replacement key pair is fully verified with a real
encrypt/decrypt round trip.