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)

CalculatorUser Nov 13, 2019

#8**+3 **

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

This agrees with Melody's answer!!

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.

Melody 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

#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 **

Ok I will follow your instructions.

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**+2 **

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

#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 prestidigitation** –**aka 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

#8**+3 **

Best Answer

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

This agrees with Melody's answer!!

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