Proof: divisibility

Question

Question: For all $a, b, c \in \mathbb{Z}$, if $a\mid bc$, then $a\mid b$ or $a\mid c$. Is this true?

My answer: True. (Proof by contrapositive) Proof that if $a \nmid b$ and $a \nmid c$, then $a \nmid bc$.

Suppose $b = ax+r$ and $c = ay+s$, where $x,y,r,s \in \mathbb{Z}$ and $x,y,r,s \neq 0$

Then multiply $b$ by $c$:

$bc = (ax+r)(ay+s)=a(ayz+sy+rz) + rs$

$bc = az + t$, where $z = ayz+sy+rz$ and $t = rs$

Because $a,r,s,y,z$ are all integers $\mathbb{Z}$that are non-zero, both $z$ and $t$ are integers that is not zero.

Therefore, $bc$ is not divisible by $a$ because of the reminder $t$. This completes the proof.

Actual answer: False (Disproof by example) Consider $a=6, b=3, c=4$, $a\mid bc$, but $a \nmid b$ or $a \nmid c$.

My question: What is wrong with my proof?

Answer 1

The first actual error (as opposed to first imprecise statement) in your proof is:

$bc = (ax+r)(ay+s)=a(ayz+sy+rz) + rs$

$bc = az + t$, where $z = ayz+sy+rz$ and $t = rs$

Because $a,r,s,y,z$ are all integers $\mathbb{Z}$that are non-zero, both $z$ and $t$ are integers that is not zero.

Presumably you meant:

$bc = (ax+r)(ay+s)=a(axy+sx+yr) + rs$

$bc = az + t$, where $z = axy+sx+yr$ and $t = rs$

And even then the next statement is wrong:

Because $a,r,s,y,z$ are all integers $\mathbb{Z}$that are non-zero, both $z$ and $t$ are integers that is not zero.

Let $a=5,x=1,y=1,s=5,r=-10$. Then $z = axy+sx+yr = 5(1)(1)+5(1)+1(-10) = 0$

Presumably when you wrote

Suppose $b = ax+r$ and $c = ay+s$, where $x,y,r,s \in \mathbb{Z}$ and $x,y,r,s \neq 0$

you somehow meant to say that $r$ and $s$ weren't multiples of $a$. At this point, there are so many problems with your argument that I'm giving up :-).

As per crostul's comment, try writing your proof out substituting $a=6,b=2,c=3$.

Answer 2

It's possible to assume $a>0$.

Saying that $a\nmid b$ means $b=ax+r$, with $0<r<a$, with no condition on $x$. Similarly, you can certainly write $c=ay+s$, with $0<s<a$. Then, upon multiplying, you get $$ bc=(ax+r)(ay+s)=a(axy+r+s)+rs $$ but in order to conclude along your line of attack you should have $0<rs<a$, which is impossible to prove. The alternative attack by proving $a\nmid rs$ also fails. The simplest counterexample for both lines of attack is $a=4$, $b=c=2$.

Answer 3

In general, that statement is not true. Observe that $12|6·4$, but it is not true that $12|6$ or $12|4$, so the given statement is false. It is only true when $a$ is prime.

Hope this really helps!