Ta có: n² + n + 1 = (n – 1)(n + 2) + 3.

Giả sử n² + n + 1 chia hết cho 9

Khi đó (n – 1)(n + 2) + 3 chia hết cho 9 (1)

⇒ (n – 1)(n + 2) + 3 chia hết cho 3

Mà n + 2 – (n – 1) = 3 chia hết cho 3

n + 2 và n – 1 đều chia hết cho 3. Do đó: (n – 1)(n + 2) chia hết cho 9. (2)

Từ (1) và (2), suy ra 3 chia hết cho 9 (vô lý)

Vậy điều giả sử là sai.

Vậy với mọi số nguyên dương n thì n² + n + 1 không chia hết cho 9.