For each proposition, write a formal proof.

$(1)$ For integers $m$ and $n$ to have the same parity, it is sufficient for

$m^2+n^2$ to be a multiple of $4.$