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!

Integers, rationals and divisibility

  1. May 13, 2012 #1
    1.To prove - For any natural number n, the number N is not divisible by 3

    2. N = n2+1



    3. Dividing naturals into three classes according to remainder outcomes during division by 3 ie. 0,1,2 ; for any whole number k ---> 3k, 3k+1, 3k+2
    And then substitute the values respectively to derive a 'false' inference from the equation. I want to know whether this is the only standard method of proving such divisibility equations true or false ; or is there any other way out?
     
  2. jcsd
  3. May 13, 2012 #2
    There is no standard way for divisibility tests. The only idea is to find a part of the expression that cannot be divided by the given number. The way you do it might differ for each problem. Of course, your method works out the best to find out the proof to what you need. Say if you had, 3x2+2, and test whether its divisible by 3, the solution would be obviously to break it up into x2 + 2/3, leading to the conclusion it is not divisible by 3.
     
  4. May 13, 2012 #3

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    You show that N is "divisible by 3" by showing that it is of the form 3m for some integer k, NOT "3m+1" or "3m+2".

    Every integer, and in particular n, is of the form 3k, 3k+ 1, or 3k+ 2. If n= 3k then [itex]n^2+1= 9k+ 1= 3(3k)+ 1[/itex]. If n= 3k+1, then [itex]n^2+ 1= (3k+1)^2+ 1= 9k^2+ 6k+ 1+ 1= 3(3k^2+ 2k)+ 2[/itex]. If n= 3k+2, then [itex]n^2+ 2= (3k+2)^2+ 1= 9k^2+ 12k+ 5=9k^2+ 12k+ 3+ 2= 3(3k^2+ 4k+ 1)+ 2[/itex].
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook