document.write( "Question 864447: Show that gcd(a,gcd(b,c))=gcd(gcd(a,b),c)
\n" ); document.write( "Ie show that gcd operator is associative \n" ); document.write( "
Algebra.Com's Answer #521346 by Edwin McCravy(20056)\"\" \"About 
You can put this solution on YOUR website!
\r\n" );
document.write( "We will use the fact that the minimal operator \r\n" );
document.write( "'min' is associative, that is,\r\n" );
document.write( "\r\n" );
document.write( "min(x,min(y,z)) = min(min(x,y),z)\r\n" );
document.write( "\r\n" );
document.write( "which is easy to prove since both sides can only be the \r\n" );
document.write( "minimal of the three numbers x, y and z.\r\n" );
document.write( "\r\n" );
document.write( "Suppose the prime factorizations of a, b and c are\r\n" );
document.write( "\r\n" );
document.write( "a = p1a1p2a2···pkak\r\n" );
document.write( "\r\n" );
document.write( "b = p1b1p2b2···pkbk\r\n" );
document.write( "\r\n" );
document.write( "c = p1g1p2g2···pkgk\r\n" );
document.write( "\r\n" );
document.write( "Then\r\n" );
document.write( "\r\n" );
document.write( "gcd(b,c) = p1min(b1,g1)p2min(b2,g2)···pkmin(bk,gk)\r\n" );
document.write( "\r\n" );
document.write( "gcd(a,b) = p1min(a1,b1)p2min(a2,b2)···pkmin(ak,bk)\r\n" );
document.write( "\r\n" );
document.write( "gcd(a,gcd(b,c)) = p1min(a1,min(b1,g1))p2min(a2,min(b2,g2))···pkmin(ak,min(bk,gk))\r\n" );
document.write( "\r\n" );
document.write( "Now since the minimal operator 'min' is associative, \r\n" );
document.write( "the above is equal to\r\n" );
document.write( "\r\n" );
document.write( "p1min(min(a1,b1),g1)p2min(min(a2,b2),g2)···pkmin(min(ak,bk),gk)\r\n" );
document.write( "\r\n" );
document.write( "which is equal to\r\n" );
document.write( "\r\n" );
document.write( "gcd(gcd(a,b),c)\r\n" );
document.write( "\r\n" );
document.write( "and the associativity of gcd is proved.\r\n" );
document.write( "\r\n" );
document.write( "Edwin
\n" ); document.write( "
\n" );