---
# System prepended metadata

title: Euclidean Algorithm Lesson

---

Project by Edgar Canela Lopez
---
Math 453 Teaching Item 1: Texting Lesson.md
---
Euclidean Algorithm Lesson 
===

<style>
body {
  background-color: #eeeeee;
}

h1 {
  color: maroon;
  margin-left: 40px;
} 



.gray {
    margin-left: 50px ;
    margin-right: 29%;
    font-weight: 500;
    color: #000000;
    background-color: #cccccc;
    border-color: #aaaaaa;
}



.blue {
    display: inline-block;
    margin-left: 29% ;
    margin-right: 0%;
    width: -webkit-calc(70% - 50px);
    width:    -moz-calc(70% - 50px);
    width:         calc(70% - 50px);
    font-weight: 500;
    color: #fff;
    border-color: #336699;
    background-color: #337799;
}

.left {
    content:url("https://i.imgur.com/rUsxo7j.png");
    width:50px; 
    border-radius: 50%;
    float:left;
}
.right{
    content:url("https://i.imgur.com/5ALcyl3.png");     width:50px;
    border-radius: 50%;
    display: inline-block;
    vertical-align:top; 
}
</style>




<div id="container" style=" padding: 6px;
    color: #fff;
    border-color: #336699;
    background-color: #337799;
    display: flex;
  justify-content: space-between;
  margin-bottom:3px;">
<div>
<i class="fa fa-envelope fa-2x"></i>
</div>
<div>
<i class="fa fa-camera fa-2x"></i>
</div>

<div>
<i class="fa fa-comments fa-2x"></i>
</div>
<div>
<i class="fa fa-address-card fa-2x" aria-hidden="true"></i>
</div>
<div>
<i class="fa fa-phone fa-2x" aria-hidden="true"></i>
</div>
<div>
<i class="fa fa-list-ul fa-2x" aria-hidden="true"></i>
</div>
<div>
<i class="fa fa-user-plus fa-2x" aria-hidden="true"></i>
</div>
</div>






<div><img class="left"/><div class="alert gray">

Professor Oak, I am stuck on trying to find the $g.c.d$ of two integers using the $\textit{Eulidean Algorithm}$.

</div></div> 


<div><div class="alert blue">

Please send me an image of your work or write out the problem and your work so far. 

</div><img class="right"/></div> 


<div><img class="left"/><div class="alert gray">

Ok. Here's the problem and my work so far:


Find the $g.c.d$ of 34 and 6 using the Euclidean Algorithm. 

$$34 = 6(5) + 4.$$

</div></div> 

<div><img class="left"/><div class="alert gray">

What do I do after dividing the two integers?

</div></div> 

<div><div class="alert blue">

Recall that for two integers $a$ and $b$ (with $a > 0$), the $g.c.d(b,a) = g.c.d(a,r_1)$ where  $r_1$ off course is the resulting remainder of dividing $b$ by $a$.  



The whole idea of the Euclidean Algorithm is to take the given pair of integers from the problem and replace them with samller integers that have the same $g.c.d$. 


With that insight in mind, what might one want to do here?




</div><img class="right"/></div> 

<div><img class="left"/><div class="alert gray">

Do I need to divide again?


</div></div> 

<div><div class="alert blue">

Correct, but what is dividng what? You need to be specific with your terminology.

</div><img class="right"/></div>

<div><img class="left"/><div class="alert gray">

I'm not sure... Is the $r_1$ our divisor? 

</div></div> 

<div><div class="alert blue">

Yes! For the next iteration of the the division, the resulting remainder from the previous calculation is our new divisor. What is $r_1$ dividing?

</div><img class="right"/></div>

<div><img class="left"/><div class="alert gray">

I don't know... Is it the 32?

</div></div> 


<div><div class="alert blue">

No. Remember, the $g.c.d(b,a) = g.c.d(a, r_1)$. Hence the largest common divisor of $a$ and $b$ is the ***largest common divisor of $a$ and $r_1$*** .

</div><img class="right"/></div> 



<div><img class="left"/><div class="alert gray">

Oh! I see. The 4 should divide the 6, since $r_1 = 4$ and $a = 6$. But wait, how do I know that the $a = 6$ and $a \not = 5$? Isn't multiplication communative? 

</div></div> 


<div><div class="alert blue">

Good observation. You need to keep track of what is your initial divisor and dividen is. These two values will be given by the integers whose $g.c.d$ you are trying to find. If it helps, always put paranthesis around your quotient to differentiate it form your divisor. Like this

$$121 = 10(12) + 1 .$$ Here, it is clear that the $q = 12$, while the $a = 10$. Note that is not rule per say, just a nifty way to keep track of your divisors for the Euclidean Algorithmn.

</div><img class="right"/></div> 


<div><img class="left"/><div class="alert gray">

Got it. Ok, so far I have this:


$$34 = 6(5) + 4.$$
$$6 = 4(1) + 2.$$


Am I done, or do I need to do more?

</div></div> 

<div><div class="alert blue">

No you're still not quite done. You need to continue with new iterations of division until "something" happens. Do you remember what that "something" is?

</div><img class="right"/></div> 

<div><img class="left"/><div class="alert gray">


The remainder has to be 0 correct? But wait I'm still sort of confused. What is my new divisor and what I am dividing into now?
</div></div> 


<div><div class="alert blue">

Precisely. As before since $g.c.d(b,a) = g.c.d(a,r_1)$, it must also be the case that $g.c.d(a,r_1) = g.c.d(r_1, r_2)$, where $r_2$ is the resulting remainder of dividng *$a$ by $r_1$*. 

</div><img class="right"/></div> 


<div><img class="left"/><div class="alert gray">

So.. what your saying is that my new divisor is my old remainder, and the new dividen is the old divisor?

</div></div> 

<div><div class="alert blue">

Very good! It seems you have a better understanding of the concept behind the Euclidean Algorithm.

</div><img class="right"/></div> 


<div><img class="left"/><div class="alert gray">


Alright then. I'm pretty sure that I am done. I have:

$$34 = 6(5) + 4.$$
$$6 = 4(1)+ 2.$$
$$4 = 2(2) + 0.$$

My remainder is 0, so I should be done. Which number is my $g.c.d$ again?


</div></div> 

<div><div class="alert blue">

Well done! Your $g.c.d$ is your last nonzero remainder; it will *always* be the last nonzero remainder of the Euclidean Algorithm.

</div><img class="right"/></div> 

<div><img class="left"/><div class="alert gray">


Ok, so the $g.c.d(34, 6) = 2$. Thanks for our help professor! Any tips when finding the $g.c.d$ by this method?


</div></div> 

<div><div class="alert blue">

Sure, here are some points to consider. Keep track of your divisors for the will be the dividen (*thing your dividing into*) of the next iteration of th division. Make sure you have the correct values of $q$ and $r$ for each dividen and divisor, (especially when dealing with a negative dividen) otherwise your $g.c.d$ will most likey be incorrect.

</div><img class="right"/></div> 

<div><img class="left"/><div class="alert gray">


Thank you! I will keep that advice in mind.


</div></div> 





---

To submit this assignment click on the Publish button ![Publish button icon](https://i.imgur.com/Qk7vi9V.png). Then copy the url of the final document and submit it in Canvas.









