# If $a + b \equiv 0 \pmod p$, and $a + b \equiv 0 \pmod q$, why does $a + b \equiv 0 \pmod {pq}$?

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,$$

$$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.

-
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

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 arithmetic should answer this immediately.

-
It does. Many thanks, now perfectly clear. – Moschops Aug 16 '12 at 21:55

Since $p$ and $q$ are distinct prime numbers, if they both separately divide $a+b$, then they both occur in the prime factorization of $a+b$. Therefore, $pq$ would divide $a+b$.

-
Are you saying $ijpq=jp=iq$?? – Rahul Aug 16 '12 at 21:39
Let me edit my post... – C. Williamson Aug 16 '12 at 21:39
Now that is the same as my answer except that my $x$ is your $a + b$. – Tunococ Aug 16 '12 at 21:54
True, and you were first. My first answer was bad. – C. Williamson Aug 16 '12 at 21:57
Guys, guys, it's all for the joy of helping number theory idiots like me! Can't we all just get along? :) Also, if I ever meet Tom Apostol, I'm going to push him over. Fair warning given. – Moschops Aug 16 '12 at 22:02