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
    Were these $3$ separate problems or related to the Chinese Remainder Theorem to find an $x$ that satisfies them simultaneously?2012-12-28
  • 0
    I havent seen chinese remainder theorem yet2012-12-28
  • 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
    Are you using little Fermat?2012-12-28
  • 0
    @Khromonkey,exactly.2012-12-28
  • 0
    How can i find an x such that $x\equiv a^p-2$ for p=3,5 and 7 simultaneously?2012-12-28
  • 0
    @Khromonkey, for example, $p=3,a=5, x\equiv 5^{3-2}\equiv\pmod 3\equiv 2$, then apply CRT2012-12-28
  • 0
    i dont know how to use chinese remainder theorem but ill +1 anyways because ill read it once I read about it.2012-12-28
  • 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}$$