Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this answer
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$.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.