+81 Use the Euclidean algorithm to find integers x and y such that 164x + 37y = 1. State your answer as a list with x first and y second, separated by a comma.
The Euclidean algorithm gives the solution (x,y) = (-30,133). You can check that 164(-30) + 37(133) = 1.
+26388 Use the Euclidean algorithm to find integers x and y such that 164x + 37y = 1.
State your answer as a list with x first and y second, separated by a comma.
\(\begin{array}{|lrclcrcl|c|} \hline \text{Euclidean algorithm}& &&&& && \text{Remainder} &\text{Remainder} \\ 164x + 37y = 1 \\ \hline & 164 &:& 37 &=& 4*37 &+& 16 & \mathbf{16} = 164-4*37 \\ & 37 &:& 16 &=& 2*16 &+& 5 & \mathbf{5}=37-2*16 \\ & 16 &:& 5 &=& 3*5 &+& 1 & \mathbf{1=16-3*5} \\ \hline \end{array}\)
\(\begin{array}{|rcll|} \hline \mathbf{1} &=& \mathbf{16-3*5} \quad | \quad \mathbf{5}=37-2*16 \\ 1 &=& 16-3*(37-2*16) \\ 1 &=& 16-3*37+6*16 \\ 1 &=& 7*16-3*37 \quad | \quad \mathbf{16} = 164-4*37 \\ 1 &=& 7*(164-4*37) -3*37 \\ 1 &=& 7*164-28*37 -3*37 \\ \mathbf{1} &=& \mathbf{\mathbf{\color{red}7}*164\mathbf{\color{red}-31}*37} \\ \hline \end{array}\)
\(\mathbf{x=7,\ y=-31} \)
