Elementary Number Theory Proof

[tylerc1991]

Homework Statement

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

Homework Equations

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

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!

 

[Yuqing]

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

 

[tylerc1991]

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

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

 

[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 = m² but rather that there does not exist q as a multiple of m such that 3q = m².

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.

 

[tylerc1991]

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.

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?

 

[Yuqing]

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

 

[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. :)

 

[tylerc1991]

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. :)

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)

 

[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.