# Integers, rationals and divisibility

1. May 13, 2012

### Kartik.

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. May 13, 2012

### Infinitum

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.

3. May 13, 2012

### HallsofIvy

Staff Emeritus
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 $n^2+1= 9k+ 1= 3(3k)+ 1$. If n= 3k+1, then $n^2+ 1= (3k+1)^2+ 1= 9k^2+ 6k+ 1+ 1= 3(3k^2+ 2k)+ 2$. If n= 3k+2, then $n^2+ 2= (3k+2)^2+ 1= 9k^2+ 12k+ 5=9k^2+ 12k+ 3+ 2= 3(3k^2+ 4k+ 1)+ 2$.