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

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.

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

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

$$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".

• Thank you. Where does the 4 come from in 4*7-3*9? – Jake Sep 14 '16 at 3:30
• $7-3*(9-7)=7-3*9+3*7=4*7-3*9$ – KonKan Sep 14 '16 at 3:31
• I'm sorry for just not seeing this, but why is 4 being multiplied by 7-3 if 7-3 was already simplified to 4? – Jake Sep 14 '16 at 3:43
• in each step of the extended Euclidean algorithm you express 1 as the linear combination of the two preceding remainders. I never said that $4$ is multiplied by $7-3$. Look carefully at my previous comment. – KonKan Sep 14 '16 at 3:48