Thread: GCD

**Fernando** · March 19th 2012, 12:07 PM

Hi everyone.

Let $a,b,c\in{\mathbb{Z}}$ . If $a|bc$ , show that $a|(a,b)(a,c)$ where $(,)$ is GCD

Well, if $a|bc\Rightarrow{bc=ak}$ , then I can multiply in the both sides by $(a,b)$ and $(a,c)$ hence

$bc(a,b)(a,c)=ak(a,b)(a,c)$ next, $(a,b)(a,c)=ak(\frac{a}{b},1)(\frac{a}{c},1)$ , but $\frac{a}{b},\frac{a}{c}\in{\mathbb{Z}}$ by hypothesis.

Therefore $a|(a,b)(a,c)$ .
But the problem is that $bc\neq{0}$
Correcto?
Thanks.

**princeps** · March 19th 2012, 10:50 PM

$\begin{cases}\gcd(a,b)=\frac{b}{k_1}\\\gcd(a,c)= \frac{c}{k_2} \end{cases}$

hence :

$\gcd(a,b) \cdot \gcd(a,c)=\frac{b\cdot c}{k_1 \cdot k_2}$

since :

$a \mid b\cdot c \Rightarrow a \mid \frac{b\cdot c }{k_1 \cdot k_2} \Rightarrow a \mid \gcd(a,b) \cdot \gcd(a,c)$

**Fernando** · March 23rd 2012, 07:29 PM

Hi, I have another idea.

Let $d=(a,b)$ and $r=(a,c)$ be then $d=ax+by$ and $r=ax'+cy'$ , now we multiplity $d\cdot r$ hence

$d\cdot r=(ax+by)(ax'+cy')=a^2xx'+acxy'+abx'y+bcyy'$ but by hypothesis $bc=ak$ therefore $(a,b)(a,c)=a(axx'+cxy'+bx'y+kyy')$ so $a|(a,b)(a,c)$

Thread: GCD

LinkBack

Thread Tools

Display

GCD

Re: GCD

Re: GCD

Search Tags