# Show that if $a \mid bc$,then $a \mid \gcd(a,b)\gcd(a,c)$.

It is a question from my exam, but i cannot figure out how to prove it.

Show that if $a \mid bc$, then $a \mid \gcd(a,b)\gcd(a,c)$.

I'd like to get helped. Thanks!

-

Using Bézout's theorem, there exist $u_1,v_1,u_2,v_2 \in \Bbb Z$ such that $\gcd(a,b) = a u_1 + bv_1$ and $\gcd(a,c) = a u_2 + c v_2$. Expanding the product, one has $\gcd(a,b)\gcd(a,c) \equiv bc v_1 v_2 \equiv 0 \pmod{a}$.

-

I often find that in these kind of problems, it is useful to think of a number as a list of prime factors (including multiplicity). For example, $12\equiv(2,2,3)$.

With this in mind, the relation $a|b$ translates simply to $a\subseteq b$, $gcd(a,b)$ translates to $a\cap b$ and $ab$ translates to $a\cup b$. So now you need only to show this elementary set-theoretic equation:

$$a\subseteq (b\cup c)\quad\Rightarrow\quad a\subseteq(a\cap b)\cup(a\cap c)$$

(which is actually the trivial statement:)

$$(a\cap b)\cup(a\cap c) \subseteq (b\cup c)$$

-

(1) $a|bc$ $\implies$ $a|(ab)(ac)$.

(2)Let $d_1=gcd(a,b)$, then $d_1|a$ and $d_1|b$ $\implies$ $d_1|ab$ $\implies$ $ab=k_1d_1$.

(3)Similarly, let $d_2=gcd(a,c)$, we have $ac=k_2d_2$.

(4)Thus, we have $(ab)(ac)=(k_1d_1)(k_2d_2)$.

(5)Substitude (1) into (4): we have $a|(k_1d_1)(k_2d_2)$ $\implies$ $a|d_1d_2$ $\implies$ $a|gcd(a,b)gcd(a,c)$ .

Not sure if it is correct.

-