0
$\begingroup$

I can see that it is true for all cases where $n$ is not divisible by $3$, such as $n = 1$, $n = 2$, $n = 4$, etc. However I can't figure out how to prove it.

$\endgroup$
  • $\begingroup$ Consider the two possible remainders for $n$ when divided by 3. What happens when you square in each case? $\endgroup$ – almagest May 24 '16 at 8:54
  • 2
    $\begingroup$ related in a more general setting: en.wikipedia.org/wiki/Fermat's_little_theorem $\endgroup$ – Math-fun May 24 '16 at 9:25
2
$\begingroup$

There are three mutually exclusive cases for an integer $n$:

  1. $n\equiv 0\pmod{3}$ (that is, $n$ is divisible by $3$);
  2. $n\equiv 1\pmod{3}$
  3. $n\equiv 2\pmod{3}$

In case 2, $n^2\equiv 1\pmod{3}$; in case 3, $$ n^2\equiv 4\equiv 1\pmod{3} $$

Just recall that from $a\equiv b\pmod{k}$ and $c\equiv d\pmod{k}$ you can deduce that $ac\equiv bd\pmod{k}$.

$\endgroup$
1
$\begingroup$

Hint:

Just observe that $2\equiv -1\mod3$.

$\endgroup$
1
$\begingroup$

We have to show that $3$ divides $(n-1)(n+1)$. Since $3$ does not divide $n$, the statement is equivalent to the fact that $3$ divides $(n-1)(n+1)n$ or $(n-1)n(n+1)$. This equivalence of statements can be observed from prime decomposition or can be proven directly. But $(n-1)n(n+1)$ is just product of $3$ consecutive numbers, so obviously it is divisible by $3$.

This proof is not as rigorous as others, but it gives you some alternative intuition related to the problem.

$\endgroup$
1
$\begingroup$

Any number $n\in\mathbb{Z}$ can be written as $n=3k+c$, where $c\in\lbrace 0,1,2\rbrace$. This is just saying that $n\equiv c\bmod 3$.

Now that we've written $n=3k+c$, let's try squaring this. This gives us $$n^2=(3k+c)^2=9k^2+6ck+c^2=3(k^2+2ck)+c^2.$$ Now, we know $c\neq 0$, so it follows that $c=1$ or $c=2$. Either way, $c^2\bmod 3=1$. So, we have that $$n^2\bmod 3=\underbrace{3(k^2+2ck)}_{0}\bmod 3+1\bmod 3=1\bmod 3.$$

$\endgroup$
  • $\begingroup$ One could speed up this process by using the fact that any number not divisible by 3 can be written as (3k +/- 1) $\endgroup$ – DJohnM May 25 '16 at 15:21
0
$\begingroup$

Consider the following cases:

  • $n\equiv\color\red1\pmod3 \implies n^2\equiv\color\red1^2\equiv3\cdot0+1\equiv1\pmod3$
  • $n\equiv\color\red2\pmod3 \implies n^2\equiv\color\red2^2\equiv3\cdot1+1\equiv1\pmod3$
$\endgroup$

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.