---
# System prepended metadata

title: The Euclidean Algorithm

---

My lesson Topic.md
---
Math 453 Teaching Item 1: Texting Lesson.md
---
The Euclidean Algorithm
===

<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">

Yo teach! I am having a hard time understanding how to use the Euclidean Algorithm. Do you think you can walk me through it?

</div></div> 


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

Of course "insert student name here." For starters, the Euclidean Algorithm is a process that helps us find the greatest common divisor of two integers. Before learning about the Euclidean Algorithm, most students would list out all the divisors of the integers they are attempting to find the gcd of which works but tends to be very inneficient when working with large integer values. This process will allow you to find the gcd of any two integers through a defined process. To help you understand the process we will try to find the gcd of 549 and 729. Do you know the first step we take?  

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


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

I see, so our main objective is to find the gcd of 549 and 729. I think we are supposed to start by using the division algorithm somehow, right?

</div></div> 

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

Thats correct. We will start by having $729 = 549q + r$ and solving for $q$ and $r$.

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

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

Alright so we will have $q = 1$ and $r = 180$.

</div></div>

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

But what is our next step? Aren't we supposed to use the remainder in the next step?

</div></div> 

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

That's correct. We will consider theorem 3.4 that we learned in class where $\gcd(b,a) = \gcd(a,r)$, so if $a = 549$ what will our next step be?

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

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

Okay so our next step will be $549 = 180q + r$ where $q= 3$ and $r = 9$. Do we now move everything over again and find $180 = 9q + r$?

</div></div> 

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

Yes that's right!

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

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

Alright now our $q = 20$ and $r = 0$, but what is our gcd?

</div></div>

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

Now that your remainder is 0, you will look at your previous remainder, which in this case is 9, and that is your gcd. 

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

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

Oh that was easier than I expected. Thank you! So will this work for any two integers?

</div></div>

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

Yes it will. Also, remember to keep yourself organized and double check your answers for each step because a mistake early on can cause a wrong answer that isn't easy to spot through all the different steps. 

</div><img class="right"/></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.





