How do I solve a linear Diophantine equation using back substitution?

Question

I'm a senior in high school taking a number theory class. I have read the other answers on this site about back substitution but frankly I do not understand them at all. I know that back substitution is a very iterative process so I'm just looking for a simple explanation and a clear example because I feel like once I get it I will be able to solve all future problem with it.

Here's the problem I am trying to solve:

Use the GCD, along with back substitution, to obtain integers $x$ and $y$ that satisfy this equation: $\gcd(143,227)=143x+227y$.

I've already found the GCD using the Euclidean Algorithm and now just need to understand back substitution. I tried writing the first equation: $1=11-(5)(2)$, where $1$ is the last nonzero remainder obtained with the Euclidean Algorithm and $5$ and $2$ are the quotient and divisor respectively (from the same division problem). I understand that the next step is to substitute but I don't really understand how. This is where I'm at and any help is greatly appreciated.

Thanks, Jake.

Answer 1

$$ 227=143+84 \\ 143=84+59 \\ 84=59+25 \\ 59=2\cdot25+9 \\ 25=2\cdot9+7 \\ 9=7+2 \\ 7=3\cdot2+1 \\ 2=2\cdot1+0 $$ So, $\gcd(227,143)=1$ and starting from the second line from the bottom (each time backsolving for the remainder from the previous line) we get: $$ 1=7-3\cdot2=7-3\cdot(9-7)=4\cdot7-3\cdot9= \\ =4\cdot(25-2\cdot9)-3\cdot9=4\cdot25-11\cdot9= \\ =4\cdot25-11\cdot(59-2\cdot25)=26\cdot25-11\cdot59= \\ =26\cdot(84-59)-11\cdot59=26\cdot84-37\cdot59= \\ =26\cdot84-37\cdot(143-84)=63\cdot84-37\cdot143=\\ =63\cdot(227-143)-37\cdot143=63\cdot227-100\cdot143 $$ so you end up with: $$ 1=63*227-100*143 $$ the last equation is called the Bezout's identity and the method of back-solving for reaching it, is usually called "the extended Euclidean algorithm".

Answer 2

Using the Euclidean Algorithm you should have found something like this $$\begin{array}{lll} 227 & = & 143\cdot 1 + 84\\ 143 & = & 84 \cdot 1 + 59\\ 84 & = & 59\cdot 1 + 25\\ 59 & = & 25\cdot 2 + 9\\ 25 & = & 9\cdot 2 + 7\\ 9 & = & 7\cdot 1 + 2\\ 7 & = & 2\cdot 3 + 1\\ \end{array} $$

So $\text{GCD}(227,143) = 1$. Now you have to do the back substitution. What does that mean? You have to use the equalities from the Euclidean Algorithm to reach your answer. This goes as follows:

From the last equality, we have that $1 = 7 - 2$. Then $2 = 9 - 7$, so the equation becomes $1 = 7 - (9 - 7)$. Then $7 = 25 - 9\cdot 2$, so $1 = 25 - 9\cdot 2 - (9 - (25 - 9\cdot 2))$, and so on. Finally, you should reach (do it!) $$\text{GCD}(227,143) = 1 = 63\cdot 227 - 100\cdot 143.$$

Answer 3

The thing that I am able to remember is continued fractions, which are easier than one might think. Here is the fraction for $227/143:$

$$ \small \begin{array}{cccccccccccccccccccccccccccccc} & & 1 & & 1 & & 1 & & 2 & & 2 & & 1 & & 3 & & 2 & \\ \frac{0}{1} & \frac{1}{0} & & \frac{1}{1} & & \frac{2}{1} & & \frac{3}{2} & & \frac{8}{5} & & \frac{19}{12} & & \frac{27}{17} & & \frac{100}{63} & & \frac{227}{143} & \end{array} $$ We see that $$ 100 \cdot 143 = 14300, $$ $$ 227 \cdot 63 = 14301, $$ $$ 227 \cdot 63 - 100 \cdot 143 = 1. $$