avatarBrett Berry

Free AI web copilot to create summaries, insights and extended knowledge, download it at here

2478

Abstract

fb"><img src="https://cdn-images-1.readmedium.com/v2/resize:fit:800/1*70ZYZ6jexJsQnqS7QFbmxQ.png"><figcaption></figcaption></figure><p id="85cc"><b>Step 2:</b> Each iteration resets the equation with values from the previous step. Repeat step 1 with the new values 231 and 91.</p><figure id="9a42"><img src="https://cdn-images-1.readmedium.com/v2/resize:fit:800/1*cU0Yv_wvXLg5cweRAFwAug.png"><figcaption>To indicate it is the 1st iteration, q and r are marked with subscripts of 1.</figcaption></figure><figure id="d5be"><img src="https://cdn-images-1.readmedium.com/v2/resize:fit:800/1*_rZKamPkS3oI5gs2_RxgdQ.png"><figcaption>231 ÷ 91 = 2 with a remainder of 49</figcaption></figure><p id="a2a3"><b>Step 3: </b>Reset the equation and increase the indexing to <i>q-2</i> and <i>r-2</i>. Determine the quotient and remainder.</p><figure id="f430"><img src="https://cdn-images-1.readmedium.com/v2/resize:fit:800/1*Mbdh--Q2rNpEzpLgdbBwJQ.png"><figcaption></figcaption></figure><figure id="823d"><img src="https://cdn-images-1.readmedium.com/v2/resize:fit:800/1*tx9JH9j4obh-F056Z4OaBg.png"><figcaption>91 ÷ 49 = 1 with a remainder of 42</figcaption></figure><p id="f2e7"><b>Step 4:</b> Reset the equation and repeat the process.</p><figure id="ada5"><img src="https://cdn-images-1.readmedium.com/v2/resize:fit:800/1*gL0kItaFprEf47HBjwYwLA.png"><figcaption></figcaption></figure><figure id="11ef"><img src="https://cdn-images-1.readmedium.com/v2/resize:fit:800/1*I6pclXbwK0g8f5dRMIqurw.png"><figcaption>49 ÷ 42 = 1 with a remainder of 7</figcaption></figure><p id="fa40"><b>Step 5: </b>Because 7 x 6 is 42 exactly, this is our final step! The greatest common divisor of 1015 and 231 is 7.</p><figure id="c619"><img src="https://cdn-images-1.readmedium.com/v2/resize:fit:800/1*iZhCV7ZP6TBv9GPnEQtwVQ.png"><figcaption></figcaption></figure><figure id="ea20"><img src="https://cdn-images-1.readmedium.com/v2/resize:fit:800/1*VNahXjqb9HCPXualV9YLhQ.png"><figcaption></figcaption></figure><figure id="6657"><img src="https://cdn-images-1.readmedium.com/v2/resize:fit:800/1*iHnlMKyTynTlzkEGAy2TAA.png"><figcaption></figcaption></figure><p id="abdb"><i>I’ll leave it to the reader to think about <b>why</b> this process produces the largest number that divides nicely into both values…</i></p><p id="41c1">Check out the visual walkthrough in the next post, it’s pretty cool →</p><div id="1063" class="link-block"> <a href="https://readmedium.com/why-does-the-euclidean-algorithm-w

Options

ork-aaf43bd3288e"> <div> <div> <h2>Why Does the Euclidean Algorithm Work?</h2> <div><h3>(and the lock riddle solution)</h3></div> <div><p>medium.com</p></div> </div> <div> <div style="background-image: url(https://miro.readmedium.com/v2/resize:fit:320/1*YDyIexo2moNzE6HA0DYZ0g.png)"></div> </div> </div> </a> </div><p id="7eac"><i>Thanks for reading!</i></p><p id="a319"><i>Please click the ❤ to let me know you learned something new!</i></p><h2 id="a114">Related Reading</h2><div id="83e9" class="link-block"> <a href="https://readmedium.com/how-do-we-know-prime-numbers-are-infinite-9470f9d1aa39"> <div> <div> <h2>How Do We Know Prime Numbers are Infinite?</h2> <div><h3>Proving Euclid’s Theorem</h3></div> <div><p>medium.com</p></div> </div> <div> <div style="background-image: url(https://miro.readmedium.com/v2/resize:fit:320/)"></div> </div> </div> </a> </div><div id="71df" class="link-block"> <a href="https://readmedium.com/intro-to-modular-arithmetic-34ad9d4537d1"> <div> <div> <h2>Intro to Modular Arithmetic</h2> <div><h3>Equivalence Classes and Circular Counting</h3></div> <div><p>medium.com</p></div> </div> <div> <div style="background-image: url(https://miro.readmedium.com/v2/resize:fit:320/1*vpJPkyD-7Y01KI3fWM595A.png)"></div> </div> </div> </a> </div><div id="d5a4" class="link-block"> <a href="https://readmedium.com/prime-numbers-the-sieve-of-eratosthenes-ee22c119b6de"> <div> <div> <h2>Prime Numbers & The Sieve of Eratosthenes</h2> <div><h3>When it comes to number envy, primes definitely steal the show, and for good reason. They’re fundamental, mysterious…</h3></div> <div><p>medium.com</p></div> </div> <div> <div style="background-image: url(https://miro.readmedium.com/v2/resize:fit:320/1*JwCzgISCLEzuNE3O62FRbQ.png)"></div> </div> </div> </a> </div></article></body>

The Euclidean Algorithm

The Euclidean Algorithm is one of the oldest numerical algorithms still in use today. Attributed to ancient Greek mathematician Euclid in his book “Elements” written approximately 300 BC, the algorithm serves as an effective method for finding the greatest common divisor of two whole numbers.

The greatest common divisor (GCD) of two whole numbers is the largest natural number that divides evenly into both without a remainder.

We’ll begin with the formal definition and then work an example. If mathematical notation makes your eyes glaze over, hang in there! It’s actually pretty straightforward when you see the example.

Formal Notation

In the initial setup, the values for a-0 and b are the two values we want to find the GCD of, a-o being the larger of the two. The goal of each step is to find the quotient q and remainder r that makes the equation true.

Initial Setup

The Euclidean Algorithm is a k-step iterative process that ends when the remainder is zero. (In other words, you keep going until there’s no remainder.) The GCD will be the last non-zero remainder.

First Iteration (I have a typo: r-0 is the same as r in the initial setup)
Final Iteration

Example:

Find the GCD of 1015 and 231

Don’t worry too much about the equations above, in practice it is rather simple. Let’s find the GCD of 1015 and 231.

Step 1: Begin by setting a = 1015 and b = 231. Determine how many times 231 goes into 1015 and the remainder leftover.

Since 231 x 4 = 924, replace q with 4. The remainder r will be 1015–924 = 91.

Step 2: Each iteration resets the equation with values from the previous step. Repeat step 1 with the new values 231 and 91.

To indicate it is the 1st iteration, q and r are marked with subscripts of 1.
231 ÷ 91 = 2 with a remainder of 49

Step 3: Reset the equation and increase the indexing to q-2 and r-2. Determine the quotient and remainder.

91 ÷ 49 = 1 with a remainder of 42

Step 4: Reset the equation and repeat the process.

49 ÷ 42 = 1 with a remainder of 7

Step 5: Because 7 x 6 is 42 exactly, this is our final step! The greatest common divisor of 1015 and 231 is 7.

I’ll leave it to the reader to think about why this process produces the largest number that divides nicely into both values…

Check out the visual walkthrough in the next post, it’s pretty cool →

Thanks for reading!

Please click the ❤ to let me know you learned something new!

Related Reading

Mathematics
Algorithms
Math
Problem Solving
Number Theory
Recommended from ReadMedium