We use cookies to personalise content and advertisements and to analyse access to our website. Furthermore, our partners for online advertising receive pseudonymised information about your use of our website. cookie policy and privacy policy.
 
+0  
 
0
66
3
avatar+97 

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?

 Jun 12, 2019
 #1
avatar+22357 
+5

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 

 

laugh

 Jun 13, 2019
 #2
avatar+97 
+2

Thank you!

power27  Jun 13, 2019
 #3
avatar+101769 
+2

Hi Heureka,

I have been learning from some of your modular arithemtic answers. I thank you for providing them.  laugh

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

 Jun 18, 2019

8 Online Users

avatar