6
$\begingroup$

I want to prove that $\gcd(a,bc)$ divides $\gcd(a,b)\gcd(a,c)$ but I can't succeed.

I tried to go with $\gcd(a,b) = sa+tb$ and it didn't work, tried to use the fact that $\gcd(a,b)$ and $\gcd (a,c)$ divide $\gcd (a,bc)$ but got stuck again. please help.

$\endgroup$
  • $\begingroup$ Okay, i know that gcd(a,b) divides gcd(a,bk), i can't see how it helps me $\endgroup$ – user5109988 Oct 22 '15 at 8:24
  • $\begingroup$ Are you allowed to consider the prime factorizations of $a$, $b$, and $c$? $\endgroup$ – Mankind Oct 22 '15 at 8:28
  • $\begingroup$ No.. we didn't learnd that yet $\endgroup$ – user5109988 Oct 22 '15 at 8:56
8
$\begingroup$

Let $d=\gcd(a,bc)$ and $d_1=\gcd(a,b) $ and $d_2=\gcd(a,c)$. Then there exits $ s_1, s_2,t_1, \text{ and } t_2 \in \mathbb{Z}$ such that $$ d_1=s_1 a+t_1b$$ and $$d_2= s_2a+t_2 c $$then $$ d_1d_2 = s_1s_2 a^2 +s_1 t_2ac +t_1 s_2 ba + t_1 t_2 bc$$ but $d\mid a $ and $d\mid bc$ so $d\mid a^2$, $d\mid ac$, $d\mid ba$ and $d\mid bc$. Hence $d \mid d_1d_2$.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

$$(\gcd(a,b)\cdot\gcd(a,c))\mathbb Z= \gcd(a,b)\mathbb Z\cdot\gcd(a,c)\mathbb Z=(a\mathbb Z+b\mathbb Z)\cdot(a\mathbb Z+c\mathbb Z)\subseteq a^2\mathbb Z+ac\mathbb Z+ab\mathbb Z+bc\mathbb Z\subseteq a\mathbb Z+bc\mathbb Z=\gcd(a,bc)\mathbb Z\Rightarrow\gcd(a,bc)\mid\gcd(a,b)\cdot\gcd(a,c).$$

Edit. The property holds for $a,b,c\in R$ with $R$ a GCD domain.

Let $d=(a,b)$ and $e=(a,c)$. Then $a=da_1$, $b=db_1$ with $(a_1,b_1)=1$, and $a=ea_2$, $c=ec_2$ with $(a_2,c_2)=1$. We have to show that $(a,bc)=(da_1,db_1c)=d(a_1,b_1c)\mid de$, that is, $(a_1,b_1c)\mid e$. Set $f=(a_1,b_1c)$. Since $f\mid a_1$ and $(a_1,b_1)=1$ we have $(f,b_1)=1$. Then $f\mid c$ and $f\mid a$, so $f\mid e$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Very nice, +1. If I'm not mistaken, this proof works precisely for Euclidean domains? $\endgroup$ – Ennar Oct 25 '15 at 9:21
  • $\begingroup$ @Ennar This works for any integral domain $R$ where one can write $\gcd(a,b)R=aR+bR$, that is, a Bezout domain. $\endgroup$ – user26857 Oct 25 '15 at 9:23
  • $\begingroup$ Thank you. I first though of Euclid's algorithm when I saw it. $\endgroup$ – Ennar Oct 25 '15 at 9:28
1
$\begingroup$

$d:=(a,bc)\mid \color{#c00}a,bc\, \Rightarrow\, d\mid \color{#c00}aa,\color{#c00}ab,\color{#c00}ac,bc\, \Rightarrow\, d\mid (aa,ab,ac,bc)=(a,b)(a,c)$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Nice, and hope can add (if needed for question) $d \mid abc, a^3$ also. $\endgroup$ – jiten Dec 11 '17 at 11:06

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.