Proof that $\sqrt{2}$ is irrational

Question

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.

Answer 1

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.

Answer 2

We are assuming that $\sqrt 2 = m/n$ with $m$ and $n$ relatively primes and thus at least one must be odd, whitout any factor in common, but we reach a contradiction.

Answer 3

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$

Answer 4

If the square root of $2$ is rational, then by definition it can be written as a ratio of two whole numbers. But then, as long as both numbers are even, you can divide both sides by $2$, and get two new numbers that have the same ratio.

Now, these two new numbers may still be even of course, but that means that you just divide them both by two again. And you cannot indefinitely keep dividing both sides, because the numbers are finite, and they keep getting smaller and smaller, so there must be some point where it is no longer true that both sides are even.

Therefore, if the square of of two can be expressed as a ratio at all, then it is also possible to express it as a ratio of two whole numbers where not both sides are even.

Answer 5

If both m and n are divisible by the same integer greater than 1, divide both by the largest such integer.

If the they are both even then you didn't divide by the bigger integer. Because you can still divide both by $2$.

I'd have worded it differently. I'd have said "If they have any factors in common divide both by that factor and keep repeating until they have no factors in common".

It means the same thing but it just makes it more clear that in the end, they will have no factors in common. And if the have no factors in common, they can't have $2$ in common. And the can't both be even.