1
$\begingroup$

Q. let $p$ and $q$ be distinct odd prime numbers. Prove that for any $x \in \mathbb{Z} /pq$ we get $$x^{(pq-p-q+3)/2} \equiv x \mod pq$$

we have just learnt the chinese remainder theorem so I have tried to use it but I'm getting on where. Please help!

$\endgroup$
3
  • 2
    $\begingroup$ It is customary here that you show some work yourself. Your post is a bit lacking in that respect. May I humbly suggest that you try to do a small example case. Such as $p=5$, $q=3$. Edit your post and type that in there. You may even get a lightbulb moment. But if you don't, take a peek at my hint/answer. As a general rule, when you are hit with a problem where you don't immediately see a way forward, you should try a small case. And then another one. Those will often enough give you an idea of how the land lies, and may point at a way. Do this with many problems to get experience! $\endgroup$ – Jyrki Lahtonen Jan 20 '15 at 22:51
  • 1
    $\begingroup$ Oh, and a friendly welcome to Math.SE from your friendly community moderator. $\endgroup$ – Jyrki Lahtonen Jan 20 '15 at 22:52
  • $\begingroup$ @JyrkiLahtonen thank you I will try $\endgroup$ – numbertheoryguy101 Jan 20 '15 at 23:07
3
$\begingroup$

Hints: Little Fermat tells you that $$ x^p\equiv x\pmod p $$ and the corresponding congruence with $q$. As a consequence of this you can surely prove that $$ x^{1+k(p-1)}\equiv x\pmod p $$ for any natural number $k$. A key observation is that $$ \frac{pq-p-q+3}2=1+\frac{(p-1)(q-1)}2. $$ Stare at this for a while. It will give you bits that you can combine with the Chinese Remainder Theorem.

$\endgroup$
1
  • $\begingroup$ I DONE IT!! thank you! this forum is great - I will try post more of my solution next time $\endgroup$ – numbertheoryguy101 Jan 20 '15 at 23:14

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.