# Is this an acceptable congruency proof?

I have a past exam question that I proved as follows: $$(\forall n\in \Bbb Z)\bigl((3n^2-5\equiv 2 \pmod 4)\lor(3n^2-5\equiv 3 \pmod 4)\bigr)$$ If odd: $$3n^2 - 7 = k4,k\in \mathbb Z$$ $$3(2l+1)^2 - 7 = k4, l\in \mathbb Z$$ $$12l^2+12l-4 = 4k$$ $$3l^2+3l-1=k$$

If even $$3n^2 - 8 = k4$$ $$3(2l)^2 - 8 = k4, l\in \mathbb Z$$ $$12l^2 -8 = 4k$$ $$3l^2-2=k$$

$$\therefore \forall n \in \mathbb Z, 3n^2 - 5 \equiv (2\mod 4) \lor (3 \mod 4)$$ Is this a sufficient proof for this question? Any tips to improve?

Edit: Also I feel like I got lucky with the whole even or odd thing, and I don't want to rely on that in the exams, how do people determine how they are going to attack this sort of problem? Or is it a matter of lots of practice?

• @dfeuer Sorry what notation specifically? – Display Name Oct 22 '13 at 5:29
• @dfeuer, yes sorry, that is the symbol I was looking for for congruency, and that Is what I meant. – Display Name Oct 22 '13 at 5:32
• Where does the $3n^2-7=k4$ come from? – dfeuer Oct 22 '13 at 5:34
• @dfeuer $3n^2 - 5 \equiv 2 \mod 4$ is the same as $3n^2 - 7 \equiv 4k, k \in \mathbb Z$ Just saying that it is some factor of 4. – Display Name Oct 22 '13 at 5:39
• Your logic is sound, but as stated it implies nothing. The last lines just say they are equal to some integer. Implication lines may be helpful. – chubakueno Oct 22 '13 at 5:48

If that is the requested proof style, probably you proved the thing; but my opinion is “that's cryptography, rather than mathematics“. You probably have better to say that you're going to find $k$, assuming that $n$ is odd or even.

But before plunging in algebraic substitutions, it's better to simplify the problem. You'll probably see how the exercise was conceived.

The statement is equivalent to showing that $3n^2\equiv 2+5\pmod{4}$ or $3n^2\equiv3+5\pmod{4}$ that's the same as $$3n^2\equiv 3\pmod{4}\quad\text{or}\quad 3n^2\equiv0\pmod 4$$ Since $3\cdot3=9\equiv 1\pmod{4}$, the statement becomes $$n^2\equiv 1\pmod{4}\quad\text{or}\quad n^2\equiv0\pmod 4$$ Now it should be easier.

First of all, the last line does not mean anything. You cannot put "$\vee$" between two non-propositional expressions.

Second of all, if you did not write any comment to this proof, it's not understandable at all. I did not understand what you assumed and what you reached. But I'm assuming that you first assumed $n$ is odd, and tried to showed something that I could not understand. You assume that proposition is true, and tried to show that there is no contradiction, I suppose. Then, did the same thing with the assumption $n$ is even. But this is not the way of proving things. Showing that there is no contradiction between two propositions does not implies that they are both true. What if they're both false? Or is there a contradiction between "Today is rainy in Istanbul" and "Today is not rainy in New York". No, but when you prove that "Today is rainy in Istanbul", can you say that "Today is not rainy in New York"? Of course not.

What you had to do was to assume that the proposition was false. That is:

$$\neg( \forall n\in \mathbb{Z}, ((3n^2−5≡2(mod4))∨(3n^2−5≡3(mod4)))$$ $$\implies \exists n \in \mathbb{Z}, \neg ((3n^2−5≡2(mod4))∨(3n^2−5≡3(mod4))$$

Start your proof with that assumption and show that there is a contradiction.

• What is meant is that "For all integers $n$, $3n^2 - 5$ is either congruent to 2 modulo 4 or congruent to 3 modulo 4." I have then shown that 4 does devide 3n^2 - 5 for all cases(even and odd encompass this), with a remainder of either two or three. I have shown that since k is the multiple of 4 against the given remainder, and that four divides this with the remainder is still integer, that it is true. – Display Name Oct 22 '13 at 7:22
• Again, you cannot simplify your expression by putting the $\vee$ symbol between $(2\,mod\,4)$ and $(3\,mod\,4)$. It does not have any meaning as $\vee$ is a logical symbol only. And without comments, it's impossible to understand that what you've shown is that. Besides, you're showing what you're trying to show by assuming itself. $3n^2 - 7 = 4k$ should be what you've reached, not what you start with. But if you're strugling with starting from somewhere else, then just assume that $3n^2 - 7 \neq 4k$ and show the contradiction. – Zafer Sernikli Oct 22 '13 at 7:44
• I see what you mean, I was trying to test if 4 divided neatly, this is a first semester uni course, so either it would have divided neatly, or it wouldn't have divided out at all, which would have meant that I needed to change how I went at the problem. I am sorry for misusing the disjunction symbol, I was merely throwing it in to mean 'or'. – Display Name Oct 22 '13 at 7:50
• Yes, you have to change your look at the problem. Even though what you've done seems to you like you've proved the proposition, it's actually mathematically and logically meaningless, because you have not shown anything. And again, assuming that the proposition is false and pointing out a contradiction is usually the best way of proving such theorems; because you can avoid from the problem "where to start" with that beginning. – Zafer Sernikli Oct 22 '13 at 8:06