3
$\begingroup$

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$

  • 0
    Then Fermat's Little Theorem should suffice.2012-12-28

3 Answers 3

4

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

  • 0
    +1. Neat ${}{}$2012-12-28
3

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

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

  • 0
    @Khromonkey, this number is special as identified by Andre, but in general you need CRT to solve such problem2012-12-28
2

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