Why is n squared plus one never divisible by three?

Answer 1

This is very easy to prove using modulo arithmetic. Basically, what you do is to look at the remainder when a number (n) is divided by 3. Let k(mod 3) represent the remainder when a number is divided by 3.

Since the divisor is 3, there are only 3 possible values for k, that is:

n = 0(mod 3), 1(mod3) or 2(mod3).

Suppose n = 0(mod 3)

then n2 + 1 = 0 + 1(mod 3) = 1(mod 3)

so that n2 + 1 leaves a remainder of 1 when divided by 3 and so is not divisible by 3.

Suppose n = 1(mod 3)

then n2 + 1 = 12 + 1(mod 3) = 2(mod 3)

so that n2 + 1 leaves a remainder of 2 when divided by 3 and so is not divisible by 3.

Suppose n = 2(mod 3)

then n2 + 1 = 22 + 1(mod 3) = 5(mod 3) = 2(mod 3)

so that n2 + 1 leaves a remainder of 2 when divided by 3 and so is not divisible by 3.

Thus, for all possible values of n, division by 3 leaves a positive remainder. And so the result follows.