$\sqrt{17}$ is irrational: the Well-ordering Principle

Prove that $\sqrt{17}$ is irrational by using the Well-ordering property of the natural numbers.

I've been trying to figure out how to go about doing this but I haven't been able to.

Solution 1:

In general, suppose $n$ is an integer that is not a perfect square. I will show that $\sqrt{n}$ is irrational. Note: This proof is not original, although I did come up with it independently.

Let $m = \lfloor \sqrt{n} \rfloor$. Since $n$ is not a perfect square (this is where we use that assumption), $m < \sqrt{n}$.

Suppose $\sqrt{n}$ is rational, so $\sqrt{n} = \frac{a}{b}$ for some positive integers $a$ and $b$.

At this point, we can go in two different directions. We can either assume that $b$ is the smallest positive integer such that $b\sqrt{n}$ is an integer, and deduce a contradiction by finding a smaller positive integer $d$ such that $d\sqrt{n}$ is an integer, or we can show that there is a smaller positive integer $d$ such that $d\sqrt{n}$ is an integer and thus create a contradiction using infinite descent.

I will use the first method.

Suppose $b$ is the smallest positive integer such that $b\sqrt{n}$ is an integer. Let $a = b\sqrt{n}$ As above, let $m = \lfloor \sqrt{n} \rfloor$, so that $m < \sqrt{n} < m+1$.

Then (watch closely - the fingers never leave the hands)

$\begin{align} \frac{a}{b} &=\sqrt{n}\\ &=\sqrt{n}\frac{\sqrt{n}-m}{\sqrt{n}-m}\\ &=\frac{n-m\sqrt{n}}{\sqrt{n}-m}\\ &=\frac{n-m(a/b)}{a/b-m}\\ &=\frac{nb-ma}{a-mb}\\ \end{align} $

so that $(a-mb)\sqrt{n} = nb-ma$ is also an integer.

Since $m < \sqrt{n} < m+1$, $m < a/b < m+1$ or $mb < a < mb+b$, or $0 < a-mb < b$.

Therefore $a-mb$ is a positive integer smaller than $b$ and $(a-mb)\sqrt{n}$ is an integer. This contradicts the definition of $b$ as the smallest such integer.

You can put $n = 17$ or $n=2$ (which is where I first saw this proof and generalized it to what you see here), or any non-perfect square and show that $\sqrt{n}$ is irrational this way.

Solution 2:

Let $b$ be the smallest positive integer whose product with $\sqrt{17}$ is an integer (if $\sqrt{17}$ is rational then, by well-ordering, such a $b$ exists). Then $c=(\sqrt{17}-4)b$ is a smaller positive integer whose product with $\sqrt{17}$ is an integer, contradiction, hence $\sqrt{17}$ is irrational.

Solution 3:

HINT:

Suppose by contradiction the root of $17$ was rational, and without loss of generality positive. Take the least $p$ such that for some $q$ the rational $\frac pq$ is that root. Now derive a contradiction by showing that $p$ isn't minimal with respect to that property.

Solution 4:

Suppose there exist integers $a_0,b_0$, with $a_0,b_0\gt 0$, such that $\left(\frac{a_0}{b_0}\right)^2=17$.

Then $a_0^2=17b_0^2$. Since the prine $17$ divides $17b_0^2$, it divides $a_0^2$, and therefore $17$ divides $a_0$. Let $a_0=17b_1$. Then $17^2b_1^2=17b_0^2$, and therefore $b_0^2=17b_1^2$. Let $a_1=b_0$.

We conclude that $a_1^2=17b_1^2$. It is easy to see that $b_1\lt b_0$.

Similarly, we can produce positive integers $a_2,b_2$ such that $b_2\lt b_1$ and $a_2^2=17b_2^2$, with $b_2\lt b_1$.

Continuing in this way, we can produce two infinite sequences $a_n,b_n$ such that $a_n^2=17b_n^2$ and $b_0\gt b_1\gt b_2\gt \cdots$.

In particular, we can produce an infinte descending sequence $b_0,b_1,b_2,\dots$ of positive integers.

This contradicts the Well-Ordering Principle.