C = n^2 + n + 1 = (n^2 + 2n + 1) - n = (n + 1)^2 - n

 khi n là số chẵn, thì (n+1) cũng là số lẻ.
=> (n+1)^2 là số lẻ. 
=> khi n là số chẵn, C sẽ chia hết cho 2.

 khi n là số lẻ, (n+1) là số chẵn và (n+1)^2 là số chẵn.
=> khi n là số lẻ, C sẽ không chia hết cho 2.
=> C sẽ chia hết cho 2 khi và chỉ khi n là số chẵn.