Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
Hinton: \mathbb{Z} produces the "blackboard bold" Z. – Arturo Magidin Nov 15 '10 at 1:17
up vote 3 down vote accepted

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

share|cite|improve this answer
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.

share|cite|improve this answer
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)$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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