2
$\begingroup$

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?

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

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

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