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

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?

• Suppose $a=bc$. – lulu Jan 24 '19 at 21:48
• Yes, but my question is really asking why my proof does not work. It feels like it should but it doesn't. – pmac Jan 24 '19 at 21:50
• $r_1 r_2$ could be divisible by $a$ as well. – Donald Splutterwit Jan 24 '19 at 21:51
• Maybe the title was misleading. I have changed it. – pmac Jan 24 '19 at 21:51
• So, take $a=4$ and $b=c=2$. Go through your argument line by line and find the error. – lulu Jan 24 '19 at 21:52

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

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

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

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

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 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 The condition $$r is crucial. In your argument you have no way to prove that $$r_1r_2.

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

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