Proof

Let $m$ be an integer.
According to the Euclidean lemma about the quotient and remainder there are unique integers $q$ and $r$ such that $m=2q + r$ with $0\le r < 2.$
Case $r=0$: Then $m=2q$, and $m$ is even by definition.
Case $r=1$: Then $m=2q+1$, and $m$ is odd by definition.
Since $r$ must by either $0$ or $1$ because of $0\le r < 2,$ it follows that every integer is either even or odd.
∎

Thank you to the contributors under CC BY-SA 4.0!