$\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.
 A: 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.
A: 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. 
A: 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. 
A: 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.
