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
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.
No comments:
Post a Comment