Correct proof for divisibilty question

Question

So I had an exam where one of the questions was: Let a and b be two integers with 1 as their greatest common divisor and let c be a third integer. Show that if a|bc then a|c.

My argument was: "That gcd (a,b)=1 means that a and b have no common factors except 1.That an integer a divides another c implies that a is a factor to c. Since a|bc, a is a factor to bc. Because a can not be a factor to b, a does not divide b. a then has to be a factor to c which means that a divides c."

Summarized: a is a factor to bc. no factor to a except number 1 is a factor to b . a is not a factor to b. a must then be a factor to c.

My teacher said that this is wrong and I have discussed it a bit with him but still cant understand his argument. He gave the exemple 6|12 but 6 does not divide 4 and 6 does not divide 3. He also says this proves my argument is wrong even though the numbers in his exemple do not fulfill that a and b should have 1 as their greatest common divisor. This is what still confuses med. If it says to let a and b have 1 as their greatest common divisor, then why cant I argue from the standpoint that they do? Maybe i was not clear enough or do not understand the exact logic in making correct proofs.

(I know there are better proofs for this question such as from auc+bvc=c but this is all I could figure by then.I also found that I would probably have needed to mention the special case a=b=1 where a actually divides b)

Answer 1

For the proof: Hint: write $ax+by=1$ for some integers $x$ and $y$. Then, multiply by $c$.

If $a$ were prime, then your argument would work. The problem is that part of $a$ might divide $b$ and another part would divide $c$.

If your argument were true, then it would prove that "if $a\nmid b$ and $a\mid bc$, then $a\mid c$", which is false. You never use the full power of the gcd in your argument only that for $a\not=\pm1$, $a$ does not divide $b$.

Answer 2

To answer your question about why your teacher's example proves that your argument is invalid, note that a crucial part of your argument relied on the statement

In order for an integer to divide another it has to be a factor to that other integer. Therefore since $a$ does not divide $b$ and $a$ divides $bc$ then $a$ divides $c$.

You are claiming here that this statement is true for any integers $a,b,$ and $c$ as long as $a$ does not divide $b$. Therefore, if one can find a counterexample using any integers $a,b,$ and, $c$ such that $a$ does not divide $b$ then your argument would be invalidated. Your teacher has given you such a counterexample. It is true that $6$, $3$, and $4$ are integers such that $6$ does not divide $3$ (or $4$) but $6\mid 3\cdot4$. The $\gcd(a,b)$ in the counterexample is irrelevant.

Answer 3

Suppose I were asked to prove:

If $M$ is even than $M = N + 1$ for some odd number.

And I gave the proof: Since $M$ is even then $M \ge 2$. So $M > 1$ so $M = N + 1$ for some odd number.

And you wanted to show my proof was wrong with a counter-example. $7 \ge 2$ so $7 > 1$ but if $7 = N + 1$ then $N = 6$ and $N$ is not odd.

And I said "But $7$ isn't even. Your premise was that $M$ is even."

We'll, I'd have a slight point. $M$ is even was my premise. But the problem with my argument is I didn't use the premise. I used the premise to get to a point that I could have gotten to without the premise. And then in giving my argument, I gave an argument that didn't need the premise, and which was false.

It is true that if $M$ is even than $M \ge 2$ but there are other numbers with that property. And then I tried to argue that because $M \ge 2$ and NOT because $M$ is even, that it is because $M\ge 2$ that $M = N+1; N$ odd.

That is NOT why $M= N+1; N$ odd. And a counter example for some other $M\ge 2$ (but in this case $M$ not even) shows that my argument why was wrong.

So same with your proof. You argued that because $\gcd(a,b) =1$ then $a\not \mid b$. Fine, but that's not the only way to get $a\not \mid b$. You can get $a\not \mid b$ by simply taking $a = 6; b= 4$.

Then you argued BECAUSE $a\not \mid b$ and $a|bc$ that it must follow that $a|c$. Well, that is not the reason. And $6 \not \mid 4$ and $6|3*4$ but $6\not \mid 3$ shows that that can not be the reason.

You can't claim that this counter-example is faulty because $\gcd(4,6)\ne 1$ unless you can give an argument that that was relevant. Because your argument did not use $\gcd(a,b)= 1$ in any necessary way, this is a valid counter-argument. However if you had used $\gcd(a,b) =1$ is a necessary way, this would not be a valid counter-argument and indeed, I'd be incapable of giving a valid counter-argument as there would be none.

....

Or suppose I offered a proof that cows were rabbits. My proof: Rabbits eat lettuce. ANd cows eat lettuce. Therefore cow are rabbits.

And you tried to show me a counter-argument, "Goats aren't rabbits and goats eat lettuce."

And I said "But goats aren't cows so that doesn't satisfy my basic premise that I'm talking about animals that are cows."