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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question

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

share|cite|improve this answer

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

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


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.