Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I got this interesting question in my mind:

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

Can we extend this result? That is, can it be shown that if $a,b \in \mathbb N$, then $a^{1/b}$ is an integer or an irrational number?

share|improve this question
22  
It doesn't really make sense to say something is easy to see but you can't prove it. "It is easy to see this" is math jargon for "I have an easy proof of this". –  Carl Mummert Sep 12 '10 at 11:50
7  
@muad, anyone saying "it is easy to see" about the Jordan curve theorem only displays the fact that s/he has not thought about the thing enough and, more importantly, not even tried to actually prove it. –  Mariano Suárez-Alvarez Sep 12 '10 at 12:05
4  
It's not obvious, although the geometric model strongly suggests it when the curve is simple (e.g. a circle). In the present case, however, there is no geometric model that might suggest that no natural number has a non-integer rational square root, so the analogy is not very strong. –  Carl Mummert Sep 12 '10 at 12:21
4  
7  
One could say that the Jordan curve theorem seems obvious, but actually isn’t. One of the main aspects of mathematical training, I’d say, is learning to chase down your intuitions and either turn them into proofs (justifying that yes, something really was obvious!) or finding the weakness in the intuition (realising that actually something isn’t so obvious after all). –  Peter LeFanu Lumsdaine Nov 25 '10 at 22:06
show 7 more comments

9 Answers 9

up vote 21 down vote accepted

These (standard) results are discussed in detail in

http://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.

share|improve this answer
    
L.Clark: Thanks pete! –  anonymous Sep 12 '10 at 15:09
    
The remark in your last paragraph is misleading since the results under discussion are much weaker than the property of being a UFD. Indeed, even the stronger property of being integrally closed is much weaker than UFD. One can deduce that Z is integrally closed from more general results that don't (immediately) imply that Z is a UFD. –  Bill Dubuque Sep 12 '10 at 16:26
    
@BD: I certainly agree that for a general domain, being integrally closed is much weaker than being a UFD. But I'm having trouble thinking of an argument that one could give in an elementary number theory course which would show the integers are integrally closed but not that they are a UFD. What do you have in mind? –  Pete L. Clark Sep 12 '10 at 23:09
    
Why do you think that Robin's answer has any relevance to your remark? As I've argued at length elsewhere (via conductors) such descent-based proofs are just unwindings of ideal-theoretic proofs, so they really do invoke the Euclidean property or some essentially equivalent property of Z. –  Bill Dubuque Sep 14 '10 at 2:06
    
From your handout, when $n$ is not a perfect $k$th power, $\sqrt[k]{n}\not\in\Bbb Q$. What happen with $\sqrt[k]{r}$ for rational and positive $r$? –  leo Jun 11 at 5:08
add comment

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^t$. 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)]

share|improve this answer
1  
I LIKE this proof –  Dario Sep 12 '10 at 19:37
9  
I don't understand why this question was edited by someone other than D. Stones. If it was incorrect, we could state that in comments. –  Carl Mummert Sep 12 '10 at 23:55
1  
@Carl: see my response in the meta thread that you created about this meta.math.stackexchange.com/questions/793 –  Bill Dubuque Sep 13 '10 at 0:34
1  
@Bill: Since you have written your own answer to this question, perhaps you could leave a comment linking to that, with a brief explanation? –  Larry Wang Sep 13 '10 at 9:22
4  
@Bill, writing a comment to the incorrect answer is a pretty one, though :) –  Mariano Suárez-Alvarez Sep 13 '10 at 15:05
show 8 more comments

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.\,$ Thus $\rm\,n\in S\,$ $\Rightarrow$ $\rm\, (n\ mod\ \ell) = 0,\,$ else it is $\rm\,\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).

share|improve this answer
add comment

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.

share|improve this answer
    
Yeah! Niven's Proof! –  Mario De León Urbina Oct 5 '13 at 3:48
add comment

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.

share|improve this answer
    
Thanks, Robin. I will note that you used the division algorithm, which is also what you use to prove that $\mathbb{Z}$ is a UFD. (Admittedly, if you hadn't said that you used it then I wouldn't have seen it.) I guess the question is: is this in any sense easier than just proving FTA? I'm not sure... –  Pete L. Clark Sep 13 '10 at 7:27
1  
You'll certainly need something like the division algorithm. The argument will work for Euclidean domains too. Note how easy it is to use the division algorithm without being aware of it :-) –  Robin Chapman Sep 13 '10 at 9:31
    
@Robin: Agreed! –  Pete L. Clark Sep 13 '10 at 9:49
    
@Robin: are you using a hard carriage-return to end your lines? Seems like your comments are getting separated into several one-liners instead of a single one... –  Arturo Magidin Sep 13 '10 at 14:18
    
@Arturo: This is the result of a recent change in the stackexchange software. See meta for details. –  Larry Wang Sep 13 '10 at 23:42
show 2 more comments

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$.

share|improve this answer
    
Right -- this argument can be stated very cleanly using the ord_p functions, and is one of the proofs I give in the notes I linked to in my answer. (This is probably my favorite proof, since it showcases the usefulness of the ord_p's.) –  Pete L. Clark Sep 12 '10 at 14:55
add comment

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.

share|improve this answer
    
This is simply the monic case of the well-known rational root test which has already been mentioned above a few times. In more technical terms one simply says that Z is integrally closed (in its fraction field), i.e. fraction that is integral over Z (root of a monic polynomial) already lies in Z. –  Bill Dubuque Sep 14 '10 at 1:53
    
I saw people mention the rational root test... but then they just applied it to polynomials like x^b-a ... the point is that the same works for monic polynomials in general. That's all :) –  Dylan Wilson Sep 14 '10 at 1:55
    
They applied it to $ x^b - c $ simply because that's all that is required here. I don't recall anyone ever implying that it works only for such binomials. –  Bill Dubuque Sep 14 '10 at 1:57
    
No worries, wasn't trying to be confrontational here. I'll remove my last sentence if it makes you feel better –  Dylan Wilson Sep 14 '10 at 2:07
    
No problem, I was just trying to help ensure that you understood what was above. –  Bill Dubuque Sep 14 '10 at 2:08
add comment

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. the gcd $\rm\,(a,b)\,$ of integers $\rm\,a,b\,$ may be expressed as an integral linear combination of the given integers: $\rm\:\ (a,b)\ =\ a\ d - b\ c\:.\ $

THEOREM $\quad \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{#0C0}{\bf n}\:\Rightarrow\ 0\ =\ (a\!-\!br)\, (c\!+\!dr) \ =\ ac\!-\!bd\color{#0C0}{\bf n} \:+\: \color{#c00}{\bf 1}\cdot r \ \Rightarrow\ r \in \mathbb{Z}\ \ $ QED

This generalizes to roots of monic quadratic polynomials (and to higher degree, see here).

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}\ \ $ QED

Nowadays my favorite proof is the $1$-line gem using Dedekind's conductor ideal. As I explained at length elsewhere, it beautifully encapsulates the denominator descent in ad-hoc "elementary" irrationality proofs.

See also my other post here. That post concisely proves the theorem after first proving from scratch the fundamental lemma that the least positive denominator $\rm\:b\:$ of a fraction divides every other denominator, i.e. $\rm\ a/b = c/d\ \Rightarrow\ b\ |\ d\ $ if $\rm\ a/b\ $ is in lowest terms. The irrationality proof follows immediately from this principal denominator ideal theorem ("unique fractionization"), namely

Proof $\ \ $ Suppose $\displaystyle\;\rm \sqrt{n} \:= \frac{a}b,\;\;$ least $\rm b>0.\ \ $ $\displaystyle\rm\sqrt{n}\; = \frac{n}{\sqrt{n}} \ \Rightarrow\ \frac{a}b = \frac{nb}a \ \Rightarrow\ b\:|\:a\ \Rightarrow\ \sqrt{n}\ \in\ \mathbb Z$

share|improve this answer
    
so that $(a-br)(c+dr)=ac-bdn+r$ and since $ac-bdn$ is an integer and $a-br=0$, we get that $r=-(ac-bdn)\in\mathbb{Z}$. –  robjohn Aug 18 '12 at 15:11
    
@Peter The $\rm\color{#C00}{leading}$ coef of the product, viewed as a polynomial in $\rm\:r,\:$ is $\rm\:ad\!-\!bc.\:$ We want this $ = \color{#C00}{\bf 1},$ since the goal of the proof is: $\,$ given that $\rm\:r\:$ is a root of a monic polynomial $\rm\:r^2-a = 0\:$ to deduce a lower-degree monic polynomial also having $\rm\:r\:$ as a root. The inductive step is clearer if you look at said higher-degree generalization. There, using the same degree-reduction step, by induction, we eventually reach a monic linear polynomial $\rm\:r - n = 0\:$ so $\rm\:r=n\in \Bbb Z.\:$ –  Bill Dubuque Aug 18 '12 at 15:34
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.