Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

4 Answers 4

up vote 6 down vote accepted

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

share|improve this answer
    
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$? –  persepolis May 19 '11 at 17:48
3  
@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$." –  Arturo Magidin May 19 '11 at 18:19
add comment

HINT $\ \:$ Noting $\displaystyle\rm\ \ \ a\ |\ b\:\iff\: \frac{b}a\in \mathbb Z$

we observe that $\rm\quad a\ |\ b,\ c\ |\ d\ \ \Rightarrow\ \ a\:c\ |\ b\:d $

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\quad j\:,\:k\ \in\ \mathbb Z\ \ \Rightarrow\:\ \ \ j\ k\ \in \: \mathbb Z$

That's true! (multiplying integers yields an integer)

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. Below I elaborate on this by showing 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\:j\:k\:.\:$ 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 that $\rm\: 1\:|\:b,\ 1\:|\:d\ \Rightarrow\ 1\:|\:\:b\:d\:,\ $ i.e. $\rm\ b,d\in\mathbb Z\ \Rightarrow\ b\:d\in \mathbb Z\:\ $ (note $\rm\ 1\:|\:n\iff n/1\in \mathbb Z\:,\:$ by definition).

Similarly, one deduces the equivalence between the divisibility difference rule, namely that $\rm\ a\ |\ b,\:c\ \Rightarrow\ a\ |\ 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\ 1\in Z\ $ be a subset of $\rm\:\mathbb Q\:.\:$ Let $\:|\:$ be the divisibility relation $\rm\: \ a\ |\ b \iff b/a\in Z\:$ for $\rm\: 0\ne a,b\in Z\:,\:$ and $\rm\ 0\ |\ b\ \iff b = 0\:.\:$ The following are equivalent.

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

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

$\rm\quad\quad(D1)\quad a\ |\ b,\:c\ \Rightarrow\ a\ |\ b-c\quad\quad\ $ for all $\rm\:a,b,c\in Z$

$\rm\quad\quad(D2)\quad a\ |\ b,\ c\ |\ d\ \Rightarrow\ a\:c\ |\ b\:d\ \ \ $ for all $\rm\:a,b,c,d\in Z$

share|improve this answer
6  
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. –  Qiaochu Yuan May 19 '11 at 19:28
2  
@Qiaochu I strongly disagree. What I wrote above is the essence of the matter. Moreover, it is comprehensible to anyone who understands integer arithmetic. As such, I find your comment quite bizarre (thanks for the unwarranted downvote). –  Bill Dubuque May 19 '11 at 19:36
3  
@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." –  Qiaochu Yuan May 19 '11 at 19:54
3  
@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. –  Bill Dubuque May 19 '11 at 20:07
2  
@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. –  Listing May 19 '11 at 21:22
show 5 more comments

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
c|d

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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