## 314 – On √n

Let’s prove that if $n\in\mathbb N$, then either $\sqrt n$ is an integer, or else it is irrational. (Cf. Abbott, Understanding analysis, Exercise 1.2.1.) There are many proofs of this fact. I present three.

1.

The standard proof of this fact uses the prime factorization of $n$: There is a unique way of writing $n$ as $\prod_{i=1}^k p_i^{\alpha_i}$, where the $p_i$ are distinct primes numbers, and the $\alpha_i$ are positive integers (the number $n=1$ corresponds to the empty product, but since $1$ is a square, we may as well assume in what follows that $n>1$).

We show that if $\sqrt{n}$ is rational, then in fact each $\alpha_i$ is even, so $\sqrt n$ is actually an integer. Write $\sqrt n=a/b$ where $a,b$ are integers that we may assume relatively prime. This gives us that $b^2n=a$.

Consider any of the primes $p=p_i$ in the factorization of $n$. Let $p^\beta$ and $p^\gamma$ be the largest powers of $p$ that divide $a$ and $b$, respectively, say $a=p^\beta c$ and $b=p^\gamma d$ where $p$ does not divide either of $c$ and $d$. Similarly, write $n=p^{\alpha}m$, where $p$ does not divide $m$ ($\alpha$ is what we called $\alpha_i$ above). We have

$p^{2\gamma} p^{\alpha}d^2m=p^{2\beta}c^2.$

The point is that since $p$ is prime, it does not divide $c^2$ or $d^2m$: If $q$ is a prime and $q$ divides a  product $hj$ (where $h,j$ are integers), then $q$ divides $h$ or it divides $j$.

This means that either $\alpha$ is even (as we wanted to show), so that $2\gamma+\alpha=2\beta$, or else (upon dividing both sides of the displayed equation by the smaller of $p^{2\gamma+\alpha}$ and $p^{2\beta}$), $p$ divides one of the two sides of the resulting equation, but not the other, a contradiction.

2.

The above is the standard proof, but there are other arguments that do not rely on prime factorizations. One I particularly like uses Bézout theorem: If $c$ is the greatest common divisor of the positive integers $a$ and $b$, then there are integers $x,y$ such that $ax+by=c$.

Suppose $\sqrt n=a/b$. We may assume that $a,b$ are relatively prime, and therefore there are integers $x,y$ such that $ax+by=1$. The key observation is that $\sqrt n=n/\sqrt n=nb/a$. This, coupled with elementary algebra, verifies that

$\displaystyle \sqrt n= \frac ab=\frac{nb}a=\frac {ay+nbx}{by+ax},$

but the latter is an integer, and we are done.

3.

Another nice way of arguing, again by contradiction, is as follows: Suppose that $\sqrt n$ is not an integer, but it is rational. There is a unique integer $m$ with $m<\sqrt n, so $0<\sqrt n -m<1$. Let $a$ be the least positive integer such that $(\sqrt n-m)a$ is an integer, call it $b$. Note that $0, which gives us a contradiction if $({\sqrt n}-m)b$ is again an integer. But this can be verified by a direct computation:

$(\sqrt n-m)b=(\sqrt n-m)^2a=(n+m^2)a-2m\sqrt n a$ $=(n-m^2)a-2m(\sqrt n-m)a$.

4.

As a closing remark, the three arguments above generalize to show that $\root k\of n$ is either an integer or irrational, for all positive integers $n,k$. Similarly, if $\displaystyle\root k\of {\frac ab}$ is rational for some positive integers $a,b$, then both $a,b$ are $k$th powers. (It is a useful exercise to see precisely how these generalizations go.)