Number Theory GCD Homework Problem

Question

This is a problem from my homework:

If $a\mid bc$, show that $a\mid $gcd$(a,b)$gcd$(a,c)$.

(Hint: use Euclid's lemma: If $a_0\mid b_0c_0$, with gcd$(a_0,b_0)=1$, then $a_0\mid c_0$.)

I tried setting $a_0=a$, $c_0=c$, and $b_0=$gcd$(a,b)$, to try to find gcd$($gcd$(a,b),a)$, but I stopped here as I wasn't able to go further.

Thanks in advance!

Answer 1

$a_0=a,b_0=\gcd(a,b)$ does not meet the condition $\gcd(a_0,b_0)=1$

The key is that $$\gcd\left(\frac{a}{\gcd(a,b)},\frac{b}{\gcd(a,b)}\right)=1$$

let $$a_0=\frac{a}{\gcd(a,b)},b_0=\frac{b}{\gcd(a,b)},c_0=c$$ we have $$\begin{align}a|bc\Rightarrow & a_0*\gcd(a,b)|b_0*\gcd(a,b)*c_0\\\Rightarrow & a_0|b_0c_0\end{align}$$ and $$\gcd(a_0,b_0)=1$$ Thus $$a_0|c_0 \Rightarrow \frac{a}{gcd(a,b)}|c$$ obviously $$\frac{a}{gcd(a,b)}|a$$. So $$\frac{a}{gcd(a,b)}|\gcd(a,c)$$ ie. $$a|\gcd(a,b)\gcd(a,c)$$

Answer 2

Bezout Theorem implies that there is integers $s_1,s_2,r_1,r_2$ such that $$\gcd(a,b)=s_1a+r_1b\ \ \ \text{and}\ \ \ \gcd(a,c)=s_2a+r_2c;$$ $$\gcd(a,b) \gcd(a,c)=(s_1a+r_1b)(s_2a+r_2c)=a((s_2a+r_2c)s_1+s_2r_1b)+r_1r_2bc;$$ and above relation complete the porof.

Answer 3

It suffices to show that for any prime $p$, the largest power of $p$ that divides $a$ also divides $\gcd(a,b).\gcd(a,c)$ when $a|bc..... $ For prime $p$ and non-zero $ x$, let $x_p$ be the largest non-negative integer $n$ such that $ p^n | x$. (That is $p^{x_p}|x$ and $ p^{1+x_p}\not|x$ )......Now for any prime $p$, we have $$a|bc \implies a_p\le b_p+c_p.$$ And $$(\gcd(a,b))_p= \min (a_p.b_p)$$ while $$(\gcd(a,c))_p= \min(a_p,c_p).$$ Let $$S= (\gcd(a,b).\gcd(a,c))_p.$$ We have $$S=\min(a_p,b_p)+ \min(a_p.c_p).$$ Now there are 3 cases : $$a_p\le b_p \implies S\ge \min (a_p,b_p)=a_p,$$ $$a_p\le c_p \implies S\ge \min(a_p,c_p)=a_p,$$ $$( a_p>b_p \text{ and } a_p>c_p) \implies S=\min(a_p,b_p)+\min(a_p.c_p)=b_p+c_p\ge a_p.$$