2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think about fundamental theorem of arithmetic... $\endgroup$ – Tunococ Aug 16 '12 at 21:35
  • $\begingroup$ 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. $\endgroup$ – Moschops Aug 16 '12 at 21:38
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It does. Many thanks, now perfectly clear. $\endgroup$ – Moschops Aug 16 '12 at 21:55
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Are you saying $ijpq=jp=iq$?? $\endgroup$ – Rahul Aug 16 '12 at 21:39
  • $\begingroup$ Let me edit my post... $\endgroup$ – C. Williamson Aug 16 '12 at 21:39
  • $\begingroup$ Now that is the same as my answer except that my $x$ is your $a + b$. $\endgroup$ – Tunococ Aug 16 '12 at 21:54
  • $\begingroup$ True, and you were first. My first answer was bad. $\endgroup$ – C. Williamson Aug 16 '12 at 21:57
  • $\begingroup$ 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. $\endgroup$ – Moschops Aug 16 '12 at 22:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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