# Does $\gcd(a,bc)$ divides $\gcd(a, b)\gcd(a, c)$?

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.

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

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

• Also, if $d_1 = 1$, we have $d_2 \vert a$ and $d_2 \vert bc$ (since $d_2 \vert c$) then $d_2 \vert \mathrm{gcd}(a,bc) = d$ (by Bezout). With your result : $d \vert d_1d_2 = d_2$ and $d_2 \vert d$ so $d = d_2$. Commented Dec 6, 2022 at 1:28

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

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

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

• Nice, and hope can add (if needed for question) $d \mid abc, a^3$ also. Commented Dec 11, 2017 at 11:06

Let $$p_i$$ be the $$i$$-th prime. For any positive integer $$n$$, denote by $$[n]_i$$ or $$n_i$$ the exponent of $$p_i$$ in the prime factorization of $$n$$, i.e.

$$n=p_1^{n_1}p_2^{n_2}\cdots.$$

Let $$i>0$$. We have: \begin{align*} [\gcd(a,b)]_i &=\min(a_i,b_i) \\ [\gcd(a,c)]_i &=\min(a_i,c_i) \\ [\gcd(a,bc)]_i &=\min(a_i,b_i+c_i) \end{align*} Also, $$\min(a_i,b_i+c_i)\le \min(a_i,b_i) + \min(a_i,c_i).$$ This can be seen by noting that $$\min(a_i,b_i) + \min(a_i,c_i)\in\{2a_i,a_i+b_i,a_i+c_i,b_i+c_i\}$$, where each possible value is no less than either $$a_i$$ or $$b_i+c_i$$ because $$a_i,b_i,c_i\ge 0$$. Thus, $$[\gcd(a,bc)]_i\le [\gcd(a,b)]_i+[\gcd(a,c)]_i$$, which translates to $$\gcd(a,bc)\mid\gcd(a,b)\gcd(a,c)$$.