Confused about a neither statement and modular

Question

I am trying currently in the process of learning proofs involving congruence of integers with methods of direct and contrapositive and proofs with cases. However, I am quite confused by this statement as follows:

Let $a,b\in Z$. Prove that if $a^2+2b^2\equiv 0\ (\mathrm{mod\ 3})$, then either $a$ and $b$ are both congruent to $0$ modulo $3$ or neither is congruent to $0$ modulo $3$.

I am trying to do this with a proof by contrapositive where I let $$q(a,b): \text{either } a \text{ and } b \text{ are both congruent to } 0 \text{ modulo } 3 \text{ or neither is congruent to } 0 \text{ modulo 3}.$$ $$p(a,b): a^2 + 2b^2 \equiv 0 (\text{ mod 3 )}$$

However, by using the negation of $q$, I am left with $(3 \nmid a \cup 3\nmid b) \cap (3 \mid a \cup 3 \mid b)$. Since I interpreted the negation of $q$ as being $$\neg ((3\mid a \cap 3 \mid b) \cup (3\nmid a \cap 3\nmid b))=\neg (3\mid a \cap 3 \mid b) \cap \neg(3\nmid a \cap 3\nmid b)$$

Am I doing something wrong here ? I think it is with the negation of $q$ that I am having trouble with and it would be nice if someone could help explain.

Thank you.

Answer 1

I don't think using formal proofs is the way to go here, but anyway... (I suggest you read from where I put a $\star$ on, closer to the bottom of the answer.)

Consider the usual axiom for congruence modulo $3$, with variables $a,b,c,\ldots$. The problem you have is to prove that $$\vdash (a^2+2b^2=0)\rightarrow(((a=0)\land(b=0))\lor((a\neq 0)\land(b\neq 0))) $$ (where equality means congruence modulo $3$). By contrapositive, this is the same as proving. $$\vdash(((a\neq 0)\lor(b\neq 0))\land((a=0)\lor(b=0)))\rightarrow(a^2+2b^2\neq 0)$$ Now, note that $(a=0)\lor(a\neq 0)$ is a tautology, so this is the same as proving \begin{align*} \vdash&\left((a=0)\lor(a\neq 0)\right)\land\left((((a\neq 0)\lor(b\neq 0))\land((a=0)\lor(b=0)))\rightarrow(a^2+2b^2\neq 0)\right)\\ &=\left(((a=0)\lor(a\neq 0))\land\left((((a\neq 0)\lor(b\neq 0))\land((a=0)\lor(b=0)))\right)\right)\to(a^2+2b^2\neq 0) \end{align*} Now look at the term on the left. Using distributivity, it is the same as $$\left((a=0)\land(((a\neq 0)\lor(b\neq 0))\land((a=0)\lor(b=0)))\right)\lor\left((a\neq 0)\land(((a\neq 0)\lor(b\neq 0))\land((a=0)\lor(b=0)))\right)$$

Now look just at the first term above, use transitivity and distributivity and get $$(((a=0)\land(a\neq 0))\lor((a=0)\land(b\neq 0)))\land((a=0)\lor(b=0))$$ But $(a=0)\land(a\neq 0)$ is always false, so the first term is equivalent to $(a=0)\land(b\neq 0)$, and this expression becomes $$(a=0)\land(b\neq 0)\land((a=0)\lor(b=0))$$ Now you use distributivity, associativity, and what-nots, and see after a few minutes that this is equivalent to $$(a=0)\land (b\neq 0)$$ Now look at the second term, do a bunch more of stuff and see it is equivalent to $(a\neq 0)\land(b=0)$.

So the problem now becomes to prove \begin{align*} \vdash&(((a=0)\land(b\neq 0))\lor((a\neq 0)\land(b=0))\rightarrow(a^2+2b^2\neq 0)\\ &=(((a=0)\land(b\neq 0))\rightarrow(a^2+2b^2\neq 0))\land(((a\neq 0)\land(b=0))\rightarrow(a^2+2b^2\neq 0)) \end{align*}

Now we have a conjuntion on the right-hand side, so this is equivalent to proving the two problems $$\vdash((a=0)\land(b\neq 0))\rightarrow(a^2+2b^2\neq 0)$$ $$\vdash((a\neq0)\land(b=0))\rightarrow(a^2+2b^2\neq 0)$$ Now for each of these problems, you do a bunch more stuff an finally prove it, somehow, hopefully...

---

$\star$ Do you see why logic is not very well-suited to prove this problem? Instead if we stated problem in a manner which we can easily understand: The contrapositive becomes

Suppose $3$ does not divide $a$ and $b$ simultaneously, and that $3$ divides at least one of $a$ and $b$. Then $3$ does not divide $a^2+2b^2$. (This is just a translation of the contrapositive you got.)

There are a bunch of ways to solve this. The second phrase in the hypothesis means that $3$ divides at least one between $a$ and $b$. Here we have two cases (yes, we can verify cases separately):

CAse 1: $3$ divides $a$.

Then by the first phrase in the hypothesis, $3$ does not divide $b$, so either $b\equiv 1\mod{3}$ or $b\equiv 2\mod{3}$. In either case (yes, we take subcases and verify them separately again), $b^2\equiv 1\mod{3}$ and $a^2+2b^2\equiv 2\mod{3}$.

CASE 2: $3$ does not divide $a$.

By the second phrase in the hypothesis, $3$ divides $b$, and therefore $a^2+2b^2\equiv 1\mod{3}$ (here, again, we have two subcases: $a\equiv 1$ or $2\mod{3}$, and in each subcase $a^2\equiv 1\mod{3}$)

---

Remark 1: There are other ways of separating the problem in cases. For example, one of the hypothesis is that $3$ divides at least one of $a$ and $b$, so we could separate in the cases that $3$ divides $a$ (as above), or that $3$ divides $b$ (and then verify things in this case).

---

Remark 2: One can also prove the theorem directly by separating in the cases where $3$ divides $a$ or not.

---

Remark 3: To avoid having to consider subcases in several parts, you can prove, as a lemma, that for every $x$ not divisible by $3$, $x^2\equiv 1\mod{3}$. Then use this when $3$ does not divide $a$ or $b$. However, the proof of this lemma will probably be divided in two cases.

Answer 2

The risk in the "logic" approach is that one may lose control of the logic of the argument. But we will set things using the your notation. (But we use $\land$ and $\lor$ instead of $\cap$ and $\cup$.)

The negation of $q(a,b)$ is $$(3\mid b)\land \lnot(3\mid b))\lor (\lnot(3\mid a)\land (3\mid b)).$$ To prove this is false, we need to prove that $(3\mid b)\land \lnot(3\mid b))$ is false, and $(\lnot(3\mid a)\land (3\mid b))$ is false. These should be straightforward. For the first, it is enough to show that if $3\mid a$ then $3\mid b$.