Correct proof of divisibility question?

Question

After having a disagreement with my teacher I posted the following question a few days ago and I have now rewritten my proof with all the comments I received earlier in mind. Would anyone like to comment if anything is still missing or if it looks good?

Q: Let a and b be integers such that gcd(a,b)=1 and let c be a third integer. Show that if a|bc then a|c.

(Note: I am aware that there are other and better proofs such as from Bezouts identity, but still like to know if the one I came up with was valid)

Proof: Any integer that divides another integer is also a factor of that integer. Since a|bc, a is a factor of bc and all the factors of a are factors of bc. Therefore, one and only one of three options holds true for factors >1; either some of the factors of a are factors of b and some of c, or all of the factors of a are factors of b and none of c, or similarly all of the factors of a are factors of c and none of b. In the trivial case that a=1, a|c because 1 divides any integer, and if b=1 then bc=c and we know that a|bc. Considering that gcd(a,b)=1, a and b have no common factors (except number 1), so the first option above can not be true. For the same reason, neither can the second option be valid. We can now conclude that the third option must be the correct one; all of the factors of a are factors of c and none of b (except number 1). This means that because a is itself one of the factors of a, a must be a factor to c, and so a|c.

Short version: all factors of a are factors of bc (a|bc) a and b have no common factors except number 1 (gcd(a,b)=1) all factors of a must then be factors to c and therefore a|c

Answer 1

Your proof is a right if you want to explain it to someone but as an exam answer it would be lengthy approach. Whenever two numbers say $a,b$ have gcd equal to 1 . Then Bezout's equation for them is $ax+by=1$ for some values of $x,y$. You said $a$ divides $bc$ .

So bc can be written as pa for some $p$........1

Now if you multiply $ax+by=1$ by $c$

You get $axc+bcy=c$

$axc+(bc)y=c$

$acx+pay=c$ from equation 1

Taking a common

$a(cx+py)=c$

Thus $a$ divides $c$ .

Answer 2

You've got the idea right; I've always wondered myself why these sorts of statements are proved using algebraic manipulation when they are so much clearer when thought of in terms of prime factorization of numbers.

Perhaps your proof can benefit from a little more formality; for example, I would write the prime factorization of each number: $a=p_{a_1}^{i_1} \cdots p_{a_n}^{i_n}$, $b=p_{b_1}^{j_1} \cdots p_{b_m}^{j_m}$, $c=p_{c_1}^{k_1} \cdots p_{c_r}^{k_r}$ and use this notation to make the arguments in the proof.

Perhaps this is one drawback of the prime factorization approach; it can get very tedious very fast.