+247 Suppose that x is an integer that satisfies the following congruences:
\(\begin{align*} 3+x &\equiv 2^2 \pmod{3^3} \\ 5+x &\equiv 3^2 \pmod{5^3} \\ 7+x &\equiv 5^2 \pmod{7^3} \end{align*}\)
What is the remainder when x is divided by 105?
+26367 Suppose that x is an integer that satisfies the following congruences:
\(\begin{align*} 3+x &\equiv 2^2 \pmod{3^3} \\ 5+x &\equiv 3^2 \pmod{5^3} \\ 7+x &\equiv 5^2 \pmod{7^3} \end{align*}\)
What is the remainder when x is divided by 105?
\(\begin{array}{|lrcll|} \hline & \mathbf{3+x} &\mathbf{ \equiv } &\mathbf{ 2^2 \pmod{3^3} } \\ & x &\equiv & 2^2-3 \pmod{3^3} \\ (1) & \mathbf{x} &\mathbf{ \equiv } & \mathbf{ 1 \pmod{27} }\\ \hline \end{array}\)
\(\begin{array}{|lrcll|} \hline & \mathbf{5+x} &\mathbf{ \equiv } &\mathbf{ 3^2 \pmod{5^3} } \\ & x &\equiv & 3^2-5 \pmod{5^3} \\ (2) & \mathbf{x} &\mathbf{ \equiv } & \mathbf{ 4 \pmod{125} }\\ \hline \end{array}\)
\(\begin{array}{|lrcll|} \hline & \mathbf{7+x} &\mathbf{ \equiv } &\mathbf{ 5^2 \pmod{7^3} } \\ & x &\equiv & 5^2-7 \pmod{7^3} \\ (3) & \mathbf{x} &\mathbf{ \equiv } & \mathbf{ 18 \pmod{343} }\\ \hline \end{array}\)
The congruences are now:
\(\begin{array}{|lrcll|} \hline (1) & \mathbf{x} &\mathbf{ \equiv } & \mathbf{ 1 \pmod{27} } \\ (2) & \mathbf{x} &\mathbf{ \equiv } & \mathbf{ 4 \pmod{125} } \\ (3) & \mathbf{x} &\mathbf{ \equiv } & \mathbf{ 18 \pmod{343} } \\ \hline \end{array} \)
\(\begin{array}{|rclrclrcl|} \hline (1) \quad \mathbf{x} &\mathbf{ \equiv } & \mathbf{ 1 \pmod{27} } \\ x &=& 1 + 27 m, \ m\in \mathbb{Z} \\\\ (2)\quad \mathbf{x} &\mathbf{ \equiv } & \mathbf{ 4 \pmod{125} } \\ x &=& 4 + 125n, \ n\in \mathbb{Z} \\ \hline 1+27m &=& 4+125n \\ 27m &=& 3+125n \\ m &=& \dfrac{3+125n}{27} \\ m &=& \dfrac{135n+3-10n}{27} \\ m &=& 5n+ \underbrace{ \dfrac{3-10n}{27} }_{=a} \\ \mathbf{m} &=& \mathbf{ 5n+a } & a &=& \dfrac{3-10n}{27} \\ & & & 27a &=& 3-10n \\ & & & 10n &=& 3-27a \\ & & & n &=& \dfrac{3-27a}{10} \\ & & & n &=& \dfrac{-30a+3+3a}{10} \\ & & & n &=& \dfrac{-30a+3+3a}{10} \\ & & & n &=& -3a+ \underbrace{ \dfrac{3+3a}{10} }_{=b} \\ & & & \mathbf{n} &=& \mathbf{ -3a+b} & b &=& \dfrac{3+3a}{10} \\ & & & & & & 10b &=& 3+3a \\ & & & & & & 3a &=& 10b - 3\\ & & & & & & a &=& \dfrac{10b - 3}{3} \\ & & & & & & a &=& \dfrac{9b - 3 + b }{3} \\ & & & & & & a &=& 3b-1+ \underbrace{ \dfrac{ b }{3} }_{=c} \\ & & & & & & \mathbf{a} &=& \mathbf{3b-1+c} \qquad \mathbf{b=3c}\\ & & & & & & a &=& 3(3c)-1+c \\ & & & & & & \mathbf{a} &=& \mathbf{ 10c-1 } \\ & & & n &=& -3(10c-1) +3c \\ & & & \mathbf{n} &=& \mathbf{ 3-27c } \\ m &=& 5(3-27c )+10c-1 \\ \mathbf{ m} &=& \mathbf{ 14-125c} \\\\ x &=& 1+27m \\ x &=& 1+27(14-125c) \\\\ (4) \quad \mathbf{x} &=& \mathbf{ 379-3375c} \\ \text{or} \mathbf{ x }&=& \mathbf{ 379 \pmod{3375}} \\ \hline \end{array}\)
The congruences are now:
\(\begin{array}{|lrcll|} \hline (4) & \mathbf{ x }&=& \mathbf{ 379 \pmod{3375}} \\ (3) & \mathbf{x} &\mathbf{ \equiv } & \mathbf{ 18 \pmod{343} } \\ \hline \end{array}\)
\(\small{ \begin{array}{|rclrclrcl|} \hline (4) \quad \mathbf{x} &\mathbf{ \equiv } & \mathbf{ 379 \pmod{3375} } \\ x &=& 379 -3375 m, \ m\in \mathbb{Z} \\\\ (3)\quad \mathbf{x} &\mathbf{ \equiv } & \mathbf{ 18 \pmod{343} } \\ x &=& 18 + 343n, \ n\in \mathbb{Z} \\ \hline 379 -3375 m &=& 18 + 343n \\ 343n &=& 361 -3375 m \\ n &=& \dfrac{361 -3375m}{343} \\ n &=& \dfrac{-3430m+343 +55m +18 }{343} \\ n &=& -10m+1+\underbrace{\dfrac{ 55m+18 }{343}}_{=a} \\ \mathbf{n} &=& \mathbf{-10m+1+a } & a &=& \dfrac{55m+18 }{343} \\ & & & 343a &=& 55m+18 \\ & & & 55m &=& 343a-18 \\ & & & m &=& \dfrac{343a-18}{55} \\ & & & m &=& \dfrac{330a+13a-18}{55} \\ & & & m &=& 6a+\underbrace{\dfrac{13a-18}{55}}_{=b} \\ & & & m &=& 6a+b & b &=& \dfrac{13a-18}{55} \\ & & & & & & 55b &=& 13a-18 \\ & & & & & & 13a &=& 55b+18\\ & & & & & & a &=& \dfrac{55b+18}{13} \\ & & & & & & a &=& \dfrac{52b+13+5+3b}{13} \\ & & & & & & a &=& 4b+1+\underbrace{\dfrac{5+3b}{13} }_{=c} \\ & & & & & & a &=& 4b+1+c & c &=& \dfrac{5+3b}{13} \\ & & & & & & & & & 13c &=& 5+3b \\ & & & & & & & & & 3b &=& 13c -5 \\ & & & & & & & & & b &=& \dfrac{13c -5}{3} \\ & & & & & & & & & b &=& \dfrac{12c-3+c-2}{3} \\ & & & & & & & & & b &=& 4c-1+\underbrace{\dfrac{c-2}{3}}_{=d} \\ & & & & & & & & & \mathbf{b} &=& \mathbf{4c-1+d} \qquad \mathbf{c=2+3d}\\ & & & & & & & & & b &=& 4(2+3d)-1+d \\ & & & & & & & & & \mathbf{b} &=& \mathbf{13d+7} \\ & & & & & & a &=& 4(13d+7)+1+2+3d \\ & & & & & & \mathbf{a} &=& \mathbf{31+55d} \\ & & & m &=& 6(31+55d)+13d+7 \\ & & & \mathbf{m} &=& \mathbf{343d+193}\\ n &=& -10(343d+193) +1+31+55d \\ \mathbf{n} &=& \mathbf{ -3375d-1898 } \\\\ x &=& 18 + 343n \\ x &=& 18 + 343(-3375d-1898 ) \\ x &=& 18-343\cdot 1898- 343\cdot 3375d \\ x &=& -650996 -1 157 625 d \\\\ x &\equiv & -650996 \pmod{1 157 625} \\ x &\equiv & -650996+1 157 625 \pmod{1 157 625} \\ x &\equiv & 506629 \pmod{1 157 625} \\\\ x &=& 506629 + 1 157 625z,\ z\in\mathbb{Z} \quad | \quad 1 157 625 = 3^35^37^3 \\ x &=& 506629 + 3^35^37^3z \\ \hline \end{array} }\)
What is the remainder when x is divided by 105?
\(105 = 3*5*7\)
\(\begin{array}{|rcll|} \hline &&\mathbf{ x \pmod{3*5*7}} \\ &\equiv & 506629 + 3^35^37^3z \pmod{3*5*7} \\ & \equiv & 506629\pmod{3*5*7} + 3^35^37^3z \pmod{3*5*7} \\ & \equiv & 4+ 0 \pmod{3*5*7} \\ & \mathbf{\equiv} & \mathbf{ 4 \pmod{3*5*7} } \\ & \mathbf{\equiv} & \mathbf{ 4 \pmod{105} } \\ \hline \end{array}\)
The remainder is 4 when x is divided by 105
+118608 Hi Heureka,
I have been learning from some of your modular arithemtic answers. I thank you for providing them.
I looked at this one and thought there should be an easier method.
This is what I came up with. Perhaps you could take a look and if you find fault with my logic then let me know.
\(\begin{align*} 3+x &\equiv 2^2 \pmod{3^3} \\ 5+x &\equiv 3^2 \pmod{5^3} \\ 7+x &\equiv 5^2 \pmod{7^3} \end{align*}\)
\(3+x\equiv 4 \quad \pmod{3^3}\\ x\equiv 1 \quad \pmod{3^3}\\ so\\ x\equiv 1 \quad \pmod{3}\\ x=1+3m\qquad \qquad (1) \)
\(5+x\equiv 9 \quad \pmod{5^3}\\ x\equiv 4 \quad \pmod{5^3}\\ x\equiv 4 \quad \pmod{5}\\ x\equiv -1 \quad \pmod{5}\\ x=-1+5n\qquad \qquad (2)\)
\(7+x\equiv 25 \quad \pmod{7^3}\\ x\equiv 18 \quad \pmod{7^3}\\ x\equiv 18 \quad \pmod{7}\\ x\equiv 4 \quad \pmod{7}\\ x=4+7k\qquad \qquad (3)\)
Solve the first 2 simultaneously
\(1+3m=-1+5n\\ 2=5n-3m\\ \text{One obvious solution for this is n=1 and m=1}\\ 2=5(1)-3(1)\\ \text{now I can add 15f and take it away again to get the general diophantine solution.}\\ 2=5(1+3f)-3(1+5f)\\ n=1+3f\\ x=-1+5n\\ x=-1+5(1+3f)\\ x=4+15f\\ \)
I could work it out with m instead of n but x in terms of f will be the same.
So now I have
\(x=4+7k \quad (3) \qquad and \qquad x=4+15f\\ \text{since }\\x\equiv 4 \pmod{7}\qquad and\\ x\equiv4\pmod{15}\\ \text{It follows that}\\ x\equiv 4 \pmod{7*15}\\ x\equiv 4 \pmod{105}\\ \)
So when x is divided by 105 the remainder is 4
