I am trying to show that $n^2 \bmod 3 = 0$ implies $n \bmod 3 = 0$.
This is a part a calculus course and I don't know anything about numbers theory. Any ideas how it can be done? Thanks!
I am trying to show that $n^2 \bmod 3 = 0$ implies $n \bmod 3 = 0$.
This is a part a calculus course and I don't know anything about numbers theory. Any ideas how it can be done? Thanks!
Hint: Try to show that $n \bmod 3 \ne 0$ does imply $n^2 \bmod 3 \ne 0$. Consider the cases $n \bmod 3 = 1$ and $n \bmod 3 = 2$. If for example $n \bmod 3 = 1$, we can write $n = 3k+1$, what follows for $n^2$?
HTH, AB,
Hint $\rm\ (1+3k)^2 = 1 + 3\:(2k+3k^2)$
and $\rm\ \ \ (2+3k)^2 = 1 + 3\:(1+4k+3k^2)$
Said mod $3\!:\ (\pm1)^2 \equiv 1\not\equiv 0\ \ $ (note $\rm\: 2\equiv -1$)
The natural way to think about the problem is that since $n^2$ is divisible by 3, hence prime factorization of $n^2$ contains at least one 3 in it(since 3 is a prime number). If so is the case, then prime factorization of $n$ must contains 3 in it.