# Proof for gcd associative property:

I’m trying to prove\show the associative property for the $\gcd(a,b)$ function.

$$\gcd( a ,\space \gcd(b,c) ) = \gcd(\space \gcd(a,b) , c )$$

Let:

$$e = \gcd( a ,\space \gcd(b,c) )\text{ and }f = \gcd(\space \gcd(a,b) , c )$$

From here you can see that

$$e\mid a,\gcd(b,c) \Longleftrightarrow e\mid a,b,c$$

And similarly,

\begin{align*}
f|\gcd(a,b),c &\Longleftrightarrow f\mid a,b,c\\
&\Longleftrightarrow f\mid e\\
&\Longleftrightarrow e\mid f
\end{align*}

If $e\mid f$ and $f\mid e \Longrightarrow |e| = |f|$ and since $e$ and $f$ are both non-negative we have the result, $e = f$, as required.

Is this proof sound?

#### Solutions Collecting From Web of "Proof for gcd associative property:"

The idea is a good one. But the many logical symbols obscure the logic of the argument.

As you wrote, let $e=\gcd(a,\gcd(b,c))$ and $f=\gcd(\gcd(a,b),c)$.

We want to show that $e$ divides $f$ and $f$ divides $e$. Let us show that $e$ divides $f$. (Remark: it is not a good idea to try to prove two things at once.)

Because $e=\gcd(a,\gcd(b,c))$, it follows that $e$ divides $a$ and $e$ divides $\gcd(b,c)$. So $e$ divides $a$, $b$, and $c$.

It follows that $e$ divides $\gcd(a,b)$ and $e$ divides $c$. This implies that $e$ divides $\gcd(\gcd(a,b),c)$, that is, $e$ divides $f$.

The fact that $f$ divides $e$ is proved in the same way.

Remark: We have used without proof the fact that $x$ divides $y$ and $z$ if and only if $x$ divides $\gcd(y,z)$. One direction is obvious. But if we define $\gcd(y,z)$ as the greatest common divisor of $y$ and $z$, it is not obvious that if $x$ divides $y$ and $z$, then $x$ divides $\gcd(y,z)$. But we can get this by using Bezout’s Theorem, and in other ways.

We can try the following way:

Let us denote $(x,y)$ as gcd$(x,y)$

Let the highest powers of prime $p$ in $a,b,c$ are $A,B,C$ respectively.

So, the highest power of $p$ that divides $(b,c)$ will be max $(B,C)$

Similarly, the highest power of $p$ that divides $(a,b)$ will be max $(A,B)$

So, the highest power of $p$ that divides $(a,(b,c))$ will be max $(A,$ max$(B,C))=$max$(A,B,C)$

Similarly, the highest power of $p$ that divides $((a,b),c)$ will be max $($ max$(A,B),C))=$max$(A,B,C)$

So, $(a,(b,c))=(a,(b,c))=(a,b,c)$