Let k $\in Z$, such that k $\ge$ -1. Then $k^2 + 1$ is not divisible by 3. I had this on the exam a few months ago and I am doing it again just for review. I want to check if I did it right this time. Any comment would be appreciated! 
Proposition: Let k $\in Z$, such that k $\ge$ -1. Then $k^2 + 1$ is not divisible by 3. 
(Hint : $(k+1)^2$ + 1 + (3-6k) = $(k-2)^2$ + 1 for all k $\in Z$)
Proof: Let P(k) be the statement that "$k^2 + 1$ is not divisible by 3"
Base case(k= -1, 0 and 1) holds.
Induction: Let k $\in Z$ and k$\ge$1, and suppose p(j) holds for all j $\in Z$ such that -1 $\le j \le k$
we need to prove P(k+1) holds.
By hint, we have $(k+1)^2 + 1= (k-2)^2 +1 - (3-6k)$
By Induction hypothesis, $(k-2)^2 + 1$ is not divisible by 3 and since (3-6k) is divisible by 3, $(k+1)^2 + 1$ is not divisible by 3.
 A: I can provide to proofs,one can ignore the second if his is not familiar with quadratic residue
Method 1
For any integer $k$, the remainder of $k$ when divided by $3$ is $-1,0,1$. So the remainder of $k^2$ can only be ${(-1})^2,0,1$  , namely $0,1$.Consequently,the remainder of $k^2+1$ is $1 \,\text{or} \,,2$ and can never be $0$.
Merhod 2
$-1$ is not a  quadratic residue mod $3$ since $3\equiv 3\pmod 4 $.So the equation $x^2\equiv -1\pmod 3$ has no solution
A: Your proof is fine. You could clarify the last point by writing 
$$(k-2)^2 + 1 = ((k+1)^2 + 1) + 3(1 - 2k)$$ and noting that if $(k+1)^2 + 1$ would be divisible by $3$, so would $(k-2)^2 + 1$ be, as a difference of two multiples of $3$, so it is not a multiple of $3$ by the induction hypothesis.
Another proof uses congruences instead of induction: every $k$ equals $0$,$1$ or $-1$ modulo 3. So $k^2$ equals $0$ or $1$ modulo 3, and $k^1 + 1$ equals $1$ or $2$ modulo 3, so can never be $0$ mod 3, i.e. $k^2 + 1$ is never divisible by $3$.
A: Your way is fine.
Another way: $(3m+r)^2 + 1 = 3(m^2 + 2mr) + (r^2+1)$ where $r < 3m+r$, so done by strong induction if we prove the cases $k=-1, 0, 1, 2$ separately.
