Prove that $\sqrt{n}$ is irrational unless $n = m^2$ for some natural number $m$.

elementary-number-theory

From Spivak's "Calculus":

A fundamental theorem about integers, which we will not prove here, states that this factorization [factorization into a product of primes] is unique, except for the order of the factors. Thus, for example, 28 can never be written as a product of primes one of which is 3, nor can it be written in a way that involves 2 only once (now you should appreciate why 1 is not allowed as a prime).

(b) Using this fact, prove that $\sqrt{n}$ is irrational unless $n = m^2$ for some natural number $m$.

The solution is given as

If $\sqrt{n} = a/b$, then $nb^2 = a^2$, so the factorization into primes of $nb^2$ and of $a^2$ must be the same. Now every prime appears an even number of times in the factorization of $a^2$, and of $b^2$, so the same must be true of the factorization of $n$. This implies that n is square.

Does this solution really prove the original statement? The statement was $\sqrt{n}$ is irrational $\rightarrow \forall m \in \mathbb{N} (n \neq m^2)$ or, equivalently, $\exists m \in \mathbb{N} (n = m^2) \rightarrow \sqrt{n}$ is rational. It seems that they proved $\sqrt{n}$ is rational $\rightarrow \exists m \in \mathbb{N} (m^2 = n) $

Best Answer

You are correct. That is what they proved. It is also equivalent to what (b) says in the problem statement.

It may be useful to see that (as I alluded to in my comment) we can interpret "$A$ unless $B$" as "$A$ is generally true, except when $B$ is true." Therefore, if $A$ isn't true, that can only mean that $B$ is true.

In the present problem, we have $A$ = "$\sqrt{n}$ is irrational" and $B$ = "$n$ is a perfect square." By our above reasoning, we can interpret this as "If $\sqrt{n}$ isn't irrational (i.e., it is rational), then $n$ must be a perfect square." And that is indeed what the given solution that you quoted shows.


Incidentally, strictly speaking, "$A$ unless $B$" does not necessarily imply "If $B$, then not $A$." It is possible that $B$ is true, and yet $A$ remains true. It only says that if $A$ is false, than $B$ is true. Granted, it often does mean a strict opposition between $A$ and $B$ in ordinary discourse, and I'm not sure I'd want to prepare a legal argument predicated on this ambiguity, but logically, the strict opposition doesn't follow.

Related Question