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'm having trouble proving this statement:

$\forall a,b,c \in \Bbb{Z} : \gcd(a,bc) | \gcd(a,b)\cdot\gcd(a,c)$,

without using the fundamental theorem of arithmetic (hasn't been taught yet).


What I've tried is to use the basic properties of GCD to come up with some equations to manipulate, but it hasn't lead to any useful result.

Let $x=\gcd(a,bc), y=\gcd(a,b), z=\gcd(a,c)$. Then $x|a$ and $x|bc$ etc. Need to manipulate this somehow to show $x|yz$, i.e. $\exists q \in \Bbb{Z} : qx=yz$.

What would be a reasonable next step?

share|improve this question

2 Answers 2

up vote 2 down vote accepted

Note that by Bezout's Theorem, there exist integers $s$ and $t$ such that $\gcd(a,b)=as+bt$. Similarly, there exist integers $u$ and $v$ such that $\gcd(a,c)=au+cv$.

Expand the product $(as+bt)(au+cv)$. We get an expression of the shape $ax+bcy$ for some integers $x$ and $y$.

Now if $e$ divides both $a$ and $bc$, then $e$ divides $ax+bcy$.

share|improve this answer
    
Perfect, I knew there was some simple way to do this. I had something similar written down, but missed the last little bit. –  jli Feb 6 '13 at 6:21

From my post last week.

Theorem $\rm\qquad gcd(bc,a)\,|\,\gcd(b,a)\,gcd(c,a)$

$\begin{eqnarray}\rm{\bf Proof}\qquad\quad\ \ gcd(b,a) &=&\ \, \ \rm j\:b+m\:a \quad \!for\ some\,\ j,m\in \Bbb Z\ \ by\ Bezout\\ \rm gcd(c,a) &=&\ \ \rm k\:c+\ n\:a \quad for\ some\,\ k,n\in \Bbb Z\ \ by\ Bezout\\ \rm\ \ \Rightarrow\ \ gcd(b,a)\,gcd(c,a) &=&\:\rm jk\,\color{#C00}{bc}\:+\:\color{#C00}a\,(\cdots)\ \ \ for\, \ \ (\cdots)\in \Bbb Z \end{eqnarray}$

Since $\rm\:gcd(bc,a)\,|\,\color{#C00}{bc,a},\:$ it divides the right-side of prior, so also the left. $\ $ QED

More explicitly one may prove, writing $\rm\,(x,y)\,$ for $\rm\,gcd(x,y)$

$$\rm (a,b)(a,c)\, =\, (a,bc)\,(a,b,c,bc/(a,bc)) $$

share|improve this answer

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.