# very hard question using chinese remainder theorem

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!

• 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! – Jyrki Lahtonen Jan 20 '15 at 22:51
• Oh, and a friendly welcome to Math.SE from your friendly community moderator. – Jyrki Lahtonen Jan 20 '15 at 22:52
• @JyrkiLahtonen thank you I will try – numbertheoryguy101 Jan 20 '15 at 23:07

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.