Take the 2-minute tour ×
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.

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|improve this question

3 Answers 3

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|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|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|improve this answer

Your Answer

 
discard

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.