# Well-ordering proof

**Number Theory**Level 2

What is wrong with this "proof" of the following statement?

For every positive integer \( n,\) the number \( n^2+n+1\) is even.

**Proof:**

Let \( S\) be the subset of positive integers \(n\) for which \(n^2+n+1\) is odd. Assume \( S\) is nonempty.

Let \( m\) be its smallest element.

Then \( m-1 \notin S,\) so \( (m-1)^2+(m-1)+1\) is even.

But \[ (m-1)^2+(m-1)+1 = m^2-m+1 = (m^2+m+1)-2m, \] so \( m^2+m+1\) equals \( ((m-1)^2+(m-1)+1)+2m,\) which is a sum of two even numbers, which is even.

So \( m \notin S;\) this is a contradiction. Therefore \( S\) is empty, and the result follows.