Loading [MathJax]/jax/element/mml/optable/BasicLatin.js

Euclidean Algorithm Example

Hello everyone. So in this video, we're going to talk about the Euclidean Algorithm and back substitution.

Find $\gcd(65,40)$ and find integers $x$ and $y$ such that $65x+40y=\gcd(65,40)$

Finding $\gcd(65,40)$

Alright, so how do we do this? Well the idea's, again, use repeated applications of the Division Algorithm to get a list of equations, for lack of a better word, where each time you're reducing the $\gcd$, step by step. So I think it's probably just best to actually do an example.

$$\begin{align} 65&=40(1)+25\\ 40&=25(1)+15\\ 25&=15(1)+10\\ 15&=10(1)+5\\ 10&=5(2)+0 \end{align}$$

So here are the equations $65=40+25$, then you divide $25$ into $40$ that goes in once, with a remainder $15$, then you divide $15$ into $25$ that goes in once with remainder $10$, then divide $10$ into $15$ that goes in once, with remainder $5$, and you do it one more time with remainder $0$.

The Euclidean Algorithm says the $\gcd$ is the last non-zero remainder, which is therefore $5$, so thus $\gcd(65,40)=5$.

Finding Integers $x$ and $y$

To find the integers $x$ and $y$, we use back substitution. We're going to start with the equation $4$, the last non-zero remainder equation, and isolate for the remainder.

$$\begin{align*} 5&=15+10(-1)&&\text{By}\,(4) \end{align*}$$

Now I'm going to do the same thing with the equation $3$. I'm going to isolate for the remainder and then sub that into my previous equation.

$$\begin{align*} 5&=15+10(-1)&&\text{By}\,(4)\\ &=15+(25+15(-1))(-1)&&\text{By }(3) \end{align*}$$

By the way, this makes sense. Again you can check it, right? $25-15=10$, so it's okay. Now I simplify.

$$\begin{align*} 5&=15+10(-1)&&\text{By}\,(4)\\ &=15+(25+15(-1))(-1)&&\text{By }(3)\\ &=25(-1)+15(2) \end{align*}$$

Again, sanity check: $25(-1)+15(2)=-25+30=5$, still good. Do the same thing now with $15$ from equation $2$.

$$\begin{align*} 5&=15+10(-1)&&\text{By}\,(4)\\ &=15+(25+15(-1))(-1)&&\text{By }(3)\\ &=25(-1)+15(2)\\ &=25(-1)+(40+25(-1))(2)&&\text{By }(2) \end{align*}$$

Again, sanity check: $40-25=15$, it's still good.

$$\begin{align*} 5&=15+10(-1)&&\text{By}\,(4)\\ &=15+(25+15(-1))(-1)&&\text{By }(3)\\ &=25(-1)+15(2)\\ &=25(-1)+(40+25(-1))(2)&&\text{By }(2)\\ &=40(2)+25(-3) \end{align*}$$

Sanity check: $40(2)+25(-3)=80-75=5$, still good. Okay now let's do the last one.

$$\begin{align*} 5&=15+10(-1)&&\text{By}\,(4)\\ &=15+(25+15(-1))(-1)&&\text{By }(3)\\ &=25(-1)+15(2)\\ &=25(-1)+(40+25(-1))(2)&&\text{By }(2)\\ &=40(2)+25(-3)\\ &=40(2)+(65+40(-1))(-3)&&\text{by }(1) \end{align*}$$

Alright, now I've used all those equations, just one last distributive property.

$$\begin{align*} 5&=15+10(-1)&&\text{By}\,(4)\\ &=15+(25+15(-1))(-1)&&\text{By }(3)\\ &=25(-1)+15(2)\\ &=25(-1)+(40+25(-1))(2)&&\text{By }(2)\\ &=40(2)+25(-3)\\ &=40(2)+(65+40(-1))(-3)&&\text{by }(1)\\ &=65(-3)+40(5) \end{align*}$$

Alright, so one last sanity check here: $65(-3)+40(5)=200-195=5$. Therefore, integers satisfying the original equation are $x=-3$ and $y=5$. You should always write a concluding sentence like this, right, make sure you actually answer the question.

Well that's great. So there's a solution that gives you the $\gcd(65,40)=5$. This part is called back substitution, and the first part is called the Euclidean Algorithm.

Key takeaways from this: the Euclidean Algorithm states that when you repeatedly apply the Division Algorithm, the last non-zero remainder is the $\gcd$, and the back substitution part says you can write down the $\gcd$ as a linear combination of the two terms you're taking the $\gcd$ of. This is sometimes called Bezout's Lemma or Bezout's Identity depends on what you read.

So that solves that problem, and I think that's all I want to say. So hopefully, this example gives you an idea of how to approach this if you saw it on an exam or on a assignment. I hope this has been enlightening. Thank you very much for your time and good luck.