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

This is excercise 1 in George E. Andrews number theory. page 51. How am i supposed to solve this? Thanks very much in advance. I used the cancellation law to get isolate the x. But I don’t know what to do next.

$5x\equiv 4 \pmod 3$

$7x\equiv 6 \pmod 5$

$9x\equiv 8 \pmod 7$

share|cite|improve this question
Were these $3$ separate problems or related to the Chinese Remainder Theorem to find an $x$ that satisfies them simultaneously? – Amzoti Dec 28 '12 at 19:41
I havent seen chinese remainder theorem yet – Carry on Smiling Dec 28 '12 at 19:41
Then Fermat's Little Theorem should suffice. – Amzoti Dec 28 '12 at 19:42
up vote 4 down vote accepted

The numbers are very special! Our system is equivalent to $2x\equiv 1$ modulo $3$, $5$, $7$, or equivalently $2x\equiv 1\pmod{105}$.

To solve $2x\equiv 1\pmod{105}$, rewrite as $2x\equiv 106\pmod{105}$. This has solution $x\equiv 53\pmod{105}$.

share|cite|improve this answer
+1. Neat ${}{}$ – user17762 Dec 28 '12 at 19:44

Observe that in each case, $ax\equiv1\equiv a^{p-1}\pmod p$

So, $x\equiv a^{p-2}\pmod p$

share|cite|improve this answer
Are you using little Fermat? – Carry on Smiling Dec 28 '12 at 19:39
@Khromonkey,exactly. – lab bhattacharjee Dec 28 '12 at 19:40
How can i find an x such that $x\equiv a^p-2$ for p=3,5 and 7 simultaneously? – Carry on Smiling Dec 28 '12 at 19:43
@Khromonkey, for example, $p=3,a=5, x\equiv 5^{3-2}\equiv\pmod 3\equiv 2$, then apply CRT – lab bhattacharjee Dec 28 '12 at 19:45
i dont know how to use chinese remainder theorem but ill +1 anyways because ill read it once I read about it. – Carry on Smiling Dec 28 '12 at 19:48

$$5 x \equiv 1 \pmod 3 \implies x \equiv 2 \pmod 3$$ $$7 x \equiv 1 \pmod 5 \implies x \equiv 3 \pmod 5$$ $$9 x \equiv 1 \pmod 7 \implies x \equiv 4 \pmod 7$$ $$x \equiv 2 \pmod 3 \text{ and }x \equiv 3 \pmod 5 \implies x \equiv a \pmod{15}$$ Since $x \equiv 2 \pmod 3$, we have $a \in \{2,5,8,11,14\}$. Since $x$ is also $3 \pmod 5$, we get that $$x \equiv 8 \pmod {15}$$

$$x \equiv 8 \pmod {15} \text{ and }x \equiv 4 \pmod 7 \implies x \equiv b \pmod{105}$$ Since $x \equiv 8 \pmod 15$, we have $b \in \{8,23,38,53,68,83,98\}$. Since $x$ is also $4 \pmod 7$, we get that $$x \equiv 53 \pmod {105}$$

share|cite|improve this answer

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.