+2863 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)
+9481 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!!
+118687
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.
+2863 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.
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)
+118687 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.
+2511 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
+2511 !!!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
Well too bad CU didnt ask to solve it for real numbers! You are contributing nothing
+2511 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
+9481 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!!
+2863 Thank you guys! This is the same answer on the Alcumus, so I can confirm that your interpretation of Euclidean Algorithm is correct!
