# Congruency proof

The question states: If $a \in \mathbb{Z}$, prove that $a^2$ is not congruent to 2 modulo 4 or 3 modulo 4.

Our work: It's an if then proof, so I am thinking we can do a contradiction proof. Suppose $a^2 \equiv 2 \pmod{4}$ and $a^2 \equiv 3 \pmod{4}$. Then you can write by definition \begin{align*} a^2 &= 4k + 2 \\\ a^2 &= 4k + 3 \end{align*}

but hold on, another way to write 2 mod 4 is $[2]_{4}$ which means the infinite set of all the integers in the form of $2 + 4k$ and $[3]_{4}$ which means the infinite set of all the integers in the form of $3 + 4k$.

so we one set is a set of even integers and one set is of odd integers. but our a^2 can't be in both right?

-
Hinton: \mathbb{Z} produces the "blackboard bold" Z. – Arturo Magidin Nov 15 '10 at 1:17

Hint: There are only 4 possible choices for $a$ modulo $4$. You can explicitly look at each one and calculate $a^2$ modulo $4$.

-
can you give me a hint. – Tyler Hilton Nov 15 '10 at 1:23
I think Brandon's hint should be more than enough. Take each choice for $a \mod (4)$ and then find what happens to $a^2 \mod (4)$ – user17762 Nov 15 '10 at 1:25
but its not a mod 4.. its $a^2 \equiv 2 \pmod{4}$. I dont get what you mean by possibilites? maybe i am missing something. – Tyler Hilton Nov 15 '10 at 1:36
are the four possiblities the following: $[a^2]_{0}, [a^2]_{1}, [a^2]_{2}, [a^2]_{3}$ and do we have to check that 2 is not an element in any of these sets? – Tyler Hilton Nov 15 '10 at 1:38

You cannot assume both that $a^2\equiv 2\pmod{4}$ *and* that $a^2\equiv 3\pmod{4}$. Your "assumption" should be "either $a^2\equiv 2\pmod{4}$ *OR* $a^2\equiv 3\pmod{4}$." That is, you need to do it by cases.

This because your assumption for a proof by contradiction should be exactly the negation of your conclusion, not something else. Your conclusion here is $$\neg\left( a^2\equiv 2\pmod{4} \text{ or } a^2\equiv 3\pmod{4}\right)$$ so the negation is just the statement that either $a^2$ is $2$ *or* $3$ modulo $4$.

So, no; you're not doing it right here, because your "assumption for contradiction" is not the correct one.

-
so how do I begin this proof? – Tyler Hilton Nov 15 '10 at 1:25
am i on the right track? – Tyler Hilton Nov 15 '10 at 1:25
@Tyler Hinton: As I mentioned: if you want to do it by contradiction, then first assume that $a^2\equiv 2\pmod{4}$ and reach a contradiction; then assume that $a^2\equiv 3\pmod{4}$ and reach a contradiction based on that. Only then can you claim that you have done the full proof by contradiction. But a better way is to follow Brandon Carter's hint: there are four possibilities for $a$ modulo $4$ to begin with, so check what kind of $a^2$ they give you; if none of them give you $2$ or $3$, you're done. – Arturo Magidin Nov 15 '10 at 1:27
@Tyler Hinton: The problem with what you have done so far is that it is worthless, because the contradiction you obtained derived from the fact that you made a contradictory assumption; so the entire line of argument you have doesn't get you anything. You need to start from scratch. – Arturo Magidin Nov 15 '10 at 1:29

HINT $\rm\quad (2\:n)^2\ =\ 4\:n^2,\quad (2\:n+1)^2\ =\ 4\:(n^2+n)+1\ \$ so squares are $\rm\equiv 0,\: 1\ (mod\ 4)$

-