Exercise 3: Fermat as a Special Case of Euler, Verified on n=21 — Possible Solution
====================================================================

PART 1: WHY FERMAT IS A SPECIAL CASE OF EULER
------------------------------
Euler's theorem states a^phi(n) ≡ 1 (mod n) for any n, whenever
gcd(a,n)=1.

This chapter's own earlier finding established that for a PRIME p,
every integer from 1 to p-1 is automatically coprime to p, so
phi(p) = p-1 exactly.

Substituting n = p (a prime) into Euler's theorem: a^phi(p) ≡ 1
(mod p) becomes a^(p-1) ≡ 1 (mod p) - which is precisely Fermat's
Little Theorem's own statement, word for word. Euler's theorem
doesn't need a separate proof for the prime case - it already
covers it, because phi(p)=p-1 makes the general formula collapse
exactly onto the more specific one.

PART 2: VERIFYING EULER'S THEOREM DIRECTLY ON n=21 (COMPOSITE)
------------------------------
Step 1: compute phi(21). 21 = 3*7, both prime and distinct, so
phi(21) = (3-1)(7-1) = 2*6 = 12.

Step 2: check three values of a coprime to 21:

a=2: gcd(2,21)=1. 2^12 mod 21 = 1
a=4: gcd(4,21)=1. 4^12 mod 21 = 1
a=5: gcd(5,21)=1. 5^12 mod 21 = 1

All three confirm a^phi(21) mod 21 = 1, exactly as Euler's theorem
predicts.

RESULT
------------------------------
Fermat's Little Theorem is exactly what Euler's theorem reduces to
when n happens to be prime, since phi(p)=p-1 in that case - not a
separately-proved coincidence. And Euler's theorem itself checks
out directly on a genuinely composite modulus (21 = 3*7), where
phi(n) is not simply n-1.

WHY THIS WORKS AS AN ANSWER
------------------------------
Part 1 makes the substitution explicit (n=p, phi(p)=p-1) rather
than just asserting Fermat is "a special case," and Part 2 verifies
Euler's own more general theorem on a genuinely different kind of
input (a composite modulus with a non-trivial phi(n) value) rather
than reusing a prime example that wouldn't actually test the
generalization.