Integer $a$ that divides $bc$ but does not divide $b$ or $c$

Question

I know this to be true but I do not know why I can't prove it. Here is my proof so far:

$a$ doesn't divide $b$ means $b = a k_1 + r_1$ for some $0 < r_1 < a$.

$a$ doesn't divide $c$ means $c = a k_2 + r_2$ for some $0 < r_2 < a$.

$a$ divides $bc$ means $bc = a k_3 + r_3$ with $r_3 = 0$.

So I can write $bc = (a k_1 + r_1)(a k_2 +r_2)$ which expands to

$bc = a(a k_1 k_2 + k_1 r_2 + k_2 r_1) + r_1 r_2$, where $r_1 r_2$ need to be $0$, but I started off saying that $r_1$ and $r_2$ were strictly positive.

So, I have proven by contradiciton that there are no integers $a,b,c$ that satisfy the property, yet $a=6$, $b=3$, and $c=8$ is an example. Where did I go wrong in my proof?

Answer 1

The problem with your proof is that $r_1r_2$ needs not be zero, but a multiple of $a$. If for example you have $bc=ak+2a$, then actually $bc=a(k+2)+0$.

By the way, $4$ divides $12=2\cdot 6$ but $4$ does not divide $2$ nor $6$. More in general, if $a$ has a power of a prime as a divisor, $p^k$, then the factors of $p^k$ can be divided among $b$ and $c$ to make them not to be divisible by $a$.

Answer 2

$r_1r_2$ doesn't have to be $0$. It only has to be a multiple of $a$.

Answer 3

Your error appears when you say that $r_1 r_2$ must equal zero (this would be true if you knew that $r_1 r_2\lt a$, but this is not necessarily the case). It is not necessarily true that $r_1 r_2=0$; all you know is that $r_1 r_2$ must also be divisible by $a$.

Answer 4

$r_1r_2$ need not be 0, since remainder is unique only if it's $0 \leq r < |a|$, but $r_1r_2$ is not necessarily less than $a$, so your proof fails.

Answer 5

Given positive integers $x$ and $y$, saying that $x$ divides $y$ is equivalent to saying that, if $z$ and $r$ are integers, then $$ y=xz+r \quad\textit{and}\quad 0\le r<x \qquad\text{implies}\qquad r=0 $$ Similarly, $x$ does not divide $y$ if and only if there are integers $z$ and $r$ such that $$ y=xz+r\quad\textit{and}\quad 0<r<x $$ The condition $r<x$ is crucial. In your argument you have no way to prove that $r_1r_2<a$.

Indeed, if $a=6$, $b=16$ and $c=9$, you have \begin{align} b&=6\cdot2+4 \\ c&=6\cdot1+3 \end{align} so $r_1=2\ne0$, $r_2=3\ne0$, but $r_1r_2=12$ which is not less than $a$ (and of course it is a multiple of $a$).

Answer 6

Where the proof goes wrong, is assuming the r values can't be divisible by divisors of a. If they can be (like given composite a), then the remainders may contain a in their product. An example: $$a=12,b=16=a+4,c=15=a+3$$ therefore $$bc=(a+4)(a+3)=a^2+3a+4a+12=a^2+8a=a(a+8)$$