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.
$\endgroup$ 24 Answers
$\begingroup$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$
$\endgroup$ 1 $\begingroup$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$.
$\endgroup$ 1 $\begingroup$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.
$\endgroup$ 1 $\begingroup$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 $$
$\endgroup$
