Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
You wrote "$\gcd(ax,bx)\gcd(a,b) \cdot x$". I wonder if you meant "$\gcd(ax,bx)=\gcd(a,b) \cdot x$"? –  Michael Hardy Feb 24 '12 at 17:47

3 Answers 3

up vote 10 down vote accepted

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 \min(a\!+\!x,b\!+\!x)\!\iff\! c \le \min(a\!+\!x,b\!+\!x)-x$

share|improve this answer
11  
+1 Welcome back! –  Tim Feb 25 '12 at 0:02
    
@Tim Thanks, and thanks to everyone for the many supportive emails, which played a large role in my decision to return. –  Bill Dubuque Feb 25 '12 at 0:15

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

share|improve this answer

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.

share|improve this answer
    
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? –  Dominick Gerard Feb 24 '12 at 7:11
    
It's not trivial if it's not obvious. Ideas don't think themselves. I added an explanation. –  bgins Feb 24 '12 at 7:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.