Proof that $\sqrt{2}$ is irrational I am having hard time flowing a proof from Introduction to the theory of computation (3rd ed.) by Michael Sipser.   Please points out what I am missing.  My questions is "Now, at least one of $m$ and $n$ must be add odd number." Why can we make such a statement already? 

PROOF First, we assume for the purpose of later obtaining a contradiction
that $\sqrt{2}$ is rational.

Thus $\sqrt{2} = \dfrac{m}{n}$,

where $m$ and $n$ are integers. If both m and n are divisible by the same integer greater than $1$, divide both by the largest such integer. Doing so doesn’t change the value of the fraction. Now, at least one of m and n must be an odd number. We multiply both sides of the equation by n and obtain

$n\cdot \sqrt{2} = m$.

We square both sides and obtain 

$2\cdot n^2 = m^2$.

Because m2 is 2 times the integer n2, we know that m2 is even. Therefore, m, too, is even, as the square of an odd number always is odd. So we can write m = 2k for some integer k. Then, substituting 2k for m, we get

$2n^2 = (2k)^2 = 4k^2$. 

Dividing both sides by $2$, we obtain 

$n^2 = 2k^2$.

But this result shows that $n^2$ is even and hence that $n$ is even. Thus we have established that both $m$ and $n$ are even. But we had earlier reduced $m$ and $n$ so that they were not both even—a contradiction.
If $m$ and $n$ are both even you can still divide both by 2. Absurd we already divided them by all integers possible greater than 1. Thus, at least 1 of them is odd.
There are numerous proofs for this fact, but my favorite is:

Assume $\sqrt{2} = m/n$.

Then $2 n^2 = m^2$.

The left side has an odd number of prime factors and the right side has an even number of prime factors.  By the fundamental theorem of arithmetic (unique prime factorization) we reach a contradiction.

$\square$