RSA, CRT et cetera

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.