I just need to check the reasoning in my proof is correct, I think it is valid although I'm not totally convinced because I can't follow the logic; does proving that $x$ is an integer prove that $ac|bd$?

Theorem: Let $a$, $b$, $c$, $d$ be integers. If $a|b$ and $c|d$, then $ac|bd$.

Proof: $aj=b$ and $ck=d$ for integers $j$, $k$. Then, $ac|bd$ implies $acx=ajck$ and thus $x=jk$ for some $x$. Since the product $jk$ is an integer, $x$ is an integer and thus $acx=ajck$ and thus $ac|bd$.


Your reasoning goes in the wrong direction; you want to demonstrate that $ac\mid bd$, i.e. that there exists an $x$ such that $acx=bd$, using the assumption that $a\mid b$ and $c\mid d$. This is done simply by showing that $x=jk$ works.

In other words, the sentence beginning with "Then $ac\mid bd$ implies..." cannot be part of an argument that $ac\mid bd$ is true. If $P$, $Q$, and $R$ are statements, then showing that $P\Rightarrow R$ and $Q\Rightarrow R$ does not show that $P\Rightarrow Q$.

  • $\begingroup$ I see, so I should say: $aj=b$ and $ck=d$ for $j$,$k \in \mathbb{Z}$. We must show that $acx=bd$. $acx=ajck$, so $x=jk$. Since $x=jk$ is an integer, then $acx=ajck$ for some $x$ and $ac|bd$? $\endgroup$ – persepolis May 19 '11 at 17:48
  • 3
    $\begingroup$ @persepolis: better. Still, better to say something like "we must show that there exists an $x$ such that $acx=bd$. Since $bd=(aj)(ck) = (ac)(jk)$, then $x=jk$ shows that $ac|bd$." $\endgroup$ – Arturo Magidin May 19 '11 at 18:19

Hint $\ $ Noting that $\displaystyle\rm\ \ \ a\mid b\,\iff\, \frac{b}a\in \mathbb Z$

we observe that $\rm\ \ a\mid b,\ c\mid d\ \ \Rightarrow\ \ ac\mid bd $

is equivalent to $\,\rm\displaystyle\,\ \ \frac{b}a,\,\frac{d}c\in\mathbb Z\ \ \Rightarrow\ \frac{b\,d}{a\,c}\in\, \mathbb Z$

in your notation $\rm\ \ \ j,\ k\ \in\ \mathbb Z\ \ \Rightarrow\ \ j\, k\ \in \, \mathbb Z$

That's true: the product of integers is an integer, i.e. integers are closed under product. So this divisibility product law is equivalent to this product closure law (except if our definition of divisibility includes $\,0\mid n\iff n= 0\,$ then we need to handle such cases separately - which is easy).

Edit $\ $ Since, based on comments, at least one reader seems to have misconstrued the intent of my answer, I elaborate below. When I posted this answer, there were already a few answers explaining the logical flaw in the proposed proof in the question. That done, my intent was instead to address another point, namely how one may exploit the the innate arithmetical structure in order to attain a simpler and more conceptual proof. Such simplification may make the proof more intuitive, which may help one to avoid making such errors. To elaborate, below I show how the "arithmetic" of the divisibility relation is intimately connected with the arithmetic of the subring $\rm\,\mathbb Z\subset\mathbb Q.\,$

First, notice how the above proof makes clear that this product rule for divisibility is essentially equivalent to the product rule for integrality, i.e. if $\rm\,j,k\,$ are integers then so too is their product $\rm\,jk.\,$ Indeed, as we saw above, this integrality product rule easily implies the divisibility product rule. Conversely, if the divisibility product rule is true, then specializing $\rm\ a = 1 = c\ $ we infer $\rm\, 1\mid b,\ 1\mid d\ \Rightarrow\ 1\mid bd,\, $ i.e. $\rm\, b,d\in\mathbb Z\ \Rightarrow\ bd\in \mathbb Z\ $ (note $\rm\, 1\mid n\iff n\in \mathbb Z,\,$ by definition).

Similarly, one deduces the equivalence between the divisibility difference rule, namely that $\rm\ a\mid b,\,c\ \Rightarrow\ a\mid b\!-\!c\ $ and the fact that $\rm\,\mathbb Z\,$ is closed under difference $\rm\,j,\,k\in \mathbb Z\ \Rightarrow\ j\!-\!k\in\mathbb Z$.

Combining these observations leads to the following equivalence between the arithmetic of divisibility relations and subrings $\rm\,Z\,$ of $\,\mathbb Q\,$ (or any field).

Theorem $\ $ Let $\rm\,Z\, $ be a subset of $\rm\,\mathbb Q\,$ with $\rm \,1\in Z.\,$ Let $\:\mid\: $ denote the divisibility relation $\rm\, a\mid b \iff b/a\in Z\,$ for $\rm\,a,b\in Z,\, a\ne 0,\ $ and $\rm\ 0\mid b \iff b = 0.\,$ Then the following two statements are equivalent.

$\rm(1)\ \ \ Z\ $ is a subring of $\rm\,\mathbb Q$

$\rm(2)\ \ $ The relation $\:\mid\: $ satsifies the following properties.

$\rm\qquad a\mid b,\,c\,\ \Rightarrow\,\ a\mid b-c\qquad $ for all $\rm\,a,b,c\in Z$

$\rm\qquad a\mid b,\ c\mid d\,\ \Rightarrow\,\ a\,c\mid b\,d\ \ \ $ for all $\rm\,a,b,c,d\in Z$

Remark $ $ The test in $(2)$ is the Subring Test in divisibility language.

  • 7
    $\begingroup$ Bill, I have avoided making this criticism for some time now, but I really think it is valid here: if the OP understood this argument, he/she wouldn't be asking this question. $\endgroup$ – Qiaochu Yuan May 19 '11 at 19:28
  • 4
    $\begingroup$ @Bill: yes, but I don't understand why you're assuming that the OP "understands integer arithmetic," to put it bluntly. It sounds like you are saying "this answer is quite comprehensible to anyone who understands this answer." $\endgroup$ – Qiaochu Yuan May 19 '11 at 19:54
  • 3
    $\begingroup$ @Qia The OP's error does not demonstrate a misunderstanding of arithmetic but, rather, of logic. Reformulating the problem as I did not only helps to avoid such logic pitfalls, but also reveals quite plainly the essence of the matter. As such I find your critique (and downvote) to be unfounded. Translating the divisibility statement into a more familiar statement about products of integers allows the OP to appeal to his well-honed intuition on integer arithmetic operations (vs. unfamiliar manipulation of divisibility relations). So there's less chance to commit such logical errors. $\endgroup$ – Bill Dubuque May 19 '11 at 20:07
  • 2
    $\begingroup$ @Qiaochu I also don't understand your problem. The proof is that elementary that even someone who is really new to maths could understand it. Basically it uses that the product of two integers is an integer which is totally clear, and that if you divide an integer by one of its divisors it remains an integer, which is also very obvious. $\endgroup$ – Listing May 19 '11 at 21:22
  • 3
    $\begingroup$ @Qia Perhaps you missed the point of my answer. When I posted it there were already answers on the OP's logic error. My point was to teach the OP a better way to formulate the proof strategy. If answers were strictly limited to precisely the question asked then this forum would be quite sterile. When teaching math it is essential to address not only the questions asked, but also closely related metamathematical issues such as proof methodology, etc. Effective teaching involves much more than mechanically answering questions. I am here first and foremost to teach. Was that not clear? $\endgroup$ – Bill Dubuque May 20 '11 at 14:23

If you're having trouble with these kinds of proofs, it's often best to start by writing down what you're given on the left side of the paper and where you're trying to get on the right side.

a|b                                                ac | bd

Next fill in what you can from definitions:

b = aj                                              bd = ack
d = ci

Now use inferences to play with the things on the left and aim for what you have on the right. Each time, you need to ensure that what you have implies what you write next.

You can also work from right to left, but you have to be careful. Here you need to make sure the steps are "if and only if" so that you can go backwards from left to right if you eventually meet in the middle of the paper.

Knowing when it's safe to make a particular step either left to right or right to left comes from being extremely careful and from knowing exactly what's going on. There are puzzles from false proofs where they test you on this. A common example is

(a-b)c = (a-b)d                   so        c = d

Looks fine, right? But given that a=b we should have noticed that (a-b)=0 and you can't cancel zero from both sides.

Anyway, getting good at this stuff is called "mathematical maturity" and it, like most kinds of maturity, takes time.


Your idea is right, but there are some difficulties of wording. When you write "Then, $ac|bd$ implies" it begins to sound as if you are going in the wrong direction. "If and only if" would have been OK.

You should have written instead something like this, which by the way is also shorter.

"Then $bd=(aj)(ck)=(ac)(jk)$. So if we let $x=jk$, then $(ac)x=bd$. It follows that $ac$ divides $bd$."

Let me repeat, you knew exactly what was going on. But there was some awkwardness in the exposition that somewhat masked that fact.


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.