Here is the forward direction: if then . If then , so will then be both odd since is odd. If then by a similar argument , so will then both be odd. Therefore, it is safe to assume that . Since it means is a normal subgroup and we can form the factor group . Notice that (in the case we are assuming) . Therefore, the order of and in is . Let . Then . Thus, , hence both are even. Thus, always have the same parity.
Now for the converse direction. We will work in cases, first we will assume that are both odd and then that both are even. If both are odd then order of in cannot be (by above argument) so , likewise . If both are even then since is odd and so (since there are only two cosets the ones different from must be equal). Regardless, in whatever case and so , so .