How can we prove that Gaussian integers are algebraic integers? I heard in a lecture that every gaussian integer is in fact a root of a monic 2nd degree polynomial, it has been a day now and I can't figure this out.

There are a few things to say here:
It's a general fact that the sum of two algebraic numbers/integers is also one and clearly, $bi = b\sqrt{-1}$ and $a$ are algebraic integers so $a+bi$ is one too.
But in this example, we can be more explicit: $a+bi$ is the root of the polynomial $x^2 - 2ax + (a^2+b^2) = 0$.
