If $a|b$ and $c|d$, then $ac|bd$

Question

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

Answer 1

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

Answer 2

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$

Answer 3

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.

Answer 4

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.

Answer 5

You say :

$ac|bd \Longrightarrow \exists x \in N, acx=bd$.

It would be better say:

$ac|bd \Longleftrightarrow \exists x \in N, acx=bd$,

then your reasoning is correct.