# Prove or disprove: For every integer a, if a is not congruent to 0 (mod 3), the a^2 is congruent to 1 (mod 3)

Prove or disprove: For every integer a, if a is not congruent to 0 (mod 3), the a^2 is congruent to 1 (mod 3)

SO this is for abstract algebra and I am really struggling with this. Here are some of the definitions and theorems I think would apply.

-an integer a divides and integer b if there is an integer q such that b=aq -Let a and b be integers, with a>0. Then there exist unique integers q and r such that b= aq+r and 0<=r

The question says hint: use 2 cases but I'm not really sure what that means. I'm guessing it wants me to look at it when a is congruent to 0 and when it's not? so i tried to do that but just ended up stuck. below is as far as i got with that attempt

Proof: Case 1 There should be some information about letting variables exist in certain number sets here

assume a is not congruent to 0 mod 3, then 3 does not divide a-0, therefore a-0 does not equal 3q for some q in the integers

I was trying to get this to wind down to thus 3 divides a^2-1 but even tho it seems true (I couldn't find a counter example) I couldn't figure out how to prove it with what I have.

Next i tried reversing it thinking I could contradict it or something. I think this would be case 2? assume a is congruent to 0 mod 3, then 3 divides a-0 and a-0=3q for some q in the integers, then 3q=a since 0 is the additive identity, therefore 3 divides a,

and again stuck and my brain hurts a little.. Can anyone help me figure out how to work this.

• Hint : Take an example – Shobhit Jan 27 '15 at 2:13
• If $a\no\equiv 0\pmod{3}$, then $a\equiv \pm 1\pmod{3}$. So $a^2\equiv (\pm 1)^2\equiv 1\pmod{3}$. – André Nicolas Jan 27 '15 at 2:16

If $a$ is not a multiple of $3$, either one of these must hold:

$a \equiv 1 \pmod 3$

or $a \equiv 2 \pmod 3$

Basically, those are saying that the remainder on dividing $a$ by $3$ is either $1$ or $2$.

Now, the second can also be expressed as $a \equiv -1 \pmod 3$

So everything can be more concisely expressed as $a \equiv \pm 1 \pmod 3$,

allowing us to square easily giving: $a^2 \equiv 1 \pmod 3$.

• Thanks so much I'll work on this again tomorrow and see if I can get it with your guys suggestions – Mikky Davey Jan 27 '15 at 3:17

Hint $\ 3\,$ divides one of $\,a\!-\!1,\,a,\,a\!+\!1,\$ so $\ 3\nmid a\,\Rightarrow\,3\mid(a\!-\!1)(a\!+\!1) = a^2\!-1$

Remark$\$ Said modly, $\ {\rm mod}\ 3\!:\ a\not\equiv 0\,\Rightarrow\, a\equiv \pm 1\,\Rightarrow\, a^2\equiv 1$

• You guys have been awesome thanks so much for laying it out. I'll attempt it again before class in the morning – Mikky Davey Jan 27 '15 at 3:18

For the two cases I think one case is letting the integer be $(3n+1)$ and the other be $(3n+2)$. Squaring both reveals what you need I believe.

• I hadn't thought of that. Thanks I'll try that tomorrow. – Mikky Davey Jan 27 '15 at 3:17

For a in (mod 3), there are three different kinds of numbers:

• a = 3m
• a = 3m+1
• a = 3m+2

We can take the last 2 which aren't equal to 0 (mod 3)

The second one:

$$a^2 = (3m+1)^2$$ $$= 9m^2 + 6m + 1$$ $$= 3(3m^2 + 2) + 1$$ $$= 3k + 1, k = 3m^2 + 2\in \Z^+$$ $$\equiv 1\mod 3$$

The third one:

$$a^2 = (3m+2)^2$$ $$= 9m^2 + 12m + 4$$ $$= 3(3m^2 + 4 + 1) + 1$$ $$= 3j + 1, j = 3m^2 + 4 + 1\in \Z^+$$ $$\equiv 1\mod 3$$