The Ultimate Crash Course for STEM Majors number theory and Euclidean Algorithm free preview

Using the Euclidean Algorithm Backwards – Finding Integers x and y in a Linear Diophantine Equation

This page is nothing more than a free preview of The Ultimate Crash Course for STEM Majors. This number theory example uses the Euclidean Algorithm backwards to find integers \(x\) and \(y\) satisfying the linear Diophantine equation \(875x+4075y=50\).

Explore The Ultimate Crash Course for STEM Majors | Explore My Fiction at AuthorJond.com

Question 2. Use your solution from Question 1 to find integers \(x\) and \(y\) such that \(875x+4075y=50\).

Theorem 4. If \((a,b)=d\), then there are integers \(x\) and \(y\) such that \[ ax+by=d. \]

From Q1

\[ \begin{aligned} 4075 &= 4(875)+575\\ 875 &= (575)(1)+300\\ 575 &= (300)(1)+275\\ 300 &= 275(1)+25\\ 300 &= 25(12)+0. \end{aligned} \]

It is suggested to work ‘The Euclidean Algorithm’ backwards.

Then,

\[ 300=25(12)+0 \]

\[ \Rightarrow 300=275(1)+25 \]

\[ \Rightarrow 300-275(1)=25 \]

\[ \Rightarrow [875-(575)(1)]-[575-(300)(1)]=25 \]

\[ \Rightarrow [875-(575)(1)]-[(4075-(4)(875))-(300)(1)]=25 \]

[Note* Get all terms to be original terms 875, 4075]

\[ \Rightarrow [875-(575)(1)]-[(4075-(4)(875))-(875-(575)(1))]=25 \]

\[ \Rightarrow 875-(575)(1)-(4075-(4)(875))+(875-(575)(1))=25 \]

\[ \Rightarrow 875-(575)(1)-4075+(4)(875)+875-(575)(1)=25 \]

\[ \Rightarrow {\color{#b020a0}{-4075+(6)(875)}}-(575)(2)=25 \]

\[ \Rightarrow -4075+(6)(875)-(4075-(4)(875))(2)=25 \]

\[ \Rightarrow -4075+(6)(875)-4075(2)+(8)(875)=25 \]

\[ \Rightarrow (14)(875)+4075(-3)=25 \]

\[ \Rightarrow (875)(28)+4075(-6)=50. \]

\[ \therefore x=28,\qquad y=-6. \]

Question 3.

Continue The Ultimate Crash Course for STEM Majors

This lesson is nothing more than a free preview of The Ultimate Crash Course for STEM Majors. Continue with the Crash Course series for additional worked examples in number theory, algebra, calculus, differential equations, mathematics, physics, engineering, and other STEM subjects.

Looking for something outside of STEM? Visit AuthorJond.com to explore my fiction, books, stories, podcasts, and other writing.

Get The Ultimate Crash Course for STEM Majors | Explore My Fiction at AuthorJond.com