How to prove: if $a,b \in \mathbb N$, then $a^{1/b}$ is an integer or an irrational number?

Question

It is well known that $\sqrt{2}$ is irrational, and by modifying the proof (replacing even with divisible by $3$), one can prove that $\sqrt{3}$ is irrational, as well. On the other hand, clearly $\sqrt{n^2} = n$ for any positive integer $n$. It seems that any positive integer has a square root that is either an integer or irrational number.

$1.$ How do we prove that if $a \in \mathbb N$, then $\sqrt a$ is an integer or an irrational number $?$

I also notice that I can modify the proof that $\sqrt{2}$ is irrational to prove that $\sqrt[3]{2}, \sqrt[4]{2}, ...$ are all irrational. This suggests we can extend the previous result to other radicals.

$2.$ Can we extend $1?$ That is, can we show that for any $a, b \in \mathbb{N}$, $a^{1/b}$ is either an integer or irrational?

Answer 1

These (standard) results are discussed in detail in

http://alpha.math.uga.edu/~pete/4400irrationals.pdf

This is the second handout for a first course in number theory at the advanced undergraduate level. Three different proofs are discussed:

1. A generalization of the proof of irrationality of $\sqrt{2}$, using the decomposition of any positive integer into a perfect $k$th power times a $k$th power-free integer, followed by Euclid's Lemma. (For some reason, I don't give all the details of this proof. Maybe I should...)

2. A proof using the functions $\operatorname{ord}_p$, very much along the lines of the one Carl Mummert mentions in his answer.

3. A proof by establishing that the ring of integers is integrally closed. This is done directly from unique factorization, but afterwards I mention that it is a special case of the Rational Roots Theorem.

Let me also remark that every proof I have ever seen of this fact uses the Fundamental Theorem of Arithmetic (existence and uniqueness of prime factorizations) in some form. [Edit: I have now seen Robin Chapman's answer to the question, so this is no longer quite true.] However, if you want to prove any particular case of the result, you can use a brute force case-by-case analysis that avoids FTA.

Answer 2

Theorem: If $a$ and $b$ are positive integers, then $a^{1/b}$ is either irrational or an integer.

If $a^{1/b}=x/y$ where $y$ does not divide $x$, then $a=(a^{1/b})^b=x^b/y^b$ is not an integer (since $y^b$ does not divide $x^b$), giving a contradiction.

I subsequently found a variant of this proof on Wikipedia, under Proof by unique factorization.

The bracketed claim is proved below.

Lemma: If $y$ does not divide $x$, then $y^b$ does not divide $x^b$.

Unique prime factorisation implies that there exists a prime $p$ and positive integer $t$ such that $p^t$ divides $y$ while $p^t$ does not divide $x$. Therefore $p^{bt}$ divides $y^b$ while $p^{bt}$ does not divide $x^b$ (since otherwise $p^t$ would divide $x$). Hence $y^b$ does not divide $x^b$.

[OOC: This answer has been through several revisions (some of the comments below might not relate to this version)]

Answer 3

The general theorem is that a natural number $a$ has a rational square root if and only if the multiplicity of every prime factor of $a$ is even. For example $2^43^611^2$ has a rational square root but $5^411^3$ does not.

Moreover, if a natural number has a rational square root, that square root is always obtained by halving the multiplicity of each prime factor, and so the square root is also a natural number.

The same principle works for $n$th roots, $n > 1$.

Answer 4

Definition: An algebraic integer is a solution of a monic polynomial with integer coefficients. This set is closed by sums and products and such.

Theorem: If an algebraic integer is rational, then it is an integer.

Proof: Apply rational roots theorem.

---

This theorem proves that $\sqrt[b]{a}$ is irrational unless $a$ is a $b$-th power.

Answer 5

As muad points out, you can also obtain this as an easy consequence of the Rational Root Theorem: if $a_nx^n+\cdots+a_0$ is a polynomial with integer coefficients, and $\frac{p}{q}$ is a rational root with $\gcd(p,q)=1$, then $p|a_0$ and $q|a_n$ (plug in, clear denominators, factor out).

So if you look at the polynomial $x^b-a$, with $b$ and $a$ positive integers, then a rational root must be of the form $\frac{p}{q}$, with $\gcd(p,q)=1$, and $q|1$. Thus, it must be an integer. So if it has a rational root, then the root is integral.

Answer 6

Here is a simple conceptual proof of irrationality of certain square roots - from first principles. Call a natural $\rm\,d > 0\,$ a denominator of $\rm\:r\in\Bbb Q\:$ if $\rm\:r = c/d\:$ for some $\rm\:c\in\mathbb Z,\:$ i.e. $ $ if $\rm\ dr\in \mathbb Z.$

Theorem $\ \ \rm r = \sqrt{a}\ $ is integral if rational,$\:$ for all $\:\rm a\in\mathbb{N}$

Proof $\ \ $ Put $\ \ \displaystyle\rm r = \frac{c}d ,\;$ with $\rm\; 0 < d\:$ least. $\ \displaystyle\rm\sqrt{a}\; = \frac{a}{\sqrt{a}} \ \Rightarrow\ \frac{c}{\color{#c00}d} = \frac{a\:d}{\color{#c00}c} \, \Rightarrow\ \color{#c00}d\:$ divides $\rm\: \color{#c00}c, \ $ by

Lemma $\;$ The least denominator of a rational $\:\rm r\:$ divides every denominator of $\rm\:r\:.$

Proof $\rm\ \, n > m\ $ denominators $\, \Rightarrow\, $ so is $\rm\ n\!-\!m\ $ by $\;\rm nr, mr\in \mathbb Z \, \Rightarrow\, (n\!-\!m)r\in \mathbb Z.\,$ Now apply

Lemma' $\ \ $ Let $\:\rm S\ne\{\,\} \,$ be a set of integers $>0\,$ closed under subtraction $> 0,\,$ i.e. for all $\rm\,n,m\in S, \,$ $\rm\ n > m\ \Rightarrow\ n-m\, \in\, S.\,$ All elements of $\rm\,S\,$ are multiples of the least $\rm\:\ell = \min\, S.$

Proof ${\bf\ 1}\,\ $ If not there is a least nonmultiple $\rm\,n\in S,\,$ contra $\rm\,n-\ell \in S\,$ is a nonmultiple of $\rm\,\ell.$

Proof ${\bf\ 2}\,\rm\,\ \ S\,$ closed under subtraction $\rm\,\Rightarrow\,S\,$ closed under remainder (mod), when it is $\ne 0,$ since mod is just repeated subtraction, i.e. $\rm\, a\ mod\ b\, =\, a - k b\, =\, a-b-b-\cdots -b.\,$ Hence $\rm\,n\in S\,$ $\Rightarrow$ $\rm\, (n\ mod\ \ell) = 0,\,$ else it's in $S$ and smaller than $\rm\,\ell,\,$ contra mimimality of $\rm\,\ell.$

Remark $\ $ In a nutshell, two applications of induction yield the following inferences

$ \rm\begin{eqnarray} S\ closed\ under\ {\bf subtraction}\!\! &\Rightarrow&\rm S\ closed\ under\ {\bf mod} = remainder = repeated\ subtraction \\ &\:\Rightarrow\:&\rm S\ closed\ under\ {\bf gcd} = repeated\ mod\ (Euclid's\ algorithm) \end{eqnarray}$

Interpreted constructively, this yields the extended Euclidean algorithm for the gcd.

The above Lemma is quite fundamental to factorization. I frequently refer to it by the suggestive moniker unique fractionization in order to highlight its equivalence to uniqueness of factorizations into irreducibles (one easily verifies that it is equivalent to Euclid's Lemma, which implies that irreducibles are prime). The structure implicit in the Lemma is a denominator or order ideal. Exploiting this structure, the proof easily generalizes to show that rational roots of monic integer coefficient polynomials must be integers, i.e. $\:\mathbb Z\:$ is integrally-closed (cf. the monic case of the Rational Root Test). In fact, this generalizes much further, employing Dedekind's key notion of a conductor ideal, to a one-line proof that PIDs are integrally closed. For much more on this see my post here and especially the posts linked there, and their links $\ldots$ (it is a beautiful web of ideas - mostly all due to Dedekind - as Noether often rightly remarked).

Answer 7

To answer Pete's comment as to how to prove integral closure of $\mathbb{Z}$ without using the UFD property.

Let $a/b$ be a rational ($a$, $b\in\mathbb{Z}$) which is integral over $\mathbb{Z}$. Let $R=\mathbb{Z}[a/b]$. Then $R$ is a finitely-generated $\mathbb{Z}$-module. It follows that $b^n R\subseteq\mathbb{Z}$ for some $n$. We reduce to proving the lemma that if $R$ is a ring with $\mathbb{Z}\subseteq R\subseteq N^{-1}\mathbb{Z}$ for some nonzero integer $N$ then $R=\mathbb{Z}$.

There are various ways of proving this. For instance if $R\ne\mathbb{Z}$ there is an element of $R$ strictly between two consecutive integers (this is the division algorithm) and so an element $x$ of $R$ strictly between $0$ and $1$. If $y$ is the least such number then considering $y^2$ gives a contradiction. Alternatively, $M=xN$ is an integer and $R\subseteq M^{-1}\mathbb{Z}$ so we can always replace $N$ by a smaller integer etc.

Answer 8

Below is a simple proof of irrationality of square-roots that I discovered as a teenager (inspired by a proof of Dedekind). It employs the Bezout identity for the gcd, i.e. $\rm\,\gcd(a,b)\,$ is an integral linear combination of the integers $\rm\,a,b,\,$ i.e. $\rm\,\gcd(a,b)\, =\, a d - b c\,$ for some integers $\,\rm c,d$.

Theorem $\ \ \ \rm r = \sqrt{n}\;\;$ is integral if rational, $\:$ for $\:\rm n\in\mathbb{N}$

Proof $\ \ $ Note that $\rm\ r = a/b,\ \ \gcd(a,b) = 1\ \Rightarrow\ ad\!-\!bc \,=\, \color{#C00}{\bf 1}\;$ for some $\:\rm c,d \in \mathbb{Z}\ $ by Bezout.

$\rm\color{#C00}{That\,}$ and $\rm\: r^2\! = \color{#0a0}{ n}\:\Rightarrow\ 0 \,=\, (a\!-\!br)\, (c\!+\!dr) \, =\, ac\!-\!bd\color{#0a0}{ n} \:+\: \color{#c00}{\bf 1}\cdot r,\ $ thus $\ r \in \mathbb{Z}$

---

This easily generalizes to roots of quadratic polynomials that are monic (lead coef $= 1)$

Theorem $\,\ $ If $\rm\,\ r^2 =\, \color{#0A0}{m\ r + n}\ \,$ for $\rm\ m,n\in\mathbb Z\ $ then $\rm\ r\in \mathbb Q\ \Rightarrow\ r\in\mathbb Z$

Proof $\quad \rm r = a/b\in \mathbb Q,\ \ \gcd(a,b) = 1\ \Rightarrow\ ad\!-\!bc \,=\, \color{#C00}{\bf 1}\;$ for some $\:\rm c,d \in \mathbb{Z}\ $ by Bezout.

So $\rm\,\ 0\, =\, (a\!-\!br)\: (c\!+\!dr)\, =\, ac\! -\! bd(\color{#0A0}{m\:r\!+\!n})+\color{#C00}{\bf 1}\cdot r \, =\, ac\!-\!adm\!-\!bdn + r \ \Rightarrow\ r \in \mathbb{Z}$

---

This method works for higher degree monic polynomials too, giving a proof by induction on degree of the (monic) Rational Root Test. This implies that roots of $\,x^b-a\,$ are integral if rational, the sought generalization in the OP.

---

Alternatively, denominator descent can be achieved via Division with Remainder = mod (vs. gcd). We call $\rm\,d\,$ a denom(inator) of $\rm\,r\,$ if $\rm\,dr\in\Bbb Z\ $ (so $\rm\,dr = j\Rightarrow r = j/d\,$ is writable with denom $\rm d)$.

Theorem $\, \ $ If $\rm \ n\in\Bbb Z_{\phantom{\frac{i}.}} $ and $\rm \ \color{#c00}{r = \sqrt{n}}\in \Bbb Q\ $ then $\rm \ r\in \Bbb Z$
Proof $\, $ Deny, so $\,\rm 1 < r = {\small \frac{a}b}\,$ and $\,\rm \color{#b0f}{b\nmid a}$, by $\rm\, r\not\in\Bbb Z,\,$ wlog $\rm\,b = $ $\rm\color{#0af}{least}$ denom. Then as here we infer $\rm\,\color{#90f}{0\neq \bar a} := a\bmod b = \color{#0a0}{a-qb}<b\,$ is a $\rm\color{#0af}{smaller}$ denom for $\rm\,r\,$ by below, contradiction. $$\begin{align} \rm \color{#c00}r\,[\ a\: &\rm = b\color{#c00}r\:\!],\ \ \text{i.e. scale equation by $\,\rm\color{#c00}r$}\\[.1em] \rm -\ q\,[\:\!br &\rm =a\:\!]\\[.1em] \rm \Rightarrow\ (\color{#0a0}{a\!-\!qb})\:\! r &\rm = b\color{#c00}n\!-\!qa,\ \ \text{by adding prior $2$ equations} \end{align}$$

Remark $\ $ It is instructive to compare the various denominator descents employed.

The denom descent in the first proof is $\rm\,a,b\,$ denom $\rm\,\Rightarrow\, \gcd(a,b)\,$ [$\color{#c00}{\bf = 1}$] $ $ denom.

In the last proof the denom descent is: $\rm\,a,b\,$ denom $\rm\,\Rightarrow\, a\ {\rm mod}\ b\,=:\,\color{#90f}{\bar a}\:$ denom.

In this answer, the denom descent is: $\rm\, a\!>\!b\,$ denom $\rm\,\Rightarrow\ a\:\!-\:\!b\ $ denom.

These are all essentially special cases of proofs that the ideal $\,a\Bbb Z + b\Bbb Z = \Bbb Z\,$ using fast or slow descent based on the (Euclidean) Division algorithm (with remainder), i.e. specializations of a proof that ideals are principal in a Euclidean domain (compare posts on denominator ideals).

That the numerator $\rm\,a = br\,$ is also a denom of $\rm\,r\,$ generalizes to any algebraic integer $\rm\,r,\,$ most efficiently by using Dedekind's conductor ideal. This generalizes the above proofs into a slick one-line proof that PIDs are integrally-closed, as I explained at length elsewhere. It beautifully abstracts the denominator descent that governs ad-hoc "elementary" irrationality proofs.

Answer 9

So... we can prove something pretty general here: the only rational roots of polynomials $x^n + \cdots + a_0$ with integer coefficients are integers.

Indeed, suppose $p/q$ is a rational root, in lowest form, then $p^n = -q(a_0q^{n-1} + a_1pq^{n-2} + \cdots + a_{n-1}p^{n-1})$. Now, if $q>1$, then any prime divisor of $q$ also divides $p^n$, and hence $p$. But this contradicts our assumption that $p/q$ is in lowest form, so we conclude that $q=1$, so the root is integral.

Answer 10

Here's a proof that uses the same idea found in user65203's answer. It relies on the following theorem:

For all integers $n\geq 1$ and $k\geq 1$, $\sqrt[n]{k}$ is rational if and only if $k$ is the $n$th power of an integer, that is, $k=q^n$ for some integer $q$.

This implies that $\sqrt[b]{a}$ is either an integer or irrational because "$a=q^b$ for some integer $q$" is either true or it isn't. If it is, then $\sqrt[b]{a}=q$, so $\sqrt[b]{a}$ is an integer. If it isn't, then $\sqrt[b]{a}$ can't be rational because the prior theorem implies that $a=q^b$ is necessary for $\sqrt[b]{a}$ to be rational.

To prove the aforementioned theorem, we need to prove the following:

• If $k=q^n$ for some integer $q$, then $\sqrt[n]{k}$ is rational.
• If $\sqrt[n]{k}$ is rational, then $k=q^n$ for some integer $q$

Fix arbitrary integers $n\geq 1$ and $k\geq 1$. The first of these is trivial:

$$k=q^n\implies\sqrt[n]{k}=q$$

which shows that $\sqrt[n]{k}$ is an integer, and hence rational. To prove the second, we'll need two preliminary lemmas:

Lemma 1: if $a$ and $b>0$ are coprime integers and $b$ divides $a$, then $b=1$.

Proof: if $a$ and $b>0$ are coprime, then the only positive integer that simultaneously divides them is $1$. $b$ clearly divides $b$, and (by assumption) $b$ divides $a$, so $b$ is a positive integer that simultaneously divides $a$ and $b$. Since $1$ is the only number with this property, $b$ must equal $1$.

Lemma 2: if $a>0$ and $b>0$ are coprime integers, then $a^m$ and $b^n$ are coprime for any positive integers $m,n$.

Proof: it is known that two integers are coprime if and only if there is no prime that simultaneously divides them. By the fundamental theorem of arithmetic, we can write

$$a=p_1^{k_1}p_2^{k_2}\cdots p_r^{k_r}$$ $$b=q_1^{l_1}q_2^{l_2}\cdots q_s^{l_s}$$

where $p_1$, $p_2$, ...,$p_r$, $q_1$, $q_2$, ...,$q_s$ are primes, and $k_1$, $k_2$, ...,$k_r$, $l_1$, $l_2$, ...,$l_s$ are the corresponding exponents appearing in the factorization.

Fix an arbitrary pair of positive integers $(m,n)$ and raise $a$ and $b$ to the $m$th and $n$th power, respectively. We get

$$a^m=\left(p_1^{k_1}p_2^{k_2}\cdots p_r^{k_r}\right)^m=p_1^{mk_1}p_2^{mk_2}\cdots p_r^{mk_r}$$ $$b^n=\left(q_1^{l_1}q_2^{l_2}\cdots q_s^{l_s}\right)^n=q_1^{nl_1}q_2^{nl_2}\cdots q_s^{nl_s}$$

It can be seen that $a^m$ has the same prime factors as $a$, and $b^n$ the same ones as $b$. Since $a$ and $b$ are coprime, they don't share a prime factor, so the prior observation implies that there is no prime that simultaneously divides $a^m$ and $b^n$. It follows that $a^m$ and $b^n$ are coprime. Since $(m,n)$ was arbitrary, we conclude that $a^m$ and $b^n$ are coprime for every pair of positive integers $(m,n)$.

We are now in a position to prove the second statement. Assume that $\sqrt[n]{k}$ is rational. We can write

$$\sqrt[n]{k}=\frac{p}{q}$$

for integers $p$ and $q$, which we may assume to be positive and coprime since $\sqrt[n]{k}>0$ and every fraction is equivalent to a reduced fraction.

Now,

\begin{align*} \sqrt[n]{k}=\frac{p}{q} &\iff k=\left(\frac{p}{q}\right)^n\\ &\iff k=\frac{p^n}{q^n}\\ &\iff p^n = kq^n \end{align*}

and since $p$ and $q$ are coprime, we know from Lemma 2 that $p^n$ and $q^n>0$ are coprime. But the equation $p^n = kq^n$ implies that $q^n$ divides $p^n$. Thus, $q^n=1$ from Lemma 1, so the equation $p^n = kq^n$ reduces to $k=p^n$, which is what we were aiming to show.

Answer 11

A generalisation of Euclid's lemma states that if $n$ divides $ab$ and $n$ is coprime to $a$, then $n$ divides $b$. Using this lemma, it is easy to prove directly that if $x$ is rational and $x^2$ is an integer, then $x$ is an integer.

Suppose that $\left(\frac{p}{q}\right)^2=m$, where $p$ and $q$ are coprime, and $m$ is an integer. Then $p^2=mq^2$, so $q$ divides $p^2$. By the above lemma, $q$ divides $p$. But $p$ and $q$ are coprime, so $q=1$ and $m=p^2$.