# 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?

• Feb 21, 2015 at 16:44

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

• @Tim Thanks, and thanks to everyone for the many supportive emails, which played a large role in my decision to return. Feb 25, 2012 at 0:15
• I don't get the last $\Leftrightarrow$ of the first proof with $cx$ Sep 30, 2017 at 20:37
• @Maman The first and third equivalences follow by Bezout, i.e. common divisors representable as integral linear combinations of the gcd arguments necessarily are greatest common divisors - see the link I gave above the proof. Sep 30, 2017 at 20:51

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

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.

• Sorry if this seems trivial, but does your statement about gcd and its prime factors offer a formal proof for this? Or is this simply a property of gcd? Feb 24, 2012 at 7:11
• It's not trivial if it's not obvious. Ideas don't think themselves. I added an explanation. Feb 24, 2012 at 7:43

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