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.

  • 1
    $\begingroup$ Hint : Take an example $\endgroup$ – Shobhit Jan 27 '15 at 2:13
  • $\begingroup$ 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}$. $\endgroup$ – 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$.

  • $\begingroup$ Thanks so much I'll work on this again tomorrow and see if I can get it with your guys suggestions $\endgroup$ – 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$

  • $\begingroup$ You guys have been awesome thanks so much for laying it out. I'll attempt it again before class in the morning $\endgroup$ – 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.

  • $\begingroup$ I hadn't thought of that. Thanks I'll try that tomorrow. $\endgroup$ – 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 $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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