GCD Proof with Multiplication: gcd(ax,bx) = x$\cdot$gcd(a,b) I was curious as to another method of proof for this:
Given $a$, $b$, and $x$ are all natural numbers,
$\gcd(ax,bx) = x \cdot \gcd(a,b)$
I'm confident I've found the method using a generic common divisor and the theorem that says an integer $C$ is a common divisor of integers $A$ and $B$ iff $C|\gcd(A,B)$.
What other ways can this be proven? Is prime factorization a possibility? Or another method?
 A: 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)$.
A: 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).$
A: Your statement is only true for $x>0$ (some people include $0$ in $\mathbb{N}$).
Here is a proof using prime factorization.
Let
$$
A = \prod p_i^{a_i}
\qquad
\text{and}
\qquad
B = \prod p_i^{b_i}
$$
where the products run over all primes $p_i$
dividing either $A$ or $B$,
which have already been collected and merged.
We can assume this because of the
fundamental theorem of arithmetic,
which guarantees just such a unique
factorization.
To show that
$$
\gcd\left(A,B\right)=\prod p_i^{\min(a_i,b_i)}
$$
$$
\text{lcm}\left(A,B\right)=\prod p_i^{\max(a_i,b_i)}
$$
(where gcd is the greatest common divisor),
consider each prime $p_i$ in turn.
Again, we utilize the fact that the gcd and lcm both
have a unique factorization over the integers,
and that they are composed of the same primes
dividing $A$ and $B$, only in different quantities.
The greatest common divisor must have the largest number of $p_i$
common to both $A$ and $B$. These have $a_i$ and $b_i$, respectively.
Therefore the gcd must have the greatest exponent that is common, i.e.
$\max~\{c|c\le a_i,b_i\}=\min(a_i,b_i)$.
Similarly, the exponent of the least common multiple must be the
least integer that is at least as large as both:
$\min~\{c|c\ge a_i,b_i\}=\max(a_i,b_i)$.
There are certain sets of numbers, or number systems,
which don't have unique factorization, but the integers
(and natural numbers) do, by the FTOA mentioned above.
A: Let $d=\gcd(a,b)$. Since $d$ divides both $a$ and $b$, we can write $a=dk$ and $b=dj$.
$\gcd \left({a\over d},{b\over d}\right)=1=\gcd(k,j)$
$xd=\gcd(xdk,xdj)=\gcd(xa,xb)=x\gcd(a,b)$
