1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Your negation of $q$ is correct. Assume $\lnot q$ is true. Now you can consider two cases: $3|a$ or $3\not |a$. In each case, prove that $a^2+2b^2$ is not congruent to $0$ modulo $3$. $\endgroup$ – Luiz Cordeiro May 3 '16 at 3:33
  • $\begingroup$ @LuizCordeiro Yes, but would about $b$ though ? Because according to the $\neg q = \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) = (3 \nmid a \cup 3 \nmid b ) \cap (3\mid a \cup 3 \mid b)$ I'm somewhat perplexed and unsure about how to proceed from the last negation $\endgroup$ – PutsandCalls May 3 '16 at 3:44
  • $\begingroup$ I really don't think using logical proofs is the best way to proceed in this exercise, or even if it is feasible at all. I will try to explain better in an answer. $\endgroup$ – Luiz Cordeiro May 3 '16 at 3:54
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you for the detailed answer ! And yes, I see your point now, I was actually stuck at the fact that $(a=0)\land(a\neq 0)$ is a contradiction which is what confused me, and I guess thats why there was a problem with the logic part. I suppose that an important takeaway is to not always apply the idea of logic when encountering "and" or "neither" ? $\endgroup$ – PutsandCalls May 3 '16 at 5:15
  • $\begingroup$ @PutsandCalls Yes, that is the point more or less. You should however be able to translate phrases from common language (english, in this case) to formal phrases (using symbols) and vice-versa. Sometimes it is a little confusing to take negatives of phrases in common language, and in those cases working with formal phrases step-by-step is safer. $\endgroup$ – Luiz Cordeiro May 3 '16 at 6:21
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Yes I see what you mean by the risk in losing control of the argument. However, in considering $(3 \mid b) \wedge \neg(3 \mid b)$, how should I define $b$ according to this if I assume that it is true? In the solutions, the approach used was to consider the cases where: 1)$3\nmid a$ and $3 \mid b$, 2) $3 \mid a$ and $3\nmid b$. I am trying to see how this was arrived at, which I am currently lacking $\endgroup$ – PutsandCalls May 3 '16 at 4:19
  • $\begingroup$ The two parts of the argument are essentially identical. If $3\mid a$ then $3\mid a^2$. If furthermore $a^2+2b^2\equiv 0\pmod{3}$, then $3\mid 2b^2$ and therefore $3\mid b$. If the "therefore" is unfamiliar, note that if $b\equiv 1\pmod{3}$ then $b^2\equiv 1\pmod{3}$ and therefore $2b^2\equiv 2\pmod{3}$, contradicting the fact that $3\mid 2b^2$. And if $b\equiv 2\pmod{3}$, again we find that $2b^2\equiv 2\pmod{3}$. $\endgroup$ – André Nicolas May 3 '16 at 4:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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