Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 3 down vote favorite

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!

share|improve this question
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... – anon Mar 22 '12 at 15:36
4  
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. – Gone Mar 22 '12 at 17:58

3 Answers

up vote 6 down vote accepted

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,

share|improve this answer
up vote 5 down vote

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

share|improve this answer
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
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. – Gone Mar 22 '12 at 15:54
up vote 4 down vote

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.