Below are $3$ proofs of the gcd distributive law $\rm\:(ax,bx) = (a,b)x\:$ using Bezout's identity, universal gcd laws, and unique factorization.
First we show that the gcd distributive law follows immediately from the fact that, by Bezout, the gcd may be specified by linear equations. Distributivity follows because such linear equations are preserved by scalings. Namely, for naturals $\rm\:a,b,c,x \ne 0$
$\rm\qquad\qquad \phantom{ \iff }\ \ \ \:\! c = (a,b) $
$\rm\qquad\qquad \iff\ \: c\:\ |\ \:a,\:b\ \ \ \ \ \ \&\ \ \ \ c\ =\ na\: +\: kb,\ \ \ $ some $\rm\:n,k\in \mathbb Z$
$\rm\qquad\qquad \iff\ cx\ |\ ax,bx\ \ \ \&\ \ \ cx = nax + kbx,\,\ \ $ some $\rm\:n,k\in \mathbb Z$
$\rm\qquad\qquad { \iff }\ \ cx = (ax,bx) $
The reader familiar with ideals will note that these equivalences are captured more concisely in the distributive law for ideal multiplication $\rm\:(a,b)(x) = (ax,bx),\:$ when interpreted in a PID or Bezout domain, where the ideal $\rm\:(a,b) = (c)\iff c = gcd(a,b)$
Alternatively, more generally, in any integral domain $\rm\:D\:$ we have
Theorem $\rm\ \ (a,b)\ =\ (ax,bx)/x\ \ $ if $\rm\ (ax,bx)\ $ exists in $\rm\:D.$
Proof $\rm\quad\: c\ |\ a,b \iff cx\ |\ ax,bx \iff cx\ |\ (ax,bx) \iff c\ |\ (ax,bx)/x\ \ \ $ QED
The above proof uses the universal definitions of GCD, LCM, which often served to simplify proofs, e.g. see this proof of the GCD * LCM law.
Alternatively, comparing powers of primes in unique factorizations, it reduces to the following
$$\begin{eqnarray} \min(a+x,\,b+x) &\,=\,& \min(a,b) + x\\
\rm expt\ analog\ of\ \ \ \gcd(a \,* x,\,b \,* x)&=&\rm \gcd(a,b)\,*x\end{eqnarray}\qquad\qquad\ \ $$
The proof is precisely the same as the prior proof, replacing gcd by min, and divides by $\,\le,\,$ and
$$\begin{eqnarray} {\rm employing}\quad\ c\le a,b&\iff& c\le \min(a,b)\\
\rm the\ analog\ of\quad\ c\ \, |\, \ a,b&\iff&\rm c\ \,|\,\ \gcd(a,b) \end{eqnarray}$$
$\ c \le a,b \!\iff\! c\!+\!x \le a\!+\!x,b\!+\!x\!\iff\! c\!+\!x \le \lfloor a\!+\!x,b\!+\!x\rfloor\!\iff\! c \le \lfloor a\!+\!x,b\!+\!x\rfloor \!-\!x$
where $\,\lfloor y,z\rfloor := \min(y,z).$
This is exercise 4.38. There is a hint to use Euclid's algorithm that you forgot to reproduce. There is also an answer (p. 503) that reads
$a^n-b^n =(a^m-b^m)(a^{n-m}b^0+a^{n-2m}b^m+\cdots+a^{n\bmod m}b^{n-m-n\bmod m})+b^{m\lfloor n/m\rfloor}(a^{n\bmod m}-b^{n\bmod m})$
What this means is that the first step of Euclid's algorithm reduces $\gcd(a^n-b^n,a^m-b^m)$ to $\gcd(a^m-b^m,b^{m\lfloor n/m\rfloor}(a^{n\bmod m}-b^{n\bmod m}))$. But $b^{m\lfloor n/m\rfloor}$ is relatively prime to $a^n-b^n$ since it divides the second term and is relatively prime to the first term; therefore it will be relatively prime to the $\gcd$ that is being computed, and we might as well remove that factor from the second argument of the $\gcd$. All in all this gives
$$
\gcd(a^n-b^n,a^m-b^m)
=\gcd(a^m-b^m,a^{n\bmod m}-b^{n\bmod m}).
$$
Now iterating as in the Euclidean algorithm eventually gives
$$
\gcd(a^m-b^m,a^n-b^n) = a^{\gcd(m,n)} - b^{\gcd(m,n)}.
$$
Best Answer
Same answer as I just gave in
sci.math...Note that $$d|x,y\Longleftrightarrow d|\gcd(x,y).$$ So: $$\begin{align*} d|a,\gcd(b,c) &\Longleftrightarrow d|a,b,c\\ &\Longleftrightarrow d|\gcd(a,b),c \end{align*}$$