1
$\begingroup$

Apply the Extended Euclidean Algorithm of back-substitution to find the value of $\gcd(85, 45)$ and to express $\gcd(85, 45)$ in the form $85x + 45y$ for a pair of integers $x$ and $y$.

I have no idea what is the difference between the regular EEA and the back-substitution EEA. The only thing that I have been taught is constructing the EEA table, for some values a, b. Can anyone help me explain this? Thanks a ton!

$\endgroup$
2
$\begingroup$

You’re probably intended to do the substitutions explicitly. You have

$$\begin{align*} 85&=1\cdot45+40\\ 45&=1\cdot40+5\\ 40&=8\cdot5\;. \end{align*}$$

Now work backwards:

$$\begin{align*} 5&=1\cdot45-1\cdot40\\ &=1\cdot45-1\cdot(1\cdot85-1\cdot45)\\ &=(-1)\cdot85+2\cdot45\;. \end{align*}$$

The tabular method is just a shortcut for this explicit back-substitution.

$\endgroup$
0
$\begingroup$

The terminology in the OP is confusing, but I want to take advantage of this post to go over the steps involved in the Euclidean algorithm vis-a-vis the extended Euclidean algorithm to make the process less dependent on mechanics and memorization:


Euclidean algorithm:

Used to find the greatest common divisor of two integers, i.e. $\gcd(a,b).$ It is based on the fact that the remainder of $\frac a b,$ shares the same $\gcd$ with $b$ as $\gcd(a,b),$ which is to say that if $$a=b\times q + r\tag{*}$$ then $\gcd(a,b)=\gcd(b,r).$ If this gcd is $d=\gcd(a,b)=\gcd(b,r),$ which can be seen by realizing that $d$ will divide the reorganized equation $(*)$ as $r=a - b\times q,$ because $d$ divides $a$ and $b$ independently, and it will therefore also divide $b$ multiplied by any other integer.

We want the $\gcd(\color{blue}{85},\color{magenta}{45}),$ which as shown below, is the same as $\gcd(\color{magenta}{45},\color{red}{40}),$ at which point we are done because the next iteration has a remainder of $0.$

$$\begin{align} \frac{\color{blue}{85}}{\color{magenta}{45}}=\color{tan}1{\small\text{, Rm }}\color{red}{40} \implies\, &\underbrace{\color{blue}{85}}_a\;(1) = \underbrace{\color{magenta}{45}}_b(\underbrace{\color{tan}1}_q) + \underbrace{\color{red}{40}}_r \tag 1 \\[2ex] \frac{\color{magenta}{45}}{\color{red}{40}}=\color{tan}{1} {\small\text{, Rm }}\color{purple}{5} \implies&\, \color{magenta}{45}\quad(1) = \color{red}{40}(\color{tan}{1}) + \bbox[5px,border:2px solid red]{ \color{gray}{\bf 5}} \tag 2 \\[2ex] \frac{\color{red}{40}}{\color{gray}{5}}=\color{tan}{8} {\small\text{, Rm }}\color{orange}{0} \implies&\, \color{red}{40}\quad(1) = \color{gray}{5}(\color{tan}8) + \color{orange}0 \end{align}$$

Hence, $\gcd(85,45)=5,$ i.e. the last remainder before the iteration producing a remainder $0.$


Extended Euclidean Algorithm:

However, the same algorithm can be extended to solve a linear Diophantine equation of the form:

$$a\,x+ b\,y=\gcd(a,b)$$

which are guaranteed to have an integer solution by Bézout's identity. This comes really handy in finding the private key of a system of modular inverses in RSA encryption.

In the case of the OP, we want to solve an integer linear relation of the form

$$\color{blue}{85}\, x + \color{magenta}{45}\, y=\bbox[5px,border:2px solid red]{ \color{gray}{\bf 5}} $$

using the work done in the Euclidean algorithm.

The process starts off with a simple rearrangement of the two equations above before the line with remainder $0$ with the intention of moving all the remainders to the RHS of the equation:

$$\begin{align} \bbox[5px,border:2px solid tan]{\color{blue}{85}(1) - \color{magenta}{45}(\color{tan}1)} &= \color{red}{40} \tag 1 \\[2ex] \color{magenta}{45}(1) - \color{red}{40}(\color{tan}{1}) &= \bbox[5px,border:2px solid red]{ \color{gray}{\bf 5}} \tag 2 \end{align} $$

Organized this way, it is clear that what we want on the LHS of the equation is boxed in tan on the LHS of the reorganized equation $(1),$ while what we want to see on the RHS of the linear equation lies on RHS of the last equation, corresponding to the $\gcd(85,45)=5,$ boxed in a red frame in the reorganized equation $(2).$

Now the trick is to simply back-substitute stepwise from bottom to top in the second set of reorganized equations the values of the remainders given by the different equation. In this case it is simply limited to a step: replacing $\color{red}{40}$ in equation $(2)$ by its value as it appears in equation $(1):$

$$\begin{align} \color{magenta}{45}(1) - \left(\;\bbox[5px,border:2px solid tan]{\color{blue}{85}(1) - \color{magenta}{45}(\color{tan}1)}\;\right) (\color{tan}{1}) &= \bbox[5px,border:2px solid red]{ \color{gray}{\bf 5}} \tag 2 \end{align} $$

This single step is more typically a chained process of consecutive substitutions to telescope into one the system of equations so that we have on both sides the desired integers.

Now it is just a matter of accounting:

$$\begin{align} \color{magenta}{45}(1) - \color{blue}{85}(1)(\color{tan}{1}) + \color{magenta}{45}(\color{tan}1)(\color{tan}{1}) &= \color{gray}{\bf 5} \\[2ex] \color{blue}{85}(-1) + \color{magenta}{45}(2) &= \color{gray}{\bf 5} \end{align} $$

to get to the solution $x=-1,$ and $y=2.$


Here is a more substantial example that happens to be solved in matrix form here, using $a = 1239$ and $b=735$ to find the gcd and solve the linear relation $ax + by = \gcd(a, b).$

Euclidean algorithm:

$$\begin{align} 1239 &= 735(1) + 504\\ 735 &= 504(1) + 231\\ 504 &= 231(2) + 42\\ 231 &= 42(5) + \bbox[5px,border:2px solid red]{21}\to \gcd(1239,735)\\ 42 &= 21(2) + 0 \end{align}$$

EEA:

$$\begin{align} 504 &= 1239 - 735(1) \\ 231 &= 735 - 504(1) \\ 42 &= 504 - 231(2) \\ 21 &= 231 - 42(5) \end{align}$$

Backsubstitution:

$$ \begin{align} 21 &= 231 - 42(5)\\ &= 231 - [504 - 231(2)](5)\\ &= 231 - 504(5) + 231(10)\\ &= 231(11) + 504(-5)\\ &= [735 - 504(1)](11) + 504(-5)\\ &= 735(11) + 504(-16)\\ &= 735(11) + [1239 - 735(1)](-16)\\ &= 735(11) + 1239(-16) - 735(-16)\\ &= 1239(-16) + 735(27) \end{align} $$

$\endgroup$
0
$\begingroup$

The method here is the back-substitution, but the organization highlights the logic. It can be done on paper but is really easy using the wonders of copy-paste-edit-latex technology.

$\tag 1 [40] = [85] - [45] \,1$ $\tag 2 [05] = [45] - [40] \,1$ $\tag ! [00] = [40] - [05] \,8 $ $\text{ >>> Remove [] from lhs of (2) and work the substitution/simplify algebra in reverse:}$ $\tag 2 5 = [45] - [40] \,1 $ $\tag 1 5 = [45] - [[85] - [45] \,1] \,1 = [85](-1) + [45](2)$

For practice, here is another one:

Write $\text{gcd}(80,62) = 80 x + 62 y$ with integers $x$ and $y$. $\tag 1 [18] = [80] - [62] \,1$ $\tag 2 [08] = [62] - [18] \,3$ $\tag 3 [02] = [18] - [08] \,2 $ $\tag ! [00] = [08] - [02] \,4 $ $\text{ >>> Remove [] from lhs of (3) and work substitution/simplify algebra in reverse:}$ $\tag 3 2 = [18] - [08] \,2 $ $\tag 2 2 = [18] - [[62] - [18] \,3] \,2 = [18]\,7 - [62]\,2$ $\tag 1 2 = [[80] - [62] \,1]\,7 - [62]\,(2) = [80] \,(7) +[62]\,(-9) $

$\endgroup$

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.