+0

0
315
1
+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?

Aug 4, 2020

#1
+26222
+3

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}$$

Aug 5, 2020
edited by heureka  Aug 5, 2020
edited by heureka  Aug 5, 2020
edited by heureka  Aug 5, 2020