Irrationality and the Fundamental Theorem of Arithmetic

[J. B. Kennedy]

Since the usual reductio proof of the irrationality of the square root of two is conceptually opaque, I thought that the sophisticate's explanation was that it was due to the FTAr, since

If r is the square root of two
and p=r q (i.e., suppose its rational),
then p squared = 2 q squared
but then the prime factors on both sides won't match up
(because the LHS is all primes squared and 2 is not)
which contradicts the FtAr and so r is irrational.

But I then came across a simpler, seemingly more basic proof ascribed to Niven (which doesn't invoke the FTAr):

If r is rational then
there is a least integer b such that br is an integer
but (br-b) is less than b (since r is btwn 1 and 2)
and then (br-b)r also is an integer,
which contradicts the assumption that b was the least
and so r is irrational.

There are many proofs of the irrationality of various constants, but
can we offer our students any simple conceptual answer to
the question of why the square root of two is irrational
beyond exhibiting the formal proofs?

[G.E. Ivey]

> Since the usual reductio proof of the irrationality
> of the square root of two is conceptually opaque, I
> thought that the sophisticate's explanation was that
> it was due to the FTAr, since
>
> If r is the square root of two
> and p=r q (i.e., suppose its rational),
> then p squared = 2 q squared
> but then the prime factors on both sides won't match
> up
> (because the LHS is all primes squared and 2 is not)
> which contradicts the FtAr and so r is irrational.
>
> But I then came across a simpler, seemingly more
> basic proof ascribed to Niven (which doesn't invoke
> the FTAr):
>
> If r is rational then
> there is a least integer b such that br is an
> integer
> but (br-b) is less than b (since r is btwn 1 and 2)
> and then (br-b)r also is an integer,
> which contradicts the assumption that b was the
> least
> and so r is irrational.
>

Where is the fact that r is sqrt(2) used here?
"There is a least integer b such that br is an
integer"?? If r= 1/2, then -2n for any positive integer n is an integer so there is no such least integer. Do you mean a least POSITIVE integer?
In that case, you have a problem: If r= 2/3, then "the least POSITIVE integer b such that br is an integer" is, of course, 3. In that case br-b= 3(2/3)- 3= 2- 3= -1 which is not a POSITIVE integer. Are you sure you have quoted Niven's proof correctly?

> There are many proofs of the irrationality of various
> constants, but
> can we offer our students any simple conceptual
> answer to
> the question of why the square root of two is
> irrational
> beyond exhibiting the formal proofs?

I don't see anything "opaque" about the using the fundamental theorem of arithmetic.

[J. B. Kennedy]

Thanks for your reply.
Yes, that should be least positive integer.
Note that the proof assumes (as it says in parentheses)
that the square root of 2 is between 1 and 2.
Then Niven's proof goes through.

It is interesting that the Niven proof uses only
this property (btwn 1 and 2) and thus can
be used to show that the square root of 3
is also irrational. (It can be generalized
for other integers and nth roots).

Yes to your last remark. I liked telling my students that the FTAr was behind the irrationality proof. Thus my puzzlement at seeing a
simpler proof that seems to rely only on the
well-ordering of the integers, which is an ingredient in
some proofs of the FTAr, and not the full-blown FTAr. My remark
about conceptual opacity was aimed at the traditional reductio.

[Jens Kruse Andersen]

J. B. Kennedy wrote:
> If r is rational then
> there is a least integer b such that br is an integer

There is a least *positive* integer b.

> but (br-b) is less than b (since r is btwn 1 and 2)
> and then (br-b)r also is an integer,

Why should (br-b)r be an integer?
Assume r = 3/2. Then b = 2 and (br-b)r = 3/2.

> which contradicts the assumption that b was the least
> and so r is irrational.

You don't use the assumption r = sqrt(b). You only assume 1<r<2.
If you "prove" all rational numbers between 1 and 2 are irrational,
then look for an error.

--
Jens Kruse Andersen

[Jens Kruse Andersen]

I wrote:
> You don't use the assumption r = sqrt(b).

I of course meant r = sqrt(2). Sorry for the typo.

--
Jens Kruse Andersen

[J. B. Kennedy]

Thanks for your reply.
(br-b)r is an integer because
the two r's in the first term square to an integer
and br is an integer by assumption.

The proof shows that all numbers between 1 and 2
which square to an integer (here 2) are irrational.

I think that it's a good proof. What do you think? JK

[Jens Kruse Andersen]

J. B. Kennedy wrote:
> Thanks for your reply.
> (br-b)r is an integer because
> the two r's in the first term square to an integer

Aah, you assume r = sqrt(2) in Niven's proof. That wasn't stated directly.
G. E. Ivey and I both thought you only assumed r was some rational number
between 1 and 2.

> and br is an integer by assumption.
>
> The proof shows that all numbers between 1 and 2
> which square to an integer (here 2) are irrational.
>
> I think that it's a good proof. What do you think? JK

I agree. But I also like this which doesn't use FTA:
Assume rational sqrt(2) = p/q, where p and q are not both even.
Then 2q^2 = p^2.
If p is odd then p^2 is odd, but 2q^2 is even.
If p is even and q odd then 4 divides p^2, but not 2q^2.
A contradiction is reached so sqrt(2) must be irrational.

--
Jens Kruse Andersen

[Gerry Myerson]

In article
<2825276.11525330070...@nitrogen.mathforum.org>,

"J. B. Kennedy" <john.b....@manchester.ac.uk> wrote:

> But I then came across a simpler, seemingly more basic proof ascribed to
> Niven (which doesn't invoke the FTAr):
>
> If r is rational then
> there is a least integer b such that br is an integer
> but (br-b) is less than b (since r is btwn 1 and 2)
> and then (br-b)r also is an integer,
> which contradicts the assumption that b was the least
> and so r is irrational.

According to Jorn Steuding, Diophantine Analysis, page 15,
this idea for proving the irrationality of sqrt 2 is due
to Estermann.

A reference is Math Gazette 59 (1975), page 110.

There's a geometric version of the same proof that John Conway
came up with a few years ago. Being a geometric proof, it's best
understood with the aid of diagrams, and such can be found on
pages 2 and 3 of http://www.nd.edu/~hahn/pdf%20files/Ch1-Addit.pdf
but I'll try to give it in words:

Suppose n^2 = 2 m^2, m, n integers.
Draw a square of side n, and put a square of side m in
the lower left corner, and another in the upper right corner.
This creates three squares along the upper left to lower right
diagonal; one in the middle, where the two m-squares overlap,
and one in each corner, that the m-squares miss. All three
of these squares have integer sides, and the two identical
corner ones must add up to the middle one. This gives a smaller
solution to x^2 = 2 y^2, and you get a proof by descent.

--
Gerry Myerson (ge...@maths.mq.edi.ai) (i -> u for email)

[J. B. Kennedy]

Thanks for the lovely references and links.

I like the Estermann proof because it also does not seem to rely on the
FTAr, and therefore does seem simpler than the usual proofs.

However, I do not think it is the same as the Niven proof. At least I cannot massage the algebra to make them look the same. The Niven proof uses the property that the square root of two is between one and two; the Estermann proof uses geometry to motivate an identity.

Both proofs leave me in a quandry. I used to tell my students that the irrationality was a consequence of the FTAr, now I will just have to say it is a `fact' with no deeper conceptual diagnosis.

[J. B. Kennedy]

Thanks again.
Your proof makes the assumption that 2q^2 is even.
This seems obvious or even definitional, but proving
it from first principles would, I think, require the FTAr.

Unique factorization into primes implies that, if a prime
factor goes into a product, the product will remain
a multiple of that factor. That's what you assume.

That's why I liked the first of the two proofs that I gave in the
original post: it nakedly invoked the FTAr and thus seemed
to anchor the proof in essential, deep ideas. But the Niven
proof doesn't seem to need the FTAr. I'm adrift. JBK

[Bill Dubuque]

Gerry Myerson <ge...@maths.mq.edi.ai.i2u4email> wrote:
> "J. B. Kennedy" <john.b....@manchester.ac.uk> wrote:
>
>> But I then came across a simpler, seemingly more basic proof
>> ascribed to Niven (which doesn't invoke the FTAr):
>>
>> If r is rational then
>> there is a least integer b such that br is an integer
>> but (br-b) is less than b (since r is btwn 1 and 2)
>> and then (br-b)r also is an integer,
>> which contradicts the assumption that b was the least
>> and so r is irrational.
>
> According to Jorn Steuding, Diophantine Analysis, page 15,
> this idea for proving the irrationality of sqrt 2 is due
> to Estermann.
>
> A reference is Math Gazette 59 (1975), page 110.

That proof is much, much older than 1975.
I'm shocked any number theorist could believe it so new.
Are you sure the reference is not to a different proof?

--Bill Dubuque

[J. B. Kennedy]

I agree that the Estermann and Niven proofs, though both are appealingly simple and avoid the FTAr, are not the same proof.
Can you remember when and where you learned the Niven proof?

[mariano.su...@gmail.com]

When I was shown that sqrt(2) is irrational, I had never
heard of the FTAr. The argument was as follows:

Assume r = p/q with p and q coprime is a square root
of 2. Then r q = p, and squaring we see that 2 q^2 = p^2
so that p^2 is even. One sees easily that this implies that
p itself is even (because the square of an odd number is odd),
say p = 2 s. Now we have that r q = 2 s, and squaring
we get 2 q^2 = 4 s^2, or, dividing by two, q^2 = 2s^2.
This shows q^2 is even, and by the same reason as before,
q is even. This contradicts our hypothesis that p and q
were coprime.

This only depends on knowing that an even number is a
multiple of two (!) and coprimality.

-- m

[Gerry Myerson]

In article
<14183393.1152611628...@nitrogen.mathforum.org>,

"J. B. Kennedy" <john.b....@manchester.ac.uk> wrote:

You can still tell your students that the irrationality of the square
root of two is a consequence of the Unique Factorization Theorem,
because it is - the proof using UFT doesn't become invalid, just because
there are proofs that don't use UFT. Moreover, the proof using UFT
generalizes to a proof that if n and k are integers and the k-th root
of n isn't an integer then it is irrational - it's a bit harder to get
this out of the other proofs, nice as they are. You can even go farther;
if a polynomial with integer coefficients is not satisfied by any
rational with numerator a factor of the constant term and denominator
a factor of the leading coefficient, then all of its roots are
irrational. And you prove this using UFT.

You can also use UFT to prove that the (common, base 10) logarithm
of 2 is irrational, if your students know about logarithms.

The Niven proof depends on the well-ordering principle, which to my
mind is a very deep conceptual diagnosis, deeper than UFT. It may seem
trivial to say that there are no integers between zero and one,
but it's actually very deep.

[Gerry Myerson]

In article <y8zzmfg...@nestle.csail.mit.edu>,
Bill Dubuque <w...@nestle.csail.mit.edu> wrote:

The London Mathematical Society published a long obituary
for Estermann. It's on the web, and one page of it,
http://www.numbertheory.org/obituaries/LMS/estermann/page11.html
is relevant here. It says, "In retirement, Estermann discovered
[1975] an elegant proof of Pythagoras's theorem which is actually
simpler than the original and is sufficiently short to be
included verbatim. [note - from what follows, it's evident
that they don't mean the theorem about the square of the hypotenuse,
they mean the irrationality of the square root of two]

They then give Estermann's proof, which is essentially
the one ascribed to Niven up near the top of this post.

I wouldn't be a bit surprised to learn that Niven (or someone)
got there before Estermann, but I don't think anyone in this
thread has cited a reference predating Estermann.

[Rob Johnson]

In article <2825276.11525330070...@nitrogen.mathforum.org>,

"J. B. Kennedy" <john.b....@manchester.ac.uk> wrote:

Another proof, using Bezout's formula, can be found at
<http://www.whim.org/nebula/math/ratalint.html>. There it is shown
that any algebraic integer which is also a rational number must be
an integer. Since the square root of 2 is an algebraic integer, but
not an integer, it cannot be rational.

Rob Johnson <r...@trash.whim.org>
take out the trash before replying
to view any ASCII art, display article in a monospaced font

[mariano.su...@gmail.com]

The argument in that link is slightly more complicated
than necessary:

Assume p/q, with q>0 and gcd(p, q) = 1, is a root of

f(x) = x^n + sum_{i=0}^{n-1} a_i x^i

with the a_i integral. Then

0 = q^n f(p/q) = p^n + sum_{i=0}^{n-1} a_i q^{n-i} p^i

Of course the sum is divisible by q so p^n is divisible
by q. This, together with gcd(p,q)=1 implies that q = 1, so that
p/q is an integer.

-- m

PS: This generalizes to the well-known lemma that says that
a rational root to a polynomial with integer coefficients has a
denominator which divides the leading coefficient, and a
numerator that divides the constant term.

[J. B. Kennedy]

Thanks. Your proof is the tradtional one that does
not seem to connect the result to any deep mathematical
principle, and is therefore conceptually opaque.

I claim it does assume more than that an even
number is a multiple of two. It assumes that one
number (q^2), which is equal to another which is
a multiple of two, is also a multiple of two. This slightly
different idea is an expression of the FTAr.

[J. B. Kennedy]

Yes, I now agree that the proof I thought was Niven's
was actually Estermann's. Thanks for the direct link
to that last page of the obituary.

Does this show that the FTAr is not a necessary ingredient of
proofs of irrationality? If so, what conceptual diagnosis
of irrationality can we offer our students? JK

[Virgil]

In article
<20434773.1152690104...@nitrogen.mathforum.org>,

"J. B. Kennedy" <john.b....@manchester.ac.uk> wrote:

We have just seen that the set of rationals whose squares are less than
2 does not have a rational LUB, but the set of reals must contain a LUB
(least upper bound) for that set.

So the completeness (LUB and GLB properties) of the field of reals
requires the presence of irrationals as well as rationals among the
reals.

[Rob Johnson]

In article <1152682261.7...@s13g2000cwa.googlegroups.com>,

It is definitely true that if gcd(p,q) = 1 and p^n is divisible by q,
then q = 1. The shorter proof above cites this fact, but leaves it
unproven. This fact can pretty quickly be proven by looking at the
primes dividing q and using the Fundamental Theorem of Arithmetic.
Another way of proving this fact is using Bezout's formula. My proof
linked above also avoids using the Fundamental Theorem of Arithmetic
by using Bezout's formula.

[mariano.su...@gmail.com]

Hm? The definition of `multiple' I was given in elementary
school was: a number n is a multiple of k if there is
a number m such that n = km. Your lemma that a number
which is equal to a another which is a multiple of 2 is itself
even follows from the transitivity of equality.

I'm quite sure you can prove that sqrt(2) is not rational
using the theory of quadatic reciprocity or even class field
theory. Maybe Brauer group theory can be used to. You can
probably pick a prime p with respect to which p-adic
analysis can frame a cool proof. You can certainly use
Dirichlet's principle that uses aproximability by rational
numbers to characterize irrationality. Or the theory of
values of algebraic functions.

Using tools that are unrelated to and overengineered
with respect to the fact you want to prove is what I call
opaque.

-- m

[mariano.su...@gmail.com]

Of course you need to prove that. But prove it as a separate
lemma, at the point where it is needed: it becomes much more
clear than using your substitution p/q -> (1-bq)/aq, which IMO
obscures what is happening.

-- m

[Gerry Myerson]

In article
<20434773.1152690104...@nitrogen.mathforum.org>,

"J. B. Kennedy" <john.b....@manchester.ac.uk> wrote:

Did you see the part where I wrote
that you can use the Unique Factorization Theorem
to prove that the base-10 logarithm of 2
is irrational?

There may be a way to prove that without the UFT,
but I've never seen it done.

I'm not entirely sure what you mean by
a "conceptual diagnosis of irrationality,"
On the first page of Chapter 1 of Burger & Tubbs,
Making Transcendence Transparent,
it says,

The Fundamental Principle of Number Theory: There are no integers
between zero and one.

Time after time, proofs of irrationality and/or transcendence
come down to this simple principle.
Is that a good enough "conceptual diagnosis of irrationality"
for you?

What do you want?

[Gerry Myerson]

In article <gerry-9B6BB4....@sunb.ocs.mq.edu.au>,
Gerry Myerson <ge...@maths.mq.edi.ai.i2u4email> wrote:

Although I've worked out how to do a Well-Ordering Principle proof
of the polynomial result.

Theorem: Let f be a monic polynomial with integer coefficients.
Let r be a solution of f(r) = 0. Then if r is not an integer,
it is irrational.

Proof. Assume the hypotheses, assume r is rational, and let n
be the smallest positive integer such that n r^j is an integer
for all j less than the degree of f. Then n {r} (where {z}
means the fractional part of z) is a smaller positive integer
with the same property, contradiction, QED.

Justification of this proof is a good exercise for the reader,
and the reader who wants some good exercise should skip the rest
of this post & figure out the justification on her own.

First of all, if r is rational, say, r = a / b with a and b
integers, b > 0, then b^(d - 1), where d is the degree of f, has
the property that multiplication by r^j gives an integer for all
j less than the degree of f. Thus, the set of all such positive
integers is not empty. By Well-Ordering, there is a least such
positive integer, which we call n.

As r is not an integer, we have 0 < {r} < 1, so 0 < n {r} < n,
so n {r} is a smaller positive integer. We write {r} = r - k
for some integer k.

[Aside: we're using the mathematician's definition of fractional
part, where, e.g., {- 0.3} = 0.7]

Now n {r} r^j = n r^(j + 1) - k n r^j is clearly an integer so
long as j + 1 is less than the degree of f. But the equation
f(r) = 0 tells us how to write r^d as a sum of integer multiples
of smaller powers of r, so even in the case j = d - 1 we get
that n {r} r^j is an integer.

This completes the justification of the proof.

[Gerry Myerson]

In article <gerry-62AB1D....@sunb.ocs.mq.edu.au>,
Gerry Myerson <ge...@maths.mq.edi.ai.i2u4email> wrote:

I've had a bit of a look for the proof.

In a thread on sci.math.research in September, 1998, Jim Propp
attributed the proof to Niven, without any references. Michael
Hardy claimed that the proof was actually older than the odd/even
and unique factorization proofs, but I think he was talking
about a geometric proof. The Well-Ordering proof may be nothing
more than the algebraic formulation of that geometric proof, but
I don't accept that the geometric proof *is* the well-ordering
proof.

You can find the Propp and Hardy posts under the Subject header,
The Book.

I didn't find the proof in Niven's book, Numbers: Rational and
Irrational, in the New Mathematical Library series, nor in his
book, Irrational Numbers, in the Carus Mathematical Monographs
series. I searched Math Reviews for anything that had both
Niven and irrational in it, and found nothing that looked like
a reference to this proof.

David Bloom published (a version of) the proof in Mathematics
Magazine (A one-sentence proof that sqrt2 is irrational, Math
Mag 68 (1995) 286). He writes that it is an algebraic version
of a geometric argument in a math history book by Eves, and it
was presented by Niven at a lecture in 1985.

In short, I still haven't found any reference to Niven or any-
one else preceding Estermann's paper in 1975.

[J. B. Kennedy]

Thanks for both of your illuminating posts. May I respond to
both with this one message?

I will take a look at the Burger and Tubbs and the Maths Mag article. They look promising.

I like the suggestion that the basic problem is that there are no integers
between zero and one (etc.), and that this is the root cause of irrationality. Irrationality is so important and so influential in mathematics, it is surprising to me that there is no clear consensus about its nature. I was satisfied with thinking it was a manifestation of the FTAr, itself a deep idea, and thus provoked by the Well-Ordering proofs which seem partially or fully to avoid it.

Most (or all?) proofs of irrationality or transcendence are proofs by contradiction, and these are, however formally acceptable, always a cheat because they depend upon further arguments to pick out the offending assumption. What I would like is a `positive proof.'

Irrationality is a negative property and thus deriving it requires some negative assumption (say, with an odd number of negations). I would like a proof which starts with something like `there are no integers between zero and one, etc.' and leads to `there is no rational root of two' but is not a proof by contradiction. Without that, I think we are missing something. We cannot formally anatomize the interaction between the structure of the natural numbers and the nature of multiplication which produces irrationality. The Well-Ordering proofs look so simple, they suggest to me that such a positive proof must be lurking nearby. I'll work on it.

Thanks again for your refs and the thoughtful response. J. K.

[Gerry Myerson]

In article
<24726914.1152871938...@nitrogen.mathforum.org>,

"J. B. Kennedy" <john.b....@manchester.ac.uk> wrote:

> I like the suggestion that the basic problem is that there are no integers
> between zero and one (etc.), and that this is the root cause of
> irrationality. Irrationality is so important and so influential in
> mathematics, it is surprising to me that there is no clear consensus about
> its nature. I was satisfied with thinking it was a manifestation of the FTAr,
> itself a deep idea, and thus provoked by the Well-Ordering proofs which seem
> partially or fully to avoid it.
>
> Most (or all?) proofs of irrationality or transcendence are proofs by
> contradiction, and these are, however formally acceptable, always a cheat
> because they depend upon further arguments to pick out the offending
> assumption. What I would like is a `positive proof.'
>
> Irrationality is a negative property and thus deriving it requires some
> negative assumption (say, with an odd number of negations). I would like a
> proof which starts with something like `there are no integers between zero
> and one, etc.' and leads to `there is no rational root of two' but is not a
> proof by contradiction. Without that, I think we are missing something. We
> cannot formally anatomize the interaction between the structure of the
> natural numbers and the nature of multiplication which produces
> irrationality. The Well-Ordering proofs look so simple, they suggest to me
> that such a positive proof must be lurking nearby. I'll work on it.

How about this:

There are no integers between zero and one. Therefore, the numbers
n sqrt 2, n sqrt 2 (sqrt 2 - 1), n sqrt 2 (sqrt 2 - 1)^2,
n sqrt 2 (sqrt 2 - 1)^3, etc., can't all be integers. Therefore,
none of them can be an integer (since it's easy to show that if any
one is an integer, so is the next one). In particular, n sqrt 2 can't be
an integer. Thus, there is no rational square root of 2.

[Gene Ward Smith]

J. B. Kennedy wrote:

> Most (or all?) proofs of irrationality or transcendence are proofs by contradiction, and these are, however formally acceptable, always a cheat because they depend upon further arguments to pick out the offending assumption. What I would like is a `positive proof.'

If you define a rational number as a number whose continued fraction
terminates and an irrational number as a number where it does not
terminate, you can prove some irrationality results directly--including
not only sqrt(2), but also eg e.

[mariano.su...@gmail.com]

J. B. Kennedy wrote:
> [snip]

> I like the suggestion that the basic problem is that there are no integers
> between zero and one (etc.), and that this is the root cause of irrationality. Irrationality is so important and so influential in mathematics, it is surprising to me that there is no clear consensus about its nature.

You seem to attach to irrationality an importance and an influence
that I nor none of the matematicians I've ever met and worked with
attaches to that notion. Moreover, I would be surprised if there
were anything at all regarding this notion which is not the subject
of a wide consensus.

I can but wonder from where you get these impressions.

D'Alambert used to tell his students ``Allez en avant, et la foi
vous viendra''...

-- m

(*) That is, something similar to ``go forwards, faith
will come to you of its own''

[fishfry]

In article <1153103891.4...@s13g2000cwa.googlegroups.com>,
"mariano.su...@gmail.com" <mariano.su...@gmail.com>
wrote:

> D'Alambert used to tell his students ``Allez en avant, et la foi
> vous viendra''...

"Push on and faith will catch up with you."

Sounds like JSH's motto!

[Bill Dubuque]

Rob Johnson <r...@trash.whim.org> wrote:
"J. B. Kennedy" <john.b....@manchester.ac.uk> wrote:
>>

>> [...] can we offer our students any simple conceptual answer

>> to the question of why the square root of two is irrational
>> beyond exhibiting the formal proofs?
>
> Another proof, using Bezout's formula, can be found at
> <http://www.whim.org/nebula/math/ratalint.html>. There it is shown
> that any algebraic integer which is also a rational number must be
> an integer. Since the square root of 2 is an algebraic integer,
> but not an integer, it cannot be rational.

If you insist on presenting this proof in Bezout (vs. GCD) form
then perhaps you should consider the following lucid presentation
(which actually proves that a Bezout domain is integrally closed).

THEOREM A rational root of a monic poly f(x) in Z[x] is integral

PROOF Suppose f(x) has a rational root p/q with gcd(p,q) = 1.

n = deg f -> q|p^n via 0 = q^n f(p/q) = p^n (mod q)

-> q|(ap+bq)^n = 1 via ap+bq = 1 (Bezout) QED

Or, ideally: (1) = (p,q)^n < (p^n,q) = (q) via q|p^n

Notice how I have emphasized the proof's ideal-theoretic essence.
Alas, that essence is obfuscated in the proof you present below,
as I pointed out the last two times you posted this proof [1,2]
where I gave the usual gcd-based proof of the RATIONAL ROOT TEST.

--Bill Dubuque

[1] http://google.com/groups?selm=y8zln3tyyhq.fsf%40nestle.ai.mit.edu
[2] http://google.com/groups?selm=y8z1xywyprp.fsf%40nestle.ai.mit.edu

Rob Johnson wrote at http://www.whim.org/nebula/math/ratalint.html
>
> Rational Algebraic Integers are Integers
> ----------------------------------------
> An algebraic number is defined as any root of a polynomial with integer
> coefficients. An algebraic integer is any root of a polynomial with
> integer coefficients where the coefficient of the leading term is 1.
> For example, phi, the golden ratio is an algebraic integer because it
> is a root of x^2 - x - 1.
>
> The claim is that all algebraic integers that are also rational numbers
> are integers. Suppose p/q is a rational number, with GCD(p,q) = 1 and
> q > 0, that is a root of
>
> n-1
> n --- k
> f(x) = x + > c x [1]
> --- k
> k=0
>
> Since GCD(p,q) = 1, there are integers a and b so that ap + bq = 1.
> Thus, p/q = (1-bq)/(aq). Since f(p/q) = 0, we have that
>
> n-1
> 1-bq n --- 1-bq k
> 0 = ( ---- ) + > c ( ---- ) [2]
> aq --- k aq
> k=0
>
> Multiplying both sides of [2] by a^n q^{n-1}, we get
>
> n-1
> (1-bq)^n --- k n-k n-k-1
> 0 = -------- + > c (1-bq) a q
> q --- k
> k=0
>
> n n-1
> 1 --- k k-1 --- k n-k n-k-1
> = - + > C(n,k) (-b) q + > c (1-bq) a q [3]
> q --- --- k
> k=1 k=0
>
> Everything on the right side of [3], except 1/q, is sums of products of
> integers. Since the right hand side of [3] sums to 0, we must have that
> 1/q is an integer as well; therefore, p/q is an integer.
>
> Another way of expressing this is by saying that if an algebraic integer
> is not an integer, then it is irrational.

[N. Silver]

Gerry Myerson wrote:
> Bill Dubuque wrote:

>> That proof is much, much older than 1975.
>> I'm shocked any number theorist could believe it so new.
>> Are you sure the reference is not to a different proof?

> The London Mathematical Society published a long obituary
> for Estermann. It's on the web, and one page of it,
> http://www.numbertheory.org/obituaries/LMS/estermann/page11.html
> is relevant here. It says, "In retirement, Estermann discovered
> [1975] an elegant proof of Pythagoras's theorem which is actually
> simpler than the original and is sufficiently short to be
> included verbatim. [note - from what follows, it's evident
> that they don't mean the theorem about the square of the hypotenuse,
> they mean the irrationality of the square root of two]
>
> They then give Estermann's proof, which is essentially
> the one ascribed to Niven up near the top of this post.
>
> I wouldn't be a bit surprised to learn that Niven (or someone)
> got there before Estermann, but I don't think anyone in this
> thread has cited a reference predating Estermann.

My apologies for not posting in this thread sooner. The
argument is very old. I remember a geometric version of it,
using a square within a square in Felix Klein's texts and
revived in another form by Apostol in a relatively recent
issue the American Mathematical Monthly. The argument
goes as follows:

Suppose sqrt(2) is rational. Then there is a smallest k in N
such that of all triangles similar to the one of sides 1, 1, sqt(2),
k, k, ksqrt(2) has integer sides (right triangle ABC).

B
*
* |
* |
* |
k* sqrt(2) * |
D * |
* *` |
* * ` |
k * * ` |
* * `E
* * |
* * |
* *|
*-----------------------------*
A k C

Draw the circular arc centered at A of radius AC
that meets hypotenuse AB at D. Erect a perpendicular
at D that crosses BC at E. Then smaller triangle BED,
being similar to ABC (having two angles in common
with) puts the matter to rest. BD = ksqrt(2) - k, an
integer. Also leg DE = ksqrt(2) - k, by similarity with
triangle ABC. But EC = ksqrt(2) - k as well, since
point E is an intersection of tangents. So, hypotenuse
BE = k - (ksqrt(2) - k).

[N. Silver]

Gerry Myerson wrote:

> I wouldn't be a bit surprised to learn that Niven (or someone)
> got there before Estermann, but I don't think anyone in this
> thread has cited a reference predating Estermann.

Here are references:

Chrystal, Algebra, Part 1, Seventh Edition, 1964, page 270.
(The body of the text hardly has changed since 1904.)

Rademacher and Toeplitz, The Enjoyment of Mathematics, 1957,
pages 23-25.

[Robert Maas, see http://tinyurl.com/uh3t]

> Most (or all?) proofs of irrationality or transcendence are proofs by
> contradiction, and these are, however formally acceptable, always a
> cheat because they depend upon further arguments to pick out the
> offending assumption. What I would like is a `positive proof.'

My view is opposite yours: At the start, we're not trying to prove
there *is* a number and it is irrational, which is a positive claim,
seemingly needing a positive proof. We're trying to prove the
non-existance of any rational number satisfying some equation, such as
r^2 = 2, a negative claim. A proof by contradiction, pretend there is
such a (rational) solution and thereby get stuck with a contradiction,
seems entirely reasonable. In fact I don't see how it's even possible
for a positive proof to yield a negative result, except as a lemma of
some more powerful theorem which was itself proved by contradiction.

Note there is only one assumption, that r^2 = 2 has a solution (r rational).
I see no need for an argument which assumption is false.

> I would like a proof which starts with something like `there are no
> integers between zero and one, etc.' and leads to `there is no rational
> root of two' but is not a proof by contradiction.

Earlier in this thread somebody mentionned that the lack of integers
between zero and one is a deep result, or difficult to prove, somesuch.
I'm wondering whether such a proof is by contradiction (assume an
integer between zero and one, and get a contradiction), in which case
we simply have a lemma depending on a theorem proved by contradiction,
which IMO shouldn't satisfy you one bit more than a direct proof by
contradiction. ("direct" means directly proving r^2 = 2 has no solution)

[Gerry Myerson]

In article <REM-2006...@Yahoo.Com>,

rem...@Yahoo.Com (Robert Maas, see http://tinyurl.com/uh3t) wrote:

> Earlier in this thread somebody mentionned that the lack of integers
> between zero and one is a deep result, or difficult to prove, somesuch.
> I'm wondering whether such a proof is by contradiction (assume an
> integer between zero and one, and get a contradiction), in which case
> we simply have a lemma depending on a theorem proved by contradiction,
> which IMO shouldn't satisfy you one bit more than a direct proof by
> contradiction. ("direct" means directly proving r^2 = 2 has no solution)

That there are no integers between zero and one
is an easy consequence of the well-ordering property:
if x is an integer strictly between zero and one
then x^2 is a smaller integer strictly between zero and one,
contradiction, qed.

One can instead take this theorem as an axiom
(where it accords with the ancient notion of an axiom
as something manifestly true)
and then prove well-ordering, induction, etc., as theorems.

[Gerry Myerson]

In article
<mctwg.161192$mF2.1...@bgtnsc04-news.ops.worldnet.att.net>,
"N. Silver" <mat...@worldnet.att.net> wrote:

Indeed, these proofs go back to ancient Greece, but they are
geometric; what I didn't make clear is that I was asking for,
not just a proof based on well-ordering, but the particular
proof given by Estermann, the one that goes, if n is the smallest
positive integer whose product with sqrt 2 is an integer, then
n ( sqrt 2 - 1 ) is a smaller positive integer whose product
with sqrt 2 is an integer, contradiction, qed. The logic behind
this proof may be the same as that behind the geometric proofs,
but I still think there's a useful distinction to be made
between the two ways of setting it out.