+0  
 
0
73
2
avatar+80 

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.

 Aug 2, 2020
 #1
avatar
0

The Euclidean algorithm gives the solution (x,y) = (-30,133).  You can check that 164(-30) + 37(133) = 1.

 Aug 2, 2020
 #2
avatar+25543 
+2

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} \)

 

laugh

 Aug 3, 2020

61 Online Users

avatar
avatar
avatar
avatar