RSA, CRT et cetera

[Julieta Shem]

Hey, let's bring this great group back to life. I recently learned that
by just ignoring Google Groups, we can get some peace here. If you
haven't done so, please do it --- let's have a clean USENET by just
ignoring a news agent.

I've been pondering about RSA and the Chinese Remainder Theorem. Even
though RSA is very much involved with the CRT, I wonder if it is the CRT
again that could help me on exercise after this first one.

--8<---------------cut here---------------start------------->8---
Exercise. Let n = pq, where p, q are distinct primes. Let a be coprime
to n. Show that

a^{ed} = a mod p
a^{ed} = a mod q,

where ed = 1 mod phi(n).

Solution. I notice first that

ed - 1 = 0 mod phi(n)
= t phi(n)
= t (q - 1) (p - 1)
= k (p - 1)

for some integer t, and k = t (q - 1). So we get

a^{ed} = a a^{ed - 1}
= a a^{k (p - 1)}
= a (a^{p - 1})^k

We're interested in reducing the equation modulo p. So by Fermat's
Little Theorem, we get

a^{ed} = a 1^k = a mod p,
a^{ed} = a 1^k = a mod q,

as desired. (Whatever we did for p, we could do for q.)
--8<---------------cut here---------------end--------------->8---

I think that's all clear. Any imperfections anywhere?

Now consider the next exercise.

Exercise. Let n = pq, a coprime to n. If

a^{ed} = a mod p
a^{ed} = a mod q,

where ed = 1 mod phi(n), show that

a^{ed} = a mod n.

--8<---------------cut here---------------start------------->8---
Analysis. This really feels like an application to the Chinese
Remainder Theorem. I looked at examples such as

x = 2 mod 3
x = 2 mod 5

and indeed Gauss's algorithm gives

x = 2 * 5 * inv(5, 3) + 2 * 3 * inv(3, 5)
= 2 * 5 * 2 + 2 * 3 * 2
= 32
= 2 mod 15,

where inv(y, z) means the multiplicative inverse of y modulo z.
--8<---------------cut here---------------end--------------->8---

But I can't see how to deduce the fact from Gauss Algorithm. Instead,
I resorted to use Bézout's identity.

--8<---------------cut here---------------start------------->8---
Exercise. If x = y mod p, x = y mod q, then x = y mod pq.

Solution. By Bézout's identify, we get

1 = ap + bq

Multiply x on both sides, getting

x = apx + bqx

From the hypothesis, x = t(1)p + y and x = t(2)q + y. Substituting...

x = ap(t(2)q + y) + bq(t(1)p + y)
= pqat(2) + apy + pqbt(1) + bqy
= pqat(2) + pqbt(1) + apy + bqy
= pq(at(2) + bt(1)) + y(ap + bq)

Now, if we reduce the last equation modulo pq, we get

x = 0 + y(ap + bq) = y

because 1 = ap + bq. We're done.
--8<---------------cut here---------------end--------------->8---

Is it merely appearance that perhaps Gauss's Algorithm would apply to
the exercise? It seems to, but I can't quite see it, so there's
probably something to learn there. Please, (alt.algebra.)help.