1
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ The problem here is that $t=rs$ could fail. What you know is that IF $rs < a$, then $t=rs$. However, $r < a$ and $s<a$ do not ensure that $rs<a$. $\endgroup$ – Crostul Jan 19 '16 at 12:56
  • $\begingroup$ Got you! The only way to approach this question is by disprove by example. Am I right? Other way to approach this question? $\endgroup$ – Joseph Jan 19 '16 at 13:00
  • $\begingroup$ I suggest you to write down your proof substituting $a=6 , b=2 , c=3$. $\endgroup$ – Crostul Jan 19 '16 at 13:11
1
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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!

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.