Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Elementary Number Theory Proof

  1. Aug 24, 2011 #1
    1. The problem statement, all variables and given/known data

    If [itex] 3 | m^2 [/itex] for some integer [itex]m[/itex], then [itex] 3 | m[/itex].

    2. Relevant equations

    [itex] a | b [/itex] means there exists an integer [itex]c[/itex] such that [itex]b = ca[/itex].

    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.

    [itex]3 | m^2 \quad \iff \quad m^2 = 3k[/itex] for some integer [itex]k[/itex].

    So then [itex]3 = \frac{m^2}{k}[/itex].

    At this point it seems intuitively obvious that [itex]m[/itex] 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. jcsd
  3. Aug 24, 2011 #2
    Try to prove the contrapositive: If 3 does not divide m then it does not divide m2
  4. Aug 24, 2011 #3
    Something like this?:

    Suppose [itex]3 \nshortmid m[/itex].

    Then there does not exist an integer [itex]k[/itex] such that [itex]3k = m[/itex].

    Therefore there does not exist an integer [itex]k[/itex] such that [itex]3km = m^2[/itex].

    But [itex]km[/itex] is just an integer, we can call it [itex]q[/itex].

    Hence, there does not exist an integer [itex]q[/itex] such that [itex]3q = m^2[/itex].

    Therefore, [itex]3 \nshortmid m^2[/itex].
  5. Aug 24, 2011 #4
    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 [tex]a \not\equiv 0\ (mod\ 3) \Longrightarrow a^2 \not\equiv 0\ (mod\ 3)[/tex] which only requires knowledge that [itex]\mathbb{Z}_3[/itex] 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
  6. Aug 24, 2011 #5
    This is just a lemma that will be used to show that [itex]sqrt{3}[/itex] 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?
  7. Aug 24, 2011 #6
    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).
  8. Aug 24, 2011 #7
    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. :)
  9. Aug 24, 2011 #8
    Wouldn't that be assuming the conclusion though? Shouldn't we start with some property about [itex]m^2[/itex] and work towards some property about [itex]m[/itex]? (i.e. that it is divisible by 3)
  10. Aug 24, 2011 #9


    User Avatar
    Science Advisor
    Homework Helper

    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook