I'm having trouble proving this statement:
$\forall a,b,c \in \Bbb{Z} : \gcd(a,bc) | \gcd(a,b)\cdot\gcd(a,c)$,
without using the fundamental theorem of arithmetic (hasn't been taught yet).
What I've tried is to use the basic properties of GCD to come up with some equations to manipulate, but it hasn't lead to any useful result.
Let $x=\gcd(a,bc), y=\gcd(a,b), z=\gcd(a,c)$. Then $x|a$ and $x|bc$ etc. Need to manipulate this somehow to show $x|yz$, i.e. $\exists q \in \Bbb{Z} : qx=yz$.
What would be a reasonable next step?
Best Answer
Note that by Bezout's Theorem, there exist integers $s$ and $t$ such that $\gcd(a,b)=as+bt$. Similarly, there exist integers $u$ and $v$ such that $\gcd(a,c)=au+cv$.
Expand the product $(as+bt)(au+cv)$. We get an expression of the shape $ax+bcy$ for some integers $x$ and $y$.
Now if $e$ divides both $a$ and $bc$, then $e$ divides $ax+bcy$.