+0

# Congruences

0
38
1

Find the least positive four-digit solution to the following system of congruences.

7x = 21 (mod 14)

2x + 18 = 16 (mod 9)

Jul 8, 2021

#1
+26122
+2

Find the least positive four-digit solution to the following system of congruences.
$$7x \equiv 21 \pmod{14} \\ 2x + 18 \equiv 16 \pmod{9}$$

$$\begin{array}{|rcll|} \hline 7x &\equiv& 21 \pmod{14} \\ 7x &\equiv& 21-14 \pmod{14} \\ 7x &\equiv& 7 \pmod{14} \\ 7x &=& 7 +14m \quad m\in \mathbb{Z} \\ 7x &=& 7 +14m \quad | \quad :7 \\ x &=& 1 +2m \quad | \quad \text{x is an odd number!} \\ x &\equiv& 1 \pmod{2} \\ \hline \end{array}$$

...so $$7x \equiv 21 \pmod{14}$$ or $$x \equiv 1 \pmod{2}$$

$$\begin{array}{|rcl|rcl|} \hline 2x + 18 &\equiv& 16 \pmod{9} \\ 2x &\equiv& 16-18 \pmod{9} \\ 2x &\equiv& -2 \pmod{9} \\ 2x &=& -2 +9n \quad n\in \mathbb{Z} \\ 2x &=& -2 +9n \quad | \quad x=1+2m \\ 2(1+2m) &=& -2 +9n \\ 2+4m &=& -2 +9n \\ 4m &=& -4 +9n \\ m &=& \frac{-4 +9n}{4} \\ m &=& \frac{-4 +8n+n}{4} \\ m &=& -1+2n+ \underbrace{ \frac{n}{4} }_{=r} \quad r \in \mathbb{Z} \\ m &=& -1+2n+ r & r &=& \frac{n}{4} \\ & & & 4r &=& n \\ & & & \mathbf{n} &=& \mathbf{4r} \\ m &=& -1+2(4r)+ r \\ \mathbf{m} &=& \mathbf{-1+9r} \\ \hline x &=& 1+2m \quad | \quad m=-1+9r \\ x &=& 1+2(-1+9r) \\ x &=& 1-2+18r \\ \mathbf{x} &=& \mathbf{-1+18r} \quad r \in \mathbb{Z} \\ \hline \end{array}$$

Find the least positive four-digit solution:

$$\begin{array}{|rcll|} \hline -1+18r &>& 999 \\ 18r &>& 1000 \\ r &>& \frac{1000}{18} \\ r &>& 55.\bar{5} \\ r &=& 56 \\ \hline x &=& -1+18*56 \\ \mathbf{ x} &=& \mathbf{1007} \\ \hline \end{array}$$

The least positive four-digit solution is 1007

Jul 9, 2021