# Elementary Number Theory Proof

1. Aug 24, 2011

### tylerc1991

1. The problem statement, all variables and given/known data

If $3 | m^2$ for some integer $m$, then $3 | m$.

2. Relevant equations

$a | b$ means there exists an integer $c$ such that $b = ca$.

3. The attempt at a solution

I realize that this is a corollary to Euclid's first theorem, and that there are plenty of ways to solve this. However, I need an elementary proof using basic rules of arithmetic and algebra.

$3 | m^2 \quad \iff \quad m^2 = 3k$ for some integer $k$.

So then $3 = \frac{m^2}{k}$.

At this point it seems intuitively obvious that $m$ must be a multiple of 3, but it obviously doesn't qualify as a proof. Could someone give me a nudge in the right direction? Thank you very much!

2. Aug 24, 2011

### Yuqing

Try to prove the contrapositive: If 3 does not divide m then it does not divide m2

3. Aug 24, 2011

### tylerc1991

Something like this?:

Suppose $3 \nshortmid m$.

Then there does not exist an integer $k$ such that $3k = m$.

Therefore there does not exist an integer $k$ such that $3km = m^2$.

But $km$ is just an integer, we can call it $q$.

Hence, there does not exist an integer $q$ such that $3q = m^2$.

Therefore, $3 \nshortmid m^2$.

4. Aug 24, 2011

### Yuqing

I don't really think that proof is valid as it's not a proof that there does not exists any integer q such that 3q = m2 but rather that there does not exist q as a multiple of m such that 3q = m2.

I was actually thinking more along the lines of something like $$a \not\equiv 0\ (mod\ 3) \Longrightarrow a^2 \not\equiv 0\ (mod\ 3)$$ which only requires knowledge that $\mathbb{Z}_3$ is a field.

It all depends on exactly how elementary you want to get. If you do not wish to invoke Euclid's lemma or the fundamental theorem of arithmetic then the proof is a bit tedious.

Last edited: Aug 24, 2011
5. Aug 24, 2011

### tylerc1991

This is just a lemma that will be used to show that $sqrt{3}$ is irrational, so you can imagine how elementary the proof must be. I would say that using the fundamental theorem of arithmetic would be allowed, but I don't see how that would be useful?

6. Aug 24, 2011

### Yuqing

With the fundamental theorem of arithmetic, we can see that the every prime power which divides m2 must have even exponent. Since 3 divides m2 it follows that 9 must, meaning if 3k = m2 then k = 3n for some n (which must also be a square).

7. Aug 24, 2011

### icystrike

Start by assuming 'm' has certain prime factorisation. Then you write down the prime factorisation for 'm' square. Hence compare with your rhs and conclude that one of the prime factor is 3. :)

8. Aug 24, 2011

### tylerc1991

Wouldn't that be assuming the conclusion though? Shouldn't we start with some property about $m^2$ and work towards some property about $m$? (i.e. that it is divisible by 3)

9. Aug 24, 2011

### mathwonk

notice that all integers have form n = 3k, n = 3k+1, or n= 3k+2. then check cases. i.e it follows that if 3 divides n^2, then n = 3k. so 3 divides n.