Exercise 3: Explaining the Three Substitutions in the RSA Correctness Proof — Possible Solution
====================================================================

WHERE ed = 1 + k*phi(n) COMES FROM
------------------------------
This chapter's own key generation step 5 computes d specifically
so that e*d ≡ 1 (mod phi(n)) - that's the entire definition of d
being the modular inverse of e. By the definition of congruence
(Chapter 3), "e*d is congruent to 1 mod phi(n)" means exactly that
e*d and 1 differ by some whole multiple of phi(n) - which is
precisely what "ed = 1 + k*phi(n) for some integer k" states. This
isn't a new assumption; it's just restating what d being e's
modular inverse already means, in a form useful for the next step.

SUBSTITUTION 1: c^d = m^(ed)
------------------------------
Since c = m^e mod n (encryption), raising c to the power d gives
(m^e)^d, which is simply m^(e*d) by ordinary exponent rules - one
exponent raised to another power multiplies the exponents together.

SUBSTITUTION 2: m^(ed) = m * (m^phi(n))^k
------------------------------
Using ed = 1 + k*phi(n) from above, m^(ed) becomes
m^(1 + k*phi(n)), which splits (again by ordinary exponent rules,
since adding exponents means multiplying the results) into
m^1 * m^(k*phi(n)), i.e. m * (m^phi(n))^k.

WHERE EULER'S THEOREM IS ACTUALLY USED
------------------------------
This is the one substitution that isn't just algebra - it's where
Chapter 8's own theorem does real work. Euler's theorem states that
m^phi(n) ≡ 1 (mod n), specifically whenever gcd(m,n)=1. Substituting
this into the expression from the previous step: (m^phi(n))^k
becomes (1)^k = 1 (mod n), collapsing the entire k*phi(n) part of
the exponent down to just 1.

PUTTING IT TOGETHER
------------------------------
c^d = m * (m^phi(n))^k ≡ m * 1 = m (mod n)

RESULT
------------------------------
Two of the three steps (splitting the exponent, combining it back
after substituting) are ordinary algebra with exponents - they'd
be true for any numbers, not just RSA's own. The one step that
genuinely relies on real mathematics specific to this course is the
middle one: replacing m^phi(n) with 1, which is only true because
of Euler's theorem, and only when gcd(m,n)=1.

WHY THIS WORKS AS AN ANSWER
------------------------------
Each of the three steps is explained separately, correctly
distinguishing which parts are just exponent-arithmetic bookkeeping
and which one step is the actual number-theoretic content (Euler's
theorem) that makes the whole proof work - rather than presenting
the derivation as one undifferentiated block of algebra.