Help understanding this proof: $\sqrt2$ is irrational

Question

Theorem: $\sqrt{2}$ is irrational

Proof (By contradiction): Assume, on the contrary that $\sqrt{2}$ is rational Then there are natural numbers $p$ and $q$, with no common factors, such that $\sqrt{2} = \frac{p}{q}$

Squaring: $2 = \frac{p^2}{q^2}$
Rearranging: $2q^2 = p^2$

So $p^2$ is even ( it is equal to twice something $ \to 2 \times q^2$ ), Hence $p$ is even.

(Why?): Because the square of an even number is even, and the square of an odd number is odd. So the only way to get the square of a number to be even is if the number is even

So $p$ is $2r$ for some $r$
Substituting for $p$: $ 2q^2 = 2r^2 = 4r^2 $
Cancelling $2$: $ q^2 = 2r^2$

So $q^2$ is even ( it is equal to twice something $\to 2 \times r^2$ ), Hence $q$ is even (Reason: See Why?)

Deduction: $p$ is even, $q$ is even...

Conclusion: if both $p$ and $q$ are even, then they have $2$ as a common factor; but by the original assumption: ...Then there are natural numbers p and q, with no common factors, this shows that $p$ and $q$ cannot have a common factor. Since this conclusion does not agree with the assumption, this means that $\sqrt{2}$ is irrational. QED

I have a couple questions about the proof:

• If I have an even number $N$, then isn't it possible to factor this number until it is odd? Then wouldn't this mean that although $p$ and $q$ are even, they can be factored until no more factors are possible?

• Is it correct to assume that any rational number can be expressed as the quotient of $2$ other numbers who have no common factors?

Answer 1

Yes, you could instead (uniquely!) write $\,p = 2^j a\,$ and $\,q = 2^k b\,$ for $\,a,b\,$ odd and then deduce a contradiction by comparing the number of factors of $2,\,$ viz. $\,p^2\,$ has an even number of $2$'s but $\,2q^2\,$ has an odd number of $2$'s, a contradiction. This method uses only the very easily proved existence and uniqueness of $2$-factorizations, i.e. representations of the form $\,2^j n,\,$ with $\,n\,$ odd (versus the much more powerful, and much more difficult to prove Fundamental Theorem of Arithmetic = existence and uniqueness of arbitrary prime factorizations).

As for your second question, yes, every fraction $\,A/B\,$ can be written with coprime numerator and denominator $\,a/b\,$ simply by cancelling their gcd $\,c,\,$ i.e. $\,A/B = ca/cb = a/b.\,$ By the maximality ("greatest") property of the gcd it follows that $\,d =\gcd(a,b) = 1,\,$ else $\,cd\,$ would be a common divisor of $\,A,B\,$ larger than the greatest common divisor $\,c=\gcd(A,B),\,$ contradiction. However, as above, it suffices to cancel only common factors of $\,2,\,$ so no knowledge of gcds is required.

Answer 2

You are correct that you can always factor a number $N$ to take away the even part; that is, we can always write

$$ N = 2^p (2k-1) $$

for some $p, k$. However, the contradiction in this case arises from your second question: Yes, it is always possible to write any rational number as a quotient of two integers with no common factors. In particular, if we write $N = p/q$ then we can arrange it so that at most one of $p, q$ are even.

However, from the argument above we see that if $\sqrt{2} = p/q$, then it would have to follow that no matter how we wrote this, that both $p$ and $q$ are even, which contradicts the above observation.

There is another way of thinking about this:

We can always write (by the fundamental theorem of arithmetic) any number as

$$ N = 2^{n_2}3^{n_3}5^{n_5}7^{n_7} \cdots $$

and so if apply this to $p, q$ as obtained previously we would see that they are both even. We could then (by cancelling a power of 2 from each of them) see that there are strictly smaller integers $p_1, q_1$ (since they have fewer factors of 2) such that

$$ \sqrt{2} = \frac{p_1}{q_1} $$

But the same argument shows that these two numbers must be also even. Hence we can find yet strictly smaller integers $p_2, q_2$ such that...

we then obtain a strictly decreasing sequence of positive integers $p_1 > p_2 > \ldots$. However, by the well-ordering principle, any such sequence must have a smallest element, which is a contradiction.