SOLUTION: Show that gcd(a,gcd(b,c))=gcd(gcd(a,b),c) Ie show that gcd operator is associative

Algebra ->  Divisibility and Prime Numbers -> SOLUTION: Show that gcd(a,gcd(b,c))=gcd(gcd(a,b),c) Ie show that gcd operator is associative       Log On


   

Question 864447: Show that gcd(a,gcd(b,c))=gcd(gcd(a,b),c)
Ie show that gcd operator is associative
Answer by Edwin McCravy(20056) About Me  (Show Source):
You can put this solution on YOUR website!
We will use the fact that the minimal operator 
'min' is associative, that is,

min(x,min(y,z)) = min(min(x,y),z)

which is easy to prove since both sides can only be the 
minimal of the three numbers x, y and z.

Suppose the prime factorizations of a, b and c are

a = p1a1p2a2···pkak

b = p1b1p2b2···pkbk

c = p1g1p2g2···pkgk

Then

gcd(b,c) = p1min(b1,g1)p2min(b2,g2)···pkmin(bk,gk)

gcd(a,b) = p1min(a1,b1)p2min(a2,b2)···pkmin(ak,bk)

gcd(a,gcd(b,c)) = p1min(a1,min(b1,g1))p2min(a2,min(b2,g2))···pkmin(ak,min(bk,gk))

Now since the minimal operator 'min' is associative, 
the above is equal to

p1min(min(a1,b1),g1)p2min(min(a2,b2),g2)···pkmin(min(ak,bk),gk)

which is equal to

gcd(gcd(a,b),c)

and the associativity of gcd is proved.

Edwin