3
$\begingroup$

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?

  • 1
    Hinton: `\mathbb{Z}` produces the "blackboard bold" **Z**.2010-11-15

3 Answers 3

3

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

  • 0
    can you give me a hint.2010-11-15
  • 3
    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)$2010-11-15
  • 0
    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.2010-11-15
  • 0
    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?2010-11-15
1

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.

  • 0
    so how do I begin this proof?2010-11-15
  • 0
    am i on the right track?2010-11-15
  • 1
    @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.2010-11-15
  • 1
    @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.2010-11-15
1

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