Take the tour ×  Put a bit more coherently, given $p$ and $q$ as
distinct prime numbers, and thus $(p,q)=1$, if  $$p^{(q-1)} +
q^{(p-1)} \equiv 1 \pmod p$$ and $$p^{(q-1)} + q^{(p-1)} \equiv
1 \pmod q,$$  why does that lead to  $$p^{(q-1)} + q^{(p-1)}
\equiv 1 \pmod {pq}?$$  The textbook I'm working with jumps to
that conclusion as if it were obvious, but it's not. Not to me,
at least.  share|improve this question I think about fundamental
theorem of arithmetic... –  Tunococ Aug 16 '12 at 21:35 I've had
lots of hints. I can manipulate the CRT over and over
mechanically but have no understanding of it. When it comes to
number theory, I just need someone to tell me, and then I
understand, much like C.Williamson has just done. Now that he's
told me, I understand. –  Moschops Aug 16 '12 at 21:38 add
comment  2 Answers  up vote 4 down vote accepted  Your question
should be rephrased as:  Let $p$ and $q$ be distinct prime
numbers. If $p | x$ and $q | x$, is it true that $pq | x$?  The
fundamental theorem of arithme