+0

# The Euclidean Algorithm for finding Greatest Common Divisor

0
136
15

Can someonne explain this to me. I never learned it, and the resources that explain it on AOPS cost money.

A problem with the Euclidean Algorithm is like this:

Find the greatest common divisor of 9118, 12173, and 33182.

I don't know what else to do then just to use brute force..

(I only changed the heading - Melody)

Nov 13, 2019
edited by Melody  Nov 14, 2019
edited by Melody  Nov 14, 2019

#8
+2

https://en.wikipedia.org/wiki/Euclidean_algorithm

Examples:

The greatest common divisor of  6  and  9

=   gcd(6, 9)   ←The difference between 6 and 9 is  3, so replace the larger number, 9, with 3.

=   gcd(6, 3)   ←The difference between 6 and 3 is  3, so replace the larger number, 6, with 3.

=   gcd(3, 3)   ←Now the two numbers are the same. So we stop.

=   3

The greatest common divisor of  8  and  12

=   gcd(8, 12)

=   gcd(8, 4)

=   gcd(4, 4)

=   4

The greatest common divisor of  24  and  81

=   gcd(24, 81)

=   gcd(24, 57)

=   gcd(24, 33)

=   gcd(24, 9)

=   gcd(15, 9)

=   gcd(6, 9)

=   gcd(6, 3)

=   gcd(3, 3)

=   3

To calculate the greatest common divisor of  3  different numbers, we can use this prinicple:

gcd(a, b, c)   =   gcd( a, gcd(b, c) )

So we apply the Euclidean algorithm twice. Let's see if this works!

gcd(9118, 12173, 33182)   =   gcd( 9118, gcd(12173, 33182) )

First, use the Euclidean algorithm to find the inner piece.

=   gcd(12173, 33182)

=   gcd(12173, 21009)

=   gcd(12173, 8836)

=   gcd(3337, 8836)

=   gcd(3337, 5499)

=   gcd(3337, 2162)

=   gcd(1175, 2162)

=   gcd(1175, 987)

=   gcd(188, 987)

=   gcd(188, 799)

=   gcd(188, 611)

=   gcd(188, 423)

=   gcd(188, 235)

=   gcd(188, 47)

=   gcd(141, 47)

=   gcd(94, 47)

=   gcd(47, 47)

=   47

Next, use the Euclidean algorithm to find the outer piece.

gcd( 9118, gcd(12173, 33182) )

=   gcd(9118, 47)

=   gcd(9071, 47)

=   gcd(9024, 47)

.

.   *Note that   9118 - 47*193  =  47   so we would have to subtract  47  a total of  193  times.*

.

=   gcd(141, 47)

=   gcd(94, 47)

=   gcd(47, 47)

=   47

Nov 14, 2019
edited by hectictar  Nov 14, 2019

#1
+2

Find the greatest common divisor of 9118, 12173, and 33182.

Factor(9118) = {2, 47, 97}

Factor(12173) = {7, 37, 47}

Factor(33182) = {2, 47, 353}

Greatest common divisor = 47

It is the only prime factor that they all have in common.

Nov 13, 2019
#2
0

wait its really just prime factorizing and listing the factors to see which of them are shared?

wow we learned this in school rip I totally forgot.

CalculatorUser  Nov 13, 2019
#3
+1

Melody this is not the euclidean algorithm

Guest Nov 13, 2019
#4
0

Oh ok guest.

Why don't YOU answer with the Euclidean algortith then.

The only euclidean algorithm I know could not be used for this.

I sposs I could look it up but since you already know why don't you share with us.

Melody  Nov 13, 2019
edited by Melody  Nov 13, 2019
#5
0

Take the smallest nonzero number, subtract it from the other nonzero numbers, repeat until one nonzero number remains, that is the gcd.

We can also use the only euclidean alrgothi you know to solve this conundrum:

gcd(a,b,c)=gcd(gcd(a,b),c)

Guest Nov 13, 2019
#6
0

Take the smallest nonzero number, subtract it from the other nonzero numbers, repeat until one nonzero number remains, that is the gcd.

the numbers are

9118, 12173, and 33182.

the smallest is 9118

subtract  smallest non zero from each of the bigger non-zeros

9118-9118, 12173-9118, and 33182-9118

0 , 3055, 24064

again

0, 0, 24064-3055 = 21009

This is clearly not what you meant guest but it is what I understood you to say.

Melody  Nov 14, 2019
#7
+1

This is one of the Mr. BBs. I’m not sure which one, but it doesn’t really matter, because they all think alike. One trait they all have is to demonstrate pseudo mathematical prestidigitation –aka fake math.

He presents a name for the method and the result, but he never actually presents the method. He uses pseudo mathematical prestidigitation for most of his solutions, but he always does it for the Euclidian Algorithm.

There are two Euclidian Algorithms in Euclid’s Elements:

One for rational numbers, in Book VII, and one for real numbers, in Book X.

GA

GingerAle  Nov 14, 2019
edited by GingerAle  Nov 14, 2019
#12
0

Well why dont you tell us what the "books" are!!!

Guest Nov 14, 2019
#13
0

!!!Mr. BB  (Read as “Triple Deranged Mr. BB”)

I did tell you what they are: Euclid’s Elements, aka Elements by Euclid, aka Στοιχεῖα (Ancient Greek Title).

Elements is a mathematical treatise in 13 books first published circa 300 BCE –back when you were a young teenager, before your arteries hardened and brain atrophied, and senility was still in your future.

!!!Mr. BB, you really should have bought a set because you cannot see what you do not understand.

This explains your rhetorical question: “Well why dont you tell us what the "books" are!!!

GA

GingerAle  Nov 14, 2019
#14
0

Well too bad CU didnt ask to solve it for real numbers! You are contributing nothing

Guest Nov 14, 2019
#15
0

This is just more proof that you cannot see what you do not understand.

CU didn’t know to ask.  However, Hectictar knew which method to use. This method is from book VII.

I did contribute something:

I posted a reference to a twenty-three-hundred-year-old set of mathematical texts.

I also posted (as a public service) a notice that you use pseudo mathematical prestidigitationaka fake math.   You may know this by the more generic name: BULLSHIT! The more experienced avoid this mathematical navigation hazard, but the younger students often walk through it, tracking it all over the forum and their academics. This happens enough, by natural means. So, we really don’t need professional bullshitters on this forum.   You should find somewhere else to spread your dung.

GA

GingerAle  Nov 14, 2019
edited by GingerAle  Nov 14, 2019
#8
+2

https://en.wikipedia.org/wiki/Euclidean_algorithm

Examples:

The greatest common divisor of  6  and  9

=   gcd(6, 9)   ←The difference between 6 and 9 is  3, so replace the larger number, 9, with 3.

=   gcd(6, 3)   ←The difference between 6 and 3 is  3, so replace the larger number, 6, with 3.

=   gcd(3, 3)   ←Now the two numbers are the same. So we stop.

=   3

The greatest common divisor of  8  and  12

=   gcd(8, 12)

=   gcd(8, 4)

=   gcd(4, 4)

=   4

The greatest common divisor of  24  and  81

=   gcd(24, 81)

=   gcd(24, 57)

=   gcd(24, 33)

=   gcd(24, 9)

=   gcd(15, 9)

=   gcd(6, 9)

=   gcd(6, 3)

=   gcd(3, 3)

=   3

To calculate the greatest common divisor of  3  different numbers, we can use this prinicple:

gcd(a, b, c)   =   gcd( a, gcd(b, c) )

So we apply the Euclidean algorithm twice. Let's see if this works!

gcd(9118, 12173, 33182)   =   gcd( 9118, gcd(12173, 33182) )

First, use the Euclidean algorithm to find the inner piece.

=   gcd(12173, 33182)

=   gcd(12173, 21009)

=   gcd(12173, 8836)

=   gcd(3337, 8836)

=   gcd(3337, 5499)

=   gcd(3337, 2162)

=   gcd(1175, 2162)

=   gcd(1175, 987)

=   gcd(188, 987)

=   gcd(188, 799)

=   gcd(188, 611)

=   gcd(188, 423)

=   gcd(188, 235)

=   gcd(188, 47)

=   gcd(141, 47)

=   gcd(94, 47)

=   gcd(47, 47)

=   47

Next, use the Euclidean algorithm to find the outer piece.

gcd( 9118, gcd(12173, 33182) )

=   gcd(9118, 47)

=   gcd(9071, 47)

=   gcd(9024, 47)

.

.   *Note that   9118 - 47*193  =  47   so we would have to subtract  47  a total of  193  times.*

.

=   gcd(141, 47)

=   gcd(94, 47)

=   gcd(47, 47)

=   47

hectictar Nov 14, 2019
edited by hectictar  Nov 14, 2019
#9
+2

Thank you guys! This is the same answer on the Alcumus, so I can confirm that your interpretation of Euclidean Algorithm is correct!

CalculatorUser  Nov 14, 2019
#10
+2

grinding alcumus be like

tommarvoloriddle  Nov 14, 2019
#11
0

Thanks Hectictar

That is a great answer.  !   I've never seen that Euclidean algorithm  before, at least I've not seen it used in that way.

Melody  Nov 14, 2019
edited by Melody  Nov 14, 2019