GCD Proof with Multiplication: gcd(ax,bx) = x$\cdot$gcd(a,b)

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).$

The following result, sometimes called Bézout's lemma, is usually proved fairly early on in a number theory course,

Bézout's lemma: Let $a$ and $b$ be integers, not both $0$. Then $\gcd(a,b)$ is the smallest positive integer which can be expressed in the form $au+bv$, where $u$ and $v$ are integers.

Let $d=\gcd(a,b)$, and let $w=\gcd(ax,bx)$. Suppose that $x$ is positive.

By Bézout's lemma, $w$ is the smallest positive integer which can be expressed in the form $w=(ax)u+(bx)v$. From this last equation, we can see that $x$ divides $w$, so $w=xk$ for some $k$. It follows that $k=au+bv$. We will show $k=d$.

By Bézout's lemma, $d$ is the smallest positive integer which can be expressed as an integer linear combination of $a$ and $b$. Since $k=au+bv$, we conclude that $d\le k$.

There are integers $s$ and $t$ such that $as+bt=d$. It follows that $(ax)s+(bx)t=xd$. Since $w=xk$ is the smallest integer that is an integer linear combination of $ax$ and $bx$, we conclude that $xk\le xd$, and therefore $k \le d$.

We have shown that $d \le k$ and $k\le d$. Thus $k=d$, and therefore $\gcd(ax,bx)=x\gcd(a,b)$.