“⇐” every integer is either even or odd
For the ⇐ direction, use the Quotient-Remainder Theorem.