1
$\begingroup$

From the book Discrete Mathematics for Computing 2nd Edition in eBook:

enter image description here

I know how to perform the Euclidean Algorithm and GCM(a,b). I am however, deeply confused by this:

$$1 = 415 - 69(421 - 1 \times 415)$$ $$ = 70 \times 415 - 69 \times 421$$


How is this expression constructed $70 \times 415 - 69 \times 421$?


N.B. I am still new to this and learning, I am using the following book(s):

Discrete Mathematics for Computing / Edition 2
by Peter Grossman [eBook]

Discrete Mathematics for Computing / Edition 3
by Peter Grossman [Physical copy]
$\endgroup$
19
  • 6
    $\begingroup$ Count how many $415$s are in that expression. (Answer: $1+69$.) $\endgroup$
    – Randall
    Commented Mar 13 at 18:13
  • 3
    $\begingroup$ $415-69(-1\times415)=(1-(-69))(415)=70\times415$ $\endgroup$ Commented Mar 13 at 18:14
  • 2
    $\begingroup$ You combine the $415$ terms and separate them from the $421$ term $\endgroup$ Commented Mar 13 at 18:24
  • 2
    $\begingroup$ Imagine if it was $x-69(y-x)$. Can you see how that equals $70x-69y$? $\endgroup$
    – Malady
    Commented Mar 13 at 19:47
  • 3
    $\begingroup$ Wow. A fifty point bounty for a canonical explanation for a line or two of elementary high school algebra. That should attract lots of identical answers. $\endgroup$ Commented Mar 16 at 15:47

3 Answers 3

3
+50
$\begingroup$

How is this expression constructed $70 \times 415 - 69 \times 421$?

Using colors might be helpful.

$$\begin{align}1& = \color{red}{415} - 69(\color{blue}{421} - 1 \times \color{red}{415}) \\\\&=\color{red}{415} - 69\times \color{blue}{421} +69 \times\color{red}{415} \\\\&=\color{red}{415}+69 \times \color{red}{415} - 69\times \color{blue}{421} \\\\&=(1+69)\times \color{red}{415}- 69\times \color{blue}{421} \\\\&=70 \times \color{red}{415} - 69 \times \color{blue}{421}\end{align}$$


To get a solution $(x,y)$ of the equation $\color{purple}{2093}x+\color{orange}{836}y=1$, they started with $$\color{blue}{421}=\color{purple}{2093}-2\times \color{orange}{836}\tag1$$ $$\color{red}{415}=\color{orange}{836}-1\times \color{blue}{421}\tag2$$ $$\color{green}6=\color{blue}{421}-1\times \color{red}{415}\tag3$$ $$1=\color{red}{415}-69\times \color{green}6\tag4$$

They have $$\begin{align}1&=\color{red}{415}-69\times \color{green}6 \\\\&=\color{red}{415}-69\times (\color{blue}{421}-1\times \color{red}{415}) \\\\&=70 \times \color{red}{415} - 69 \times \color{blue}{421} \\\\&=70 \times (\color{orange}{836}-1\times \color{blue}{421})- 69 \times \color{blue}{421} \\\\&=70\times \color{orange}{836}-139\times \color{blue}{421} \\\\&=70\times \color{orange}{836}-139\times (\color{purple}{2093}-2\times \color{orange}{836}) \\\\&=\color{purple}{2093}\times (-139)+\color{orange}{836}\times 348\end{align}$$

Therefore, $(x,y)=(-139,348)$ is a solution of the equation $\color{purple}{2093}x+\color{orange}{836}y=1$.

$\endgroup$
6
  • $\begingroup$ How do you go from: $= 415 - 69 \times 421 + 69 \times 415$ to $= 415 + 69 \times 415 - 69 \times 421$ and from this to: $= (1 + 69) \times 415 - 69 \times 421$ ? I don't understand the steps and transitions that's happening there! $\endgroup$ Commented Mar 17 at 7:32
  • $\begingroup$ @Alix Blaine : Since we have that $A-B+C$ is equal to $A+C-B$, setting $A=415,B=69\times 421$ and $C=69\times 415$ gives $$415−69×421+69×415$$$$=415+69×415−69×421$$ Next, since we have that $E\times D+F\times D-G$ is equal to $(E+F)\times D-G$, setting $D=415,E=1,F=69$ and $G=69\times 421$ gives $$415+69×415−69×421$$$$=1\times 415+69\times 415-69\times 421$$$$=(1+69)\times 415-69\times 421$$ $\endgroup$
    – mathlove
    Commented Mar 17 at 8:04
  • $\begingroup$ So you are doing some re-writing? $\endgroup$ Commented Mar 17 at 9:35
  • $\begingroup$ Any link where I can learn about this? $\endgroup$ Commented Mar 17 at 9:36
  • 1
    $\begingroup$ @Alix Blaine : "you are doing some re-writing?" Yes, I am. "Any link where I can learn about this?" You might want to see this. "How to you arrive here: $1×415+69×415−69×421$" Since we have that $A+B−C$ is equal to $1×A+B−C$ (just rewriting $A$ as $1\times A$), setting $A=415,B=69×415$ and $C=69×421$, we have $$415+69×415−69×421$$ $$=1×415+69×415−69×421$$ $\endgroup$
    – mathlove
    Commented Mar 17 at 14:27
2
$\begingroup$

You already brought up the Euclidean algorithm. For $n,m\in\mathbb{Z}$ with $\operatorname{gcd}(n,m)=1$ you get from "reversing" the algorithm an expression of $1=an+bm$.

Example:

$\operatorname{gcd}(13,23)=1$.

We have

$23=1\cdot 13+10$

$13=1\cdot 10+3$

$10=3\cdot 3+1$

Now use the last equation to get an expression in $1$ and substitute into the other equations to express this in terms of $23$ and $13$.

So $1=10-3\cdot 3$.

Now $13=1\cdot 10+3\Leftrightarrow 3=13-10$ (we solve for the "remainder" for the substitution)

Now plug this in for $3$.

$1=10-3\cdot (13-10)=10-3\cdot 13+3\cdot 10=4\cdot 10-3\cdot 13$.

Proceed and solve the first equation for $10$.

$10=23-13$.

Plug this in:

$1=4(23-13)-3\cdot 13=4\cdot 23-4\cdot 13-3\cdot 13=4\cdot 23-7\cdot 13$.

$\endgroup$
1
$\begingroup$

As far as I see, the calculations from the quotation concern to construct an integer solution $(x,y)$ of the Diophantine equation $2093x+836y=1$. To do this, we apply first the Euclidean algorithm to find the greatest common divisor to numbers $r_1=2093$ and $r_2=836$ and then go backwards. Namely, the Euclidean algorithm yields:

$r_3=421=2093-2\times 836=r_1-2\times r_2$

$r_4=415=836-1\times 421=r_2-1\times r_3$

$r_5=6=421-1\times 415=r_3-1\times r_4$

$r_6=1=415-69\times 6=r_4-69\times r_5$.

Next we go backwards:

$1=r_6=r_4-69\times r_5=415-69\times 6$

$1=r_4-69\times r_5=r_4-69\times (r_3-1\times r_4)=-69\times r_3+70\times r_4=-69\times 421+70\times 415$

$1=-69\times r_3+70\times r_4=-69\times r_3+70\times (r_2-1\times r_3)=70\times r_2-139\times r_3=70\times 836-139\times 421$

$1=70\times r_2-139\times r_3=70\times r_2-139\times (r_1-2\times r_2)=-139\times r_1+348\times r_2=-139\times 2093+348\times 836$

That is we constructed an integer solution $(x,y)=(-139,348)$ of the equation $2093x+836y=1$.

$\endgroup$
5
  • $\begingroup$ Hi, I am super confused by $r_n$ in your examples. $\endgroup$ Commented Mar 16 at 11:06
  • $\begingroup$ Can you simplify this with those numbers from the book example? $\endgroup$ Commented Mar 16 at 11:07
  • 1
    $\begingroup$ @AlixBlaine The $r_n$'s are consecutive remainders of the Euclidean algorithm. They are used to indicate what is going on. Yes, we can skip them, but then the calculations will become a distributivity exercise. :-) $\endgroup$ Commented Mar 16 at 11:23
  • $\begingroup$ What do you mean by "a distributivity exercise"? $\endgroup$ Commented Mar 16 at 11:27
  • 1
    $\begingroup$ @AlixBlaine A sequence of arithmetic transformations, based on the distributive law, for instance: $1=415-69\times 6=415-69\times (421-415)=-69\times 421+70\times 415= -69\times 421+70\times (836-1\times 421)=70\times 836-139\times 421= 70\times 836-139\times (2093-2\times 836)=-139\times 2093+348\times 836.$ I think, this does not explain a lot what is going on and from where we obtained the respective numbers. $\endgroup$ Commented Mar 16 at 11:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .