3
$\begingroup$

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!

  • 0
    @anon It's not quite a tautology since $\rm\:q\ |\ n^2\:\Rightarrow\:q\ |\ n\:$ is true [iff $\rm\:q\:$ is squarefree](http://math.stackexchange.com/a/54105/242), which is not equivalent to $\rm\:q\:$ is prime, since, e.g. products of distinct primes are squarefree, but are prime iff the product has $1$ factor.2012-03-22

3 Answers 3

6

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,

5

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$)

  • 1
    @TheChaz Indeed, being an exercise in a calculus book, it may be intended to illustrate proof by contradiction /contrapositive. Probably one cannot assume known any nontrivial number theory.2012-03-22
4

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.