Chapter 31.1, Problem 10E

Program Plan Intro

To prove that for all the integers $a,bandc,$

  $\gcd (a,\gcd (b,c))=\gcd (\gcd (a,b),c)$ and hence to show that the gcd operator is associative.

Explanation of Solution

Assume

  $\begin{array}{l}d=\gcd (a,b,c),a=dp,b=dpandc=dr.\\ \end{array}$

Claim $\gcd (a,\gcd (b,c))=d$

Let $e=\gcd (b,c)$

  $\begin{array}{l}b=es,\\ c=et\end{array}$

Since $d\left|bandd\right|c,thusd|e.$

Let $e=dm,$ thus

  $\begin{array}{l}b=(dm)s=sq,\\ c=(dm)t=dr.\end{array}$

Assume $k=\gcd (p,m),$

  $\begin{array}{l}k|p,k|m,\\ \Rightarrow dk|dp,dk|dm,\\ \Rightarrow dk|dp,dk|(dm)s,dk|(dm)t,\\ \Rightarrow dk|a,dk|b,dk|c.\\ \end{array}$

Since $d=\gcd (a,b,c),thusk=1.$

  $\begin{array}{l}\gcd (a,\gcd (b,c))=\gcd (a,e)\\ =\gcd (dp,dm)\\ =d*\gcd (p,m)\\ =d*k\\ =d\end{array}$

Hence,

  $\gcd (a,\gcd (b,c))=d=\gcd (\gcd (a,b),c).$