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!

  • 2
    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...2012-03-22
  • 4
    What on Earth is this doing in a calculus course?2012-03-22
  • 0
    @anon: That is not the usual definition of a prime, is it?2012-03-22
  • 0
    @Harald: Depending on where you are in number theory, [it is](http://en.wikipedia.org/wiki/Prime_number#Prime_elements_in_rings) (I suppose prime just means irreducible in elementary NT so my comment wasn't really helpful).2012-03-22
  • 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$)

  • 0
    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...)2012-03-22
  • 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.