+421 How do you work out what y and z are if x=y (mod z), where 7x+1=0 mod 3, x=0 mod 2, without guessing and checking, and finding the LCM?
+26388 How do you work out what y and z are if x=y (mod z), where 7x+1=0 mod 3, x=0 mod 2,
without guessing and checking, and finding the LCM?
\(\begin{array}{|lrcll|} \hline & 7x+1 &\equiv& 0 \pmod{ 3 } & \text{or} \\ & 7x+1 &=& 0 + 3n,\ n\in \mathbb{Z} \\ & 7x+1 &=& 3n \\ (1) & \mathbf{7x} &=& \mathbf{3n-1} \\ \hline & x &\equiv& 0 \pmod{ 2 } & \text{or}\\ & x &=& 0 + 2m,\ m\in \mathbb{Z} \\ & x &=& 2m \quad | \quad *7 \\ (2) & \mathbf{7x} &=& \mathbf{14m} \\ \hline & \mathbf{7x} = 3n-1 &=& 14m \\ & 3n-1 &=& 14m \\ (3) & \mathbf{3n-14m} &=& \mathbf{1} \\ \hline \end{array} \)
The Euler Method: Source see: https://www.math.nyu.edu/faculty/hausner/euler.pdf
\(\mathbf{3n-14m=1}\qquad\) Take this equation modulo 3 ( the smallest coefficient ).
\(\begin{array}{|rcll|} \hline \mathbf{3n-14m} &=& \mathbf{1} \\ && \text{Take this equation modulo $3$ ( the smallest coefficient )}. \\ \text{This yields} \\ 3n &=& 14m+1 \\ n &=& \dfrac{14m+1}{3} \\ n &=& \dfrac{15m-m+1}{3} \\ n &=& 5m+\dfrac{1-m}{3} \\ \text{We get } \mathbf{n} &=& \mathbf{5m+a},\ \text{where $\mathbf{a}$ is a new variable } \\ \hline a &=& \dfrac{1-m}{3} \\ 3a &=& 1-m \\ \mathbf{m} &=& \mathbf{1-3a} \qquad \text{( we have finished, no fraction there )}\\ \hline \text{Now go back to the} \\ \text{"x" equation (2) to get } \mathbf{x}&=&\mathbf{2m}. \\ x &=& 2(1-3a) \\ x &=& 2-6a \qquad \text{or} \\ \mathbf{x} &\equiv& \mathbf{2 \pmod{6}}\quad | \quad (x=y \pmod{z}) \\ \hline y=2,\ z=6 \\ \hline \end{array}\)
