0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you. Where does the 4 come from in 4*7-3*9? $\endgroup$ – Jake Sep 14 '16 at 3:30
  • $\begingroup$ $7-3*(9-7)=7-3*9+3*7=4*7-3*9$ $\endgroup$ – KonKan Sep 14 '16 at 3:31
  • $\begingroup$ 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? $\endgroup$ – Jake Sep 14 '16 at 3:43
  • $\begingroup$ 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. $\endgroup$ – KonKan Sep 14 '16 at 3:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.