1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

##n^2## is divided by 3, then n is also divided by 3.

  1. Feb 15, 2015 #1
    1. The problem statement, all variables and given/known data
    Prove that if ##n^2## is divided by 3, then also n can also be divided by 3.

    2. Relevant equations


    3. The attempt at a solution

    Is there anything wrong with this argument?

    By contradiction, suppose ##3|n## and 3 doesn't divide ##n^2##.
    Then ##3m = n##. Multiple both sides by ##n##
    $$
    3(mn) = n^2
    $$
    Thus, ##3|n^2## and we have reached a contradiction. Therefore, If ##3|n^2##, then ##3|n##.
     
  2. jcsd
  3. Feb 15, 2015 #2

    Nathanael

    User Avatar
    Homework Helper

    Right. If n=3m then n2=9m2 which is always divisible by 3.
     
  4. Feb 16, 2015 #3
    This is not right. Your prove that the conjecture 3|n Λ not 3|n^2 produces a contradiction, but that proves that 3|n ⇒ 3|n^2.
    You need to prove that 3|n^2 ⇒ 3|n
     
  5. Feb 16, 2015 #4

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    What you have proved is that "if n is divisible by 3 then [itex]n^2[/itex] is divisible by 3. That's the "wrong way around"!
    To give a proof by contradiction, you need to start "suppose n is NOT divisible by 3", not that is divisible by 3.

    Do you see that if n is not divisible by 3, it must be of the form "3k+ 1" or "3k+ 2" for some integer k?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: ##n^2## is divided by 3, then n is also divided by 3.
  1. Prove n^3 <= 2^n (Replies: 9)

Loading...