# simple congruence system problem.

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$

-
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 – dREaM Dec 28 '12 at 19:41
Then Fermat's Little Theorem should suffice. – Amzoti Dec 28 '12 at 19:42

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

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

-
Are you using little Fermat? – dREaM 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? – dREaM 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. – dREaM 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}$$

-