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 . Then copy the url of the final document and submit it in Canvas.