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?


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

  • $\begingroup$ Perfect, I knew there was some simple way to do this. I had something similar written down, but missed the last little bit. $\endgroup$ – 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)) $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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