# Proof involving logical connectives

So I'm a little confused as to how to disprove the following statement using formal logic: Let x and y be integers. If $$d\in \mathbb{Z}$$ such that $$d|(ax+by)$$ for some $$a,b\in \mathbb{Z}$$, then $$d|x$$ and $$d|y$$.

Here's what I have so far: Rewrite the statement as $$\forall x\in \mathbb{Z}, \forall y\in \mathbb{Z},\exists d\in \mathbb{Z} ((\exists a,b\in \mathbb{Z} (d|(ax+by))) \Rightarrow (d|x \wedge d|y))$$.

But if I set x = y = 0, then the statement is true (it is false if a = b = 0 and $$x\neq 0$$ and $$d = x+1$$). Since the statement is a universal statement, will this counterexample suffice?

Question: is my rewritten version of the statement equivalent to the original statement?

It's mostly correct, except for the $$\exists \, d \in \mathbb{Z}$$. When we say something like let $$d \in \mathbb{Z}$$, it is implicitly understood that $$d$$ is an arbitrarily chosen integer. In other words, it's just another way to say, for all $$d \in \mathbb{Z}$$.

Notice that $$x$$ and $$y$$ share the exact same English description: "Let $$x$$ and $$y$$ be integers". You correctly determined that a universal quantifier was used for each. The integer $$d$$ is also employing the same universal quantifier for the same reason.

Typically, the reason why the $$d$$ was separate from $$x$$ and $$y$$ is to emphasize the role that this integer $$d$$ plays in the proposition; in this case, if $$d$$ divides $$(ax + by)$$ for some integers $$x$$ and $$y$$, then $$d$$ divides $$x$$ and $$d$$ divides $$y$$. Observe that $$d$$ is definitely more involved than $$x$$ and $$y$$ are, although all three of them were arbitrarily chosen integers--the integer $$d$$ is just more important in this case.

Therefore, the proper logical skeleton of the above proposition is as follows $$\forall x \in \mathbb{Z} \, \forall y \in \mathbb{Z} \, \forall \, d \in \mathbb{Z}\, \Big( \, \exists \, a \in \mathbb{Z} : \, \exists \, b \in \mathbb{Z} : d \,| \,(ax+by) \implies d \, | \, x \, \wedge \, d \, | \, y \, \Big)$$

or more compactly

$$\forall \, x ,y,z \in \mathbb{Z}\,\Big(\exists \, a,b \in \mathbb{Z} : d \, | \, (ax+by) \implies d \, | \, x \wedge d \, | \, y \, \Big)$$

Thus, if we wish to find a counterexample, we would consider the negation $$\exists \, x,y,z \in \mathbb{Z} : \,\Big[\exists a,b \in \mathbb{Z} : d \, | \, (ax+by) \, \wedge \big(d \, \nmid x \lor d\, \nmid y\big)\,\Big]$$

Given this structure, here is my counterexample below. You can expose the yellow area by hovering your mouse over it.

Let $$a = 2, x = 5, b = 3, y = 2,$$ and $$d=2$$. Then $$d \, | \, (ax + by)$$, since using our assignments yields $$2 \, | \, 16$$, but $$d \nmid x$$, because $$2 \nmid 5$$.

Your rewritten version is not quite correct (in fact, the rewritten statement is true while the original statement is false). Your rewritten version could be stated as "Let $$x$$ and $$y$$ be integers. Then there is some $$d \in \mathbb{Z}$$ such that, if there exists $$a, b \in \mathbb{Z}$$ such that $$d \mid (ax + by)$$, then $$d \mid x$$ and $$d \mid y$$." You should convince yourself that this statement is true, and not equivalent to the original statement!

You should have written something like "$$\forall x,y,d \in \mathbb{Z} (\exists a,b \in \mathbb{Z} (d \mid (ax + by)) \implies (d \mid x \land d \mid y))$$" instead. The important thing is that the question does not ask if there exists a $$d$$ such that $$\exists a,b \in \mathbb{Z} (d \mid (ax + by)) \implies (d \mid x \land d \mid y)$$. It asks if $$\exists a,b \in \mathbb{Z} (d \mid (ax + by)) \implies (d \mid x \land d \mid y)$$ is true regardless of the value of $$d$$. Thus, $$d$$ should be universally quantified.

To show that the statement $$\forall x,y,d \in \mathbb{Z} (\exists a,b \in \mathbb{Z} (d \mid (ax + by)) \implies (d \mid x \land d \mid y))$$ is false, you must provide specific values of $$x, y, d \in \mathbb{Z}$$ such that $$\exists a,b \in \mathbb{Z} (d \mid (ax + by)) \implies (d \mid x \land d \mid y)$$ is false; i.e. $$\exists a,b \in \mathbb{Z} (d \mid (ax + by))$$ and $$\lnot (d \mid x \land d \mid y)$$ are both true.