+78 Solve the linear Diophantine equation 11x - 13y = 1 using Euclid's algorithm.
I did this:
First, start with Euclid's algorithm.
13/11
13 = 11(1) + 2
2 = 13(1) + 11(-1)
11/2
11 = 2(5) + 1
1 = 11(1) + 2(-5)
Ok, now we go onto substituting, etc.
The 2 can be substituted.
1 = 11(1) + 13(1) + 11(-1)
Simplify.
1 = 11(7) + 13(-5)
But 77 - 65 is not 1, which means my answer is wrong. How should I fix it?
+26367 Solve the linear Diophantine equation 11x - 13y = 1 using Euclid's algorithm.
\(\begin{array}{|rcll|} \hline 11x-13y=1 \\ \mathbf{11x+(-13)y=1} \\ \text{Euclid's Algorithm} &&&\text{remainder}\\ \hline -13 &=& -1\times11-2 & -2 = -13+11 \\ 11 &=& -5\times(-2)+1 & 1 =11+5\times(-2) \\ -2 &=& -2\times 1+0 \qquad \text{stop} \\ \hline \end{array} \)
\(\begin{array}{|rcll|} \hline \text{backwards substitution} \\ \hline 1 &=& 11+5\times(-2) \quad & | \quad -2=-13+11 \\ 1 &=& 11+5\times(-13+11) \\ 1 &=& 11+5\times(-13) +5\times+11 \\ 1 &=& 6\times 11+5\times(-13) \\ \hline x=6 && y=5 \\ &\text{check}& \\ 11\times 6 +5\times(-13) &=& 1\\ 66-65 &=& 1 \ \checkmark \\ \hline \end{array} \)
