Why is the negation of the statement $\exists x P(x)$ given by $\forall x (\neg P(x))$ and not $\not \exists x P(x)$?

The two statements are equivalent, the reason why we write it that way it is because it is easier to deal/prove it. It is irrelevant which way it is easier to say it, the important thing is being able to use.

Just consider the statement $\exists x \in \mathbb Z, x^2+(x+1)^2 \mbox{ is even}$. This is not true, now try to show that this is false.

Try to prove separately each of the following two statements:

• $\not\exists x \in \mathbb Z, x^2+(x+1)^2 \mbox{ is even}$
• $\forall x \in \mathbb Z, x^2+(x+1)^2 \mbox{ is odd}$

It is easier to deal with the second one.

Which form to consider simpler is basically a matter of taste and convention.

There are some accounts of predicate logic that consider $\exists$ the only primitive quantifier and treat $\forall x\,\varphi$ as an abbreviation for $\neg\exists x\neg\varphi$.

My impression is that this is something of a minority option these days, but it is not wrong as such.