+248 Find the least positive four-digit solution to the following system of congruences.
\(\begin{align*} 7x &\equiv 21 \pmod{14} \\ 2x+13 &\equiv 16 \pmod{9} \\ -2x+1 &\equiv x \pmod{25} \\ \end{align*}\)
+26391 Find the least positive four-digit solution to the following system of congruences.
\(\begin{align*} 7x &\equiv 21 \pmod{14} \\ 2x+13 &\equiv 16 \pmod{9} \\ -2x+1 &\equiv x \pmod{25} \\ \end{align*}\)
\(\begin{array}{|lrcll|} \hline & \mathbf{7x} &\mathbf{\equiv}& \mathbf{ 21 \pmod{14}} \\ & 7x &\equiv& 21 -14 \pmod{14} \\ & 7x &\equiv& 7 \pmod{14} \\ & 7x &=& 7 +14n \quad & | \quad : 7 \\ \color{blue}(1) & \mathbf{ x} &=& \mathbf{ 1+2n } ~ \text{ and } ~ n \in \mathbb{Z}\qquad [~ \text{ or } ~x \equiv 1 \pmod{2} ] \\ \hline \end{array} \)
\(\begin{array}{|lrcll|} \hline & \mathbf{2x+13} &\mathbf{\equiv}& \mathbf{16 \pmod{9} } \\ & 2x & \equiv & 16 -13 \pmod{9} \\ & 2x & \equiv & 3 \pmod{9} \\ & 2x & = & 3 + 9m \\\\ & \mathbf{x } & = & \mathbf{\dfrac{3 + 9m}{2}} \\ & x &=& \dfrac{8m+m+2+1}{2} \\ & x &=& 4m+1+ \underbrace{\dfrac{ m+1}{2}}_{=a} \\ & x &=& 4m+1+ a & a = \dfrac{ m+1}{2} \\ & & & & 2a = m+1 \\ & & & & \mathbf{m =2a-1} \\ & x &=& 4(2a-1)+1+ a \\ & x &=& -3+9a \\ & x &\equiv& -3 \pmod{9} \\ & x &\equiv& -3+9 \pmod{9} \\ & x &\equiv& 6 \pmod{9} \\ \color{blue}(2) & \mathbf{ x} &=& \mathbf{ 6+9m } ~ \text{ and } ~ m \in \mathbb{Z} \\ \hline \end{array}\)
\(\begin{array}{|lrcll|} \hline & \mathbf{-2x+1} &\mathbf{\equiv}& \mathbf{x \pmod{25} } \\ & -2x+1 &=& x +25k \\ & -3x+1 &=& 25k \\ & 3x &=& 1-25k \\ & \mathbf{x } & = & \mathbf{\dfrac{1-25k}{3}} \\ & x &=& \dfrac{1-24k-k}{3} \\ & x &=& -8k +\underbrace{\dfrac{1-k}{3}}_{=a} \\ & x &=& -8k +a & a = \dfrac{1-k}{3} \\ & & & & 3a = 1-k \\ & & & & \mathbf{k =1-3a} \\ & x &=& -8(1-3a) +a \\ & x &=& -8+25a \\ & x &\equiv& -8 \pmod{25} \\ & x &\equiv& -8+25 \pmod{25} \\ & x &\equiv& 17 \pmod{25} \\ \color{blue}(3) & \mathbf{ x} &=& \mathbf{ 17+25k } ~ \text{ and } ~ k \in \mathbb{Z} \\ \hline \end{array}\)
The system of congruences is now:
\(\begin{array}{|rcll|} \hline \color{blue}(1) & \mathbf{ x} &=& \mathbf{ 1+2n } ~ \text{ and } ~ n \in \mathbb{Z}\qquad [~ \text{ or } ~x \equiv 1 \pmod{2} ] \\ \color{blue}(2) & \mathbf{ x} &=& \mathbf{ 6+9m } ~ \text{ and } ~ m \in \mathbb{Z}\qquad [~ \text{ or } ~x \equiv 6 \pmod{9} ] \\ \color{blue}(3) & \mathbf{ x} &=& \mathbf{ 17+25k } ~ \text{ and } ~ k \in \mathbb{Z}\qquad [~ \text{ or } ~x \equiv 17 \pmod{25} ] \\ \hline \end{array}\)
\(\begin{array}{|lrcll|} \hline \color{blue}(1) & \mathbf{ x} &=& \mathbf{ 1+2n } \\ \color{blue}(2) & \mathbf{ x} &=& \mathbf{ 6+9m } \\\\ & 1+2n &=& 6+9m \\ & 2n &=& 9m+5 \\ & \mathbf{ n } &=& \mathbf{\dfrac{ 9m+5 }{2}} \\ & n &=& \dfrac{8m+m+4+1}{2} \\ & n &=& 4m+2+\underbrace{\dfrac{ m+1}{2}}_{=a} \\ & n &=& 4m+2+a & a = \dfrac{ m+1}{2} \\ & & & & 2a = m+1 \\ & & & & \mathbf{m =2a-1} \\ & x &=& 6+9m \\ & x &=& 6+9(2a-1) \\ & x &=& -3+18a \\ & x &\equiv& -3 \pmod{18} \\ & x &\equiv& -3 +18\pmod{18} \\ & x &\equiv& 15 \pmod{18} \\ \color{blue}(4) & \mathbf{ x} &=& \mathbf{ 15+18z } ~ \text{ and } ~ z \in \mathbb{Z} \\ \hline \end{array} \)
The system of congruences is now:
\(\begin{array}{|lrcll|} \hline \color{blue}(4) & \mathbf{ x} &=& \mathbf{ 15+18z } ~ \text{ and } ~ z \in \mathbb{Z} & [~ \text{ or } ~x \equiv 15 \pmod{18} ] \\ \color{blue}(3) & \mathbf{ x} &=& \mathbf{ 17+25k } ~ \text{ and } ~ k \in \mathbb{Z} & [~ \text{ or } ~x \equiv 17 \pmod{25} ] \\\\ & 15+18z &=& 17+25k \\ & 18z &=& 2+25k \\ & \mathbf{z} &=& \mathbf{\dfrac{ 25k + 2 } {18}} \\ & z &=& \dfrac{18k+7k+2}{18} \\ & z &=& k+\underbrace{\dfrac{ 7k+2}{18}}_{=a} \\ & z &=& k+a & a = \dfrac{ 7k+2}{18} \\ & & & & 18a = 7k+2 \\ & & & & 7k = 18a-2 \\ & & & & k = \dfrac{18a-2}{7} \\ & & & & k = \dfrac{14a+4a-2}{7} \\ & & & & k = 2a+\underbrace{\dfrac{4a-2}{7}}_{=b} \quad | \quad \\ & & & & k = 2a+b & b = \dfrac{4a-2}{7} \\ & & & & & 7b = 4a-2 \\ & & & & & 4a = 7b+2 \\ & & & & & a = \dfrac{7b+2}{4} \\ & & & & & a = \dfrac{8b-b+2}{4} \\ & & & & & a = 2b+\underbrace{\dfrac{2-b}{4}}_{=c} \\ & & & & & a = 2b+c \qquad c = \dfrac{2-b}{4} \\ & & & & & \qquad\qquad \qquad 4c = 2-b \\ & & & & & \qquad \qquad \qquad \mathbf{b= 2-4c} \\ & & & & & a = 2(2-4c)+c \\ & & & & & \mathbf{a = 4-7c} \\ & & & & k = 2(4-7c)+ 2-4c \\ & & & & \mathbf{k = 10-18c} \\ & z &=& 10-18c+4-7c \\ &\mathbf{ z }&=& \mathbf{14-25c} \\ & x &=& 15+18z \\ & x &=& 15+18(14-25c) \\ & \mathbf{x} &=& \mathbf{267-450c} ~ \text{ and } ~ c \in \mathbb{Z} & [~ \text{ or } ~x \equiv 267 \pmod{450} ] \\ \hline \end{array}\)
The least positive four-digit solution:
\(\begin{array}{|rcll|} \hline 267-450c &>& 999 \\ -450c &>& 999-267 \\ -450c &>& 732 \quad & | \quad :(-450) \\ c &<& -\dfrac{732}{450} \\ c &<& -1.62666666667 \\ \hline \end{array}\)
\(\begin{array}{|rcll|} \hline x_{\text{4digit}} &=& 267 -450(-2) \\ x_{\text{4digit}} &=& 267 +900 \\ \mathbf{x_{\text{4digit}}} &=& \mathbf{1167} \\ \hline \end{array}\)
+26391 Find the least positive four-digit solution to the following system of congruences.
\(\begin{align*} 7x &\equiv 21 \pmod{14} \\ 2x+13 &\equiv 16 \pmod{9} \\ -2x+1 &\equiv x \pmod{25} \\ \end{align*}\)
\(\begin{array}{|lrcll|} \hline & \mathbf{7x} &\mathbf{\equiv}& \mathbf{ 21 \pmod{14}} \\ & 7x &\equiv& 21 -14 \pmod{14} \\ & 7x &\equiv& 7 \pmod{14} \\ & 7x &=& 7 +14n \quad & | \quad : 7 \\ \color{blue}(1) & \mathbf{ x} &=& \mathbf{ 1+2n } ~ \text{ and } ~ n \in \mathbb{Z}\qquad [~ \text{ or } ~x \equiv 1 \pmod{2} ] \\ \hline \end{array} \)
\(\begin{array}{|lrcll|} \hline & \mathbf{2x+13} &\mathbf{\equiv}& \mathbf{16 \pmod{9} } \\ & 2x & \equiv & 16 -13 \pmod{9} \\ & 2x & \equiv & 3 \pmod{9} \\ & 2x & = & 3 + 9m \\\\ & \mathbf{x } & = & \mathbf{\dfrac{3 + 9m}{2}} \\ & x &=& \dfrac{8m+m+2+1}{2} \\ & x &=& 4m+1+ \underbrace{\dfrac{ m+1}{2}}_{=a} \\ & x &=& 4m+1+ a & a = \dfrac{ m+1}{2} \\ & & & & 2a = m+1 \\ & & & & \mathbf{m =2a-1} \\ & x &=& 4(2a-1)+1+ a \\ & x &=& -3+9a \\ & x &\equiv& -3 \pmod{9} \\ & x &\equiv& -3+9 \pmod{9} \\ & x &\equiv& 6 \pmod{9} \\ \color{blue}(2) & \mathbf{ x} &=& \mathbf{ 6+9m } ~ \text{ and } ~ m \in \mathbb{Z} \\ \hline \end{array}\)
\(\begin{array}{|lrcll|} \hline & \mathbf{-2x+1} &\mathbf{\equiv}& \mathbf{x \pmod{25} } \\ & -2x+1 &=& x +25k \\ & -3x+1 &=& 25k \\ & 3x &=& 1-25k \\ & \mathbf{x } & = & \mathbf{\dfrac{1-25k}{3}} \\ & x &=& \dfrac{1-24k-k}{3} \\ & x &=& -8k +\underbrace{\dfrac{1-k}{3}}_{=a} \\ & x &=& -8k +a & a = \dfrac{1-k}{3} \\ & & & & 3a = 1-k \\ & & & & \mathbf{k =1-3a} \\ & x &=& -8(1-3a) +a \\ & x &=& -8+25a \\ & x &\equiv& -8 \pmod{25} \\ & x &\equiv& -8+25 \pmod{25} \\ & x &\equiv& 17 \pmod{25} \\ \color{blue}(3) & \mathbf{ x} &=& \mathbf{ 17+25k } ~ \text{ and } ~ k \in \mathbb{Z} \\ \hline \end{array}\)
The system of congruences is now:
\(\begin{array}{|rcll|} \hline \color{blue}(1) & \mathbf{ x} &=& \mathbf{ 1+2n } ~ \text{ and } ~ n \in \mathbb{Z}\qquad [~ \text{ or } ~x \equiv 1 \pmod{2} ] \\ \color{blue}(2) & \mathbf{ x} &=& \mathbf{ 6+9m } ~ \text{ and } ~ m \in \mathbb{Z}\qquad [~ \text{ or } ~x \equiv 6 \pmod{9} ] \\ \color{blue}(3) & \mathbf{ x} &=& \mathbf{ 17+25k } ~ \text{ and } ~ k \in \mathbb{Z}\qquad [~ \text{ or } ~x \equiv 17 \pmod{25} ] \\ \hline \end{array}\)
\(\begin{array}{|lrcll|} \hline \color{blue}(1) & \mathbf{ x} &=& \mathbf{ 1+2n } \\ \color{blue}(2) & \mathbf{ x} &=& \mathbf{ 6+9m } \\\\ & 1+2n &=& 6+9m \\ & 2n &=& 9m+5 \\ & \mathbf{ n } &=& \mathbf{\dfrac{ 9m+5 }{2}} \\ & n &=& \dfrac{8m+m+4+1}{2} \\ & n &=& 4m+2+\underbrace{\dfrac{ m+1}{2}}_{=a} \\ & n &=& 4m+2+a & a = \dfrac{ m+1}{2} \\ & & & & 2a = m+1 \\ & & & & \mathbf{m =2a-1} \\ & x &=& 6+9m \\ & x &=& 6+9(2a-1) \\ & x &=& -3+18a \\ & x &\equiv& -3 \pmod{18} \\ & x &\equiv& -3 +18\pmod{18} \\ & x &\equiv& 15 \pmod{18} \\ \color{blue}(4) & \mathbf{ x} &=& \mathbf{ 15+18z } ~ \text{ and } ~ z \in \mathbb{Z} \\ \hline \end{array} \)
The system of congruences is now:
\(\begin{array}{|lrcll|} \hline \color{blue}(4) & \mathbf{ x} &=& \mathbf{ 15+18z } ~ \text{ and } ~ z \in \mathbb{Z} & [~ \text{ or } ~x \equiv 15 \pmod{18} ] \\ \color{blue}(3) & \mathbf{ x} &=& \mathbf{ 17+25k } ~ \text{ and } ~ k \in \mathbb{Z} & [~ \text{ or } ~x \equiv 17 \pmod{25} ] \\\\ & 15+18z &=& 17+25k \\ & 18z &=& 2+25k \\ & \mathbf{z} &=& \mathbf{\dfrac{ 25k + 2 } {18}} \\ & z &=& \dfrac{18k+7k+2}{18} \\ & z &=& k+\underbrace{\dfrac{ 7k+2}{18}}_{=a} \\ & z &=& k+a & a = \dfrac{ 7k+2}{18} \\ & & & & 18a = 7k+2 \\ & & & & 7k = 18a-2 \\ & & & & k = \dfrac{18a-2}{7} \\ & & & & k = \dfrac{14a+4a-2}{7} \\ & & & & k = 2a+\underbrace{\dfrac{4a-2}{7}}_{=b} \quad | \quad \\ & & & & k = 2a+b & b = \dfrac{4a-2}{7} \\ & & & & & 7b = 4a-2 \\ & & & & & 4a = 7b+2 \\ & & & & & a = \dfrac{7b+2}{4} \\ & & & & & a = \dfrac{8b-b+2}{4} \\ & & & & & a = 2b+\underbrace{\dfrac{2-b}{4}}_{=c} \\ & & & & & a = 2b+c \qquad c = \dfrac{2-b}{4} \\ & & & & & \qquad\qquad \qquad 4c = 2-b \\ & & & & & \qquad \qquad \qquad \mathbf{b= 2-4c} \\ & & & & & a = 2(2-4c)+c \\ & & & & & \mathbf{a = 4-7c} \\ & & & & k = 2(4-7c)+ 2-4c \\ & & & & \mathbf{k = 10-18c} \\ & z &=& 10-18c+4-7c \\ &\mathbf{ z }&=& \mathbf{14-25c} \\ & x &=& 15+18z \\ & x &=& 15+18(14-25c) \\ & \mathbf{x} &=& \mathbf{267-450c} ~ \text{ and } ~ c \in \mathbb{Z} & [~ \text{ or } ~x \equiv 267 \pmod{450} ] \\ \hline \end{array}\)
The least positive four-digit solution:
\(\begin{array}{|rcll|} \hline 267-450c &>& 999 \\ -450c &>& 999-267 \\ -450c &>& 732 \quad & | \quad :(-450) \\ c &<& -\dfrac{732}{450} \\ c &<& -1.62666666667 \\ \hline \end{array}\)
\(\begin{array}{|rcll|} \hline x_{\text{4digit}} &=& 267 -450(-2) \\ x_{\text{4digit}} &=& 267 +900 \\ \mathbf{x_{\text{4digit}}} &=& \mathbf{1167} \\ \hline \end{array}\)
