Exercise 2.2.5 (Solutions of some congruences)

Proof.

(a)

Since $\gcd (20,30)=10\nmid 4$, there is no solution to $20x\equiv 4(\mathit{mod}30)$.

( $20x-4=30k\Rightarrow 10\mid 4\Rightarrow 5\mid 2$: this is absurd.)

(b)

Since $\gcd (4,20)=4\nmid 30$, there is no solution to $20x\equiv 30(\mathit{mod}4)$.

(c)

The Bézout’s algorithm gives the inverse of $353$ modulo $400$, which is $17$. Therefore $$\begin{array}{llll}\hfill 353x\equiv 254(\mathit{mod}400)& ⟺x\equiv 254\times 17(\mathit{mod}400)& \hfill & \\ \hfill & ⟺x\equiv 318(\mathit{mod}400).& \hfill & \end{array}$$

Check: $353\times 318\equiv 254(\mathit{mod}400)$.

(d)

$$\begin{array}{llll}\hfill 57x\equiv 87(\mathit{mod}105)& ⟺19x\equiv 29(\mathit{mod}35)& \hfill & \\ \hfill & ⟺x\equiv 29\times 24(\mathit{mod}35)& \hfill & \\ \hfill & ⟺x\equiv 31(\mathit{mod}35).& \hfill & \end{array}$$

This gives $3$ solutions modulo $105$:

$$x\equiv 31,66,101(\mathit{mod}105).$$

(e)

$$\begin{array}{llll}\hfill 64x\equiv 83(\mathit{mod}105)& ⟺x\equiv 83\times 64(\mathit{mod}105)& \hfill & \\ \hfill & ⟺x\equiv 62(\mathit{mod}105).& \hfill & \end{array}$$

(f)

Since $19$ divides $589,817$ and $209$, $$\begin{array}{llll}\hfill 589x\equiv 209(\mathit{mod}817)& ⟺31x\equiv 11(\mathit{mod}43)& \hfill & \\ \hfill & ⟺x\equiv 11\times 25(\mathit{mod}43)& \hfill & \\ \hfill & ⟺x\equiv 17(\mathit{mod}43).& \hfill & \end{array}$$

This gives $19$ solutions modulo $817$: $x\equiv$

$$17,60,103,146,189,232,275,318,361,404,447,490,533,576,619,662,705,748,791(\mathit{mod}817).$$

(g)

Here $\gcd (49,999)=1$. $$\begin{array}{llll}\hfill 49x\equiv 5000(\mathit{mod}999)& ⟺49x\equiv 5(\mathit{mod}999)& \hfill & \\ \hfill & ⟺x\equiv 367\times 5(\mathit{mod}999)& \hfill & \\ \hfill & ⟺x\equiv 836(\mathit{mod}999).& \hfill & \end{array}$$