# Proving that a natural number is divisible by $3$

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!

-
The definition of a prime number is that $p|ab\Rightarrow p|a\text{ or }p|b$, which makes this rather tautological in view of 3 being prime... –  anon Mar 22 '12 at 15:36
What on Earth is this doing in a calculus course? –  Peter Taylor Mar 22 '12 at 15:45
@anon: That is not the usual definition of a prime, is it? –  Harald Hanche-Olsen Mar 22 '12 at 16:08
@Harald: Depending on where you are in number theory, it is (I suppose prime just means irreducible in elementary NT so my comment wasn't really helpful). –  anon Mar 22 '12 at 16:16
@anon It's not quite a tautology since $\rm\:q\ |\ n^2\:\Rightarrow\:q\ |\ n\:$ is true iff $\rm\:q\:$ is squarefree, 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. –  Bill Dubuque Mar 22 '12 at 17:58

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

-
If I could elaborate (since the OP might not be able to connect the dots, even of this good hint)... The contrapositive of the statement $$n^2 \mod 3 = 0 \Rightarrow n \mod 3 = 0$$ is $$n \mod 3 \neq 0 \Rightarrow n^2 \mod 3 \neq 0$$. This is what Bill is showing. There are two options for $n$ if it is not $0$ mod 3... n = 3k + 1 or n = 3k + 2 (here Bill and I are using "n" in different ways...) –  The Chaz 2.0 Mar 22 '12 at 15:50
@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. –  Bill Dubuque Mar 22 '12 at 15:54

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.

-