Proof that the sqrt (2) is irrational
Porker899
irrational but I was wondering if anyone has ever seen a very short proof of it
(or if there is a "shortest proof" of it).
My other question was that after a course in number theory roughly around the
level of Rosen's "Elementary Number Theory and its Applications", if anyone had
any suggestions on number theory books that I could study afterwards. In other
words, what are some other areas with good books that I could use to study on
my own? I did not know if Rosen's book was sufficient to move on or if I
needed to find a more advanced introductory book.
Thanks in advance.
Ronald Bruck
the "To," "Cc," and "Newsgroups" headers for details. ]]
In article <20030517231617...@mb-m03.aol.com>, Porker899
<pork...@aol.com> wrote:
Hardy and Wright. Definitely.
--Ron Bruck
Dean
Elementary Classical Analysis" had the following proof:
Assume that the sqrt(2) is rational. Then, by definition there are
Relatively Prime Integers P and Q such that
sqrt(2) = P/Q. Which implies that
2 = (P/Q)^2 = (P^2) / (Q^2). Which implies that
2*(Q^2) = P^2. Which implies that 2 divides P^2. Which implies that 2
divides P. Which implies that 4 divides P^2. Which implies that 4 divides
2*(Q^2). Which Implies that 2 divides Q^2. Which implies that 2 divides Q.
Which contradicts the assumption that Q and P are relatively prime (since 2
divides them both). Therefore there are no such two Relatively Prime
Integers, P and Q, such that sqrt(2) = P/Q, and therefore sqrt(2) is not
rational.
I am unfamiliar with Rosen's text.
"Porker899" <pork...@aol.com> wrote in message
news:20030517231617...@mb-m03.aol.com...
Michael Knudsen
> I actually have two questions. I know how to prove that the sqrt (2) is
> irrational but I was wondering if anyone has ever seen a very short proof of it
> (or if there is a "shortest proof" of it).
Dean has given the standard proof, and I don't think you can do it
shorter without referring to results not as trivial as this. For
example sqrt(p) (especially sqrt(2)) is irrational for all p since
X^p-1 is irreducible in Q[X] by the Eisenstein irreducibility criterium.
--
Michael Knudsen [knu...@imf.au.dk]
Jon Haugsand
> I actually have two questions. I know how to prove that the sqrt (2) is
> irrational but I was wondering if anyone has ever seen a very short proof of it
> (or if there is a "shortest proof" of it).
How do you define "shortness" here? (Proof theory has the concept,
but I somehow doubt this is what you have in mind.)
Assume m/n=sqrt(2). If both n and m are even, divide by 2 until at
least one of them is odd.
Then m*m/n*n = 2, or m*m=2*n*n. Thus m has to be an even number
(because odd times odd = odd). So, if m=2*m' we have:
2*m'*m' = n*n, but then n also has to be even --> contradiction.
--
Jon Haugsand
Dept. of Informatics, Univ. of Oslo, Norway, mailto:jon...@ifi.uio.no
http://www.ifi.uio.no/~jonhaug/, Phone: +47 22 95 21 52
Rouben Rostamian
>irrational but I was wondering if anyone has ever seen a very short proof
>of it (or if there is a "shortest proof" of it).
I guess the standard proof is as short as it gets.
However...
There is a _very_ short proof of the fact that the nth root
of 2 is irrational when n is an integer > 2.
Here's how it goes:
Suppose the nth root of 2, with n>2, is rational. Then there exit
integers p and q such that (p/q)^n = 2, that is, p^n = 2q^n or
q^n + q^n = p^n. By Fermat's Last Theorem this equation has
no integer solutions. QED.
This appeared in one of the recent issues of the American
Mathematical Monthly.
--
Rouben Rostamian <rost...@umbc.edu>
G. Frege
>
> I actually have two questions. I know how to prove that the sqrt(2) is
> irrational but I was wondering if anyone has ever seen a very short proof
> of it
>
Assume sqrt(2) = n/m for some n,m e N. Then 2m^2 = n^2. This is
impossible. (The power of 2 occurring in the prime factorization of the
left hand side of the equation would be _odd_, while it would be _even_
at the right hand side. This is not possible by the PF theorem.) qed.
F.
Joona I Palaste
> However...
This also means that if Fermat's Last Theorem were false, there would
exist n:th roots of 2, where n is a natural>2, that had rational values.
This seems very counter-intuitive but I think it can't be proven to be
false any easier than Fermat's Last Theorem can be proven to be true.
--
/-- Joona Palaste (pal...@cc.helsinki.fi) ---------------------------\
| Kingpriest of "The Flying Lemon Tree" G++ FR FW+ M- #108 D+ ADA N+++|
| http://www.helsinki.fi/~palaste W++ B OP+ |
\----------------------------------------- Finland rules! ------------/
"We're women. We've got double standards to live up to."
- Ally McBeal
Terry E
"Michael Knudsen" <knu...@localhost.localdomain> wrote in message
news:udd65o8...@localhost.localdomain.i-did-not-set--mail-host-address-
-so-tickle-me...
> --
> Michael Knudsen [knu...@imf.au.dk]
>
Joona I Palaste
> Rouben Rostamian <rou...@pc18.math.umbc.edu> scribbled the following:
>> In article <20030517231617...@mb-m03.aol.com>,
>> Porker899 <pork...@aol.com> wrote:
>>>I actually have two questions. I know how to prove that the sqrt (2) is
>>>irrational but I was wondering if anyone has ever seen a very short proof
>>>of it (or if there is a "shortest proof" of it).
>> I guess the standard proof is as short as it gets.
>> However...
>> There is a _very_ short proof of the fact that the nth root
>> of 2 is irrational when n is an integer > 2.
>> Here's how it goes:
>> Suppose the nth root of 2, with n>2, is rational. Then there exit
>> integers p and q such that (p/q)^n = 2, that is, p^n = 2q^n or
>> q^n + q^n = p^n. By Fermat's Last Theorem this equation has
>> no integer solutions. QED.
>> This appeared in one of the recent issues of the American
>> Mathematical Monthly.
> This also means that if Fermat's Last Theorem were false, there would
> exist n:th roots of 2, where n is a natural>2, that had rational values.
> This seems very counter-intuitive but I think it can't be proven to be
> false any easier than Fermat's Last Theorem can be proven to be true.
Lies, all lies! Lies, I tell you! It would not mean that!
If Fermat's Last Theorem were false, that means there would exist some
4-tuples of naturals (x, y, z, n) so that n>2 and x^n + y^n = z^n. For
them to correspond to a rational-valued natural root of 2, x and y would
have to be equal. That is a stronger requirement than them both being
natural.
Sorry about the screw-up. Sometimes I don't think things all the way
through.
--
/-- Joona Palaste (pal...@cc.helsinki.fi) ---------------------------\
| Kingpriest of "The Flying Lemon Tree" G++ FR FW+ M- #108 D+ ADA N+++|
| http://www.helsinki.fi/~palaste W++ B OP+ |
\----------------------------------------- Finland rules! ------------/
"No, Maggie, not Aztec, Olmec! Ol-mec!"
- Lisa Simpson
Denis Feldmann
Oh... I thought yo just meant that if FLT was false, then sqrt(2) would be
rational and 2+2 would be equal to 5. After all, FLT *is* true, so...
>
>> Kingpriest of "The Flying Lemon Tree" G++ FR FW+ M- #108 D+ ADA N+++|
>> http://www.helsinki.fi/~palaste W++ B OP+ |
> \----------------------------------------- Finland rules! ------------
> / "No, Maggie, not Aztec, Olmec! Ol-mec!"
> - Lisa Simpson
Pete Klimek
"G. Frege" <g.f...@simple-line.de> wrote in message
news:3edecvsnhdb5klu6u...@4ax.com...
> On 18 May 2003 03:16:17 GMT, pork...@aol.com (Porker899) wrote:
>
> >
> > I actually have two questions. I know how to prove that the sqrt(2) is
> > irrational but I was wondering if anyone has ever seen a very short
proof
> > of it
> >
>
positive integer k such that k*sqrt(2) is an integer. However, k*sqrt(2) - k
is a smaller such integer, contradiction.
Pete Klimek
Michael Knudsen
>> Dean has given the standard proof, and I don't think you can do it
>> shorter without referring to results not as trivial as this. For
>> example sqrt(p) (especially sqrt(2)) is irrational for all p since
>> X^p-1 is irreducible in Q[X] by the Eisenstein irreducibility criterium.
> What is (1) ^p - 1 ?
It was to early in the morning. Of course (?) I meant: X^2-p is
irreducible (...)
--
Michael Knudsen [knu...@imf.au.dk]
Rob Johnson
The length of a proof depends on what you are allowed to use. If you
can use the Fundamental Theorem of Arithmetic, that integers can be
factored uniquely into a product of powers of primes, then you can use
the proofs given so far in other threads.
However, another useful theorem is that rational algebraic integers are
integers (see http://www.whim.org/nebula/math/ratalint.html). Using
this theorem, you can note that sqrt(2) is an algebraic integer since it
satisfies x^2 - 2 = 0 to which there are no integer solutions. Thus,
sqrt(2) is irrational.
Rob Johnson
r...@whim.org
Stephen J. Herschkorn
>
>Another short proof: If sqrt(2) is rational, then there exists a smallest
>positive integer k such that k*sqrt(2) is an integer. However, k*sqrt(2) - k
>is a smaller such integer, contradiction.
>
>
As short as it is invalid.
--
Stephen J. Herschkorn hers...@rutcor.rutgers.edu
Doug Norris
>Another short proof: If sqrt(2) is rational, then there exists a smallest
>positive integer k such that k*sqrt(2) is an integer. However, k*sqrt(2) - k
>is a smaller such integer, contradiction.
By that logic, consider 6/5. 6/5 is rational, therefore there exists a
smallest positive integer (namely 5) such that 5 * 6/5 is an integer. However,
(5 * 6/5 - 5) = (6 - 5) = 1, a smaller such integer.
Now...find the flaw in your proof.
Doug
Denis Feldmann
Tss, tss.. . I had this reaction at first. But, in fact, you read it wrong :
1 is not a smaller integer *such that * 1* 6/5 is an integer. But n =k
sqrt(2)-k * is one*, as n*sqrt(2)=2k-ksqrt(2), an integer *by definition of
k*
>
> Doug
Denis Feldmann
>> Another short proof: If sqrt(2) is rational, then there exists a
>> smallest positive integer k such that k*sqrt(2) is an integer.
>> However, k*sqrt(2) - k is a smaller such integer, contradiction.
>>
>>
>
> As short as it is invalid.
Perfectly valid : let's decompose it.
n=k*sqrt(2)-k is a positive integer (if k*sqrt(2) is one) , because
1<sqrt(2).(and n<k, because sqrt(2)<2) But then n*sqrt(2)=2k-ksqrt(2), and
(by hypothesis), this is an integer, so n is a smaller integer than k
*having the same property*
G. Frege
wrote:
????
> Now...find the flaw in your proof.
>
Imho the proof is valid. Note that he said _such_ an integer (not just
"...integer"). In fact, IF k*sqrt(2) is an integer then (k*sqrt(2) -
k)*sqrt(2) is an integer too (!). (That's not true for 1*6/5.) And it's
smaller than k.
We just have to consider that sqrt(2) < 2. Which follows easily from
sqrt(2)^2 = 2.
F.
G. Frege
wrote:
> ...And it's smaller than k.
^^^^
Ehhrrr, I meant _k*sqrt(2) - k_ is smaller than k, of course (and it's
also an integer IF k*sqrt(2) is one).
F.
fourierr
Neat! And it can be adjusted for any sqrt(n) where
sqrt(n) is not an integer.
Whose proof is this?
fourierr
--
Direct access to this group with http://web2news.com
http://web2news.com/?sci.math
R3769
>As I recall (from about 25 years ago) a book titled "An Introduction to
>Elementary Classical Analysis" had the following proof:
>Assume that the sqrt(2) is rational. Then, by definition there are
>Relatively Prime Integers P and Q such that
>sqrt(2) = P/Q. Which implies that
>2 = (P/Q)^2 = (P^2) / (Q^2). Which implies that
>2*(Q^2) = P^2. Which implies that 2 divides P^2. Which implies that 2
>divides P. Which implies that 4 divides P^2. Which implies that 4 divides
>2*(Q^2). Which Implies that 2 divides Q^2. Which implies that 2 divides Q.
>Which contradicts the assumption that Q and P are relatively prime (since 2
>divides them both). Therefore there are no such two Relatively Prime
>Integers, P and Q, such that sqrt(2) = P/Q, and therefore sqrt(2) is not
>rational.
>
It seems to me there is something missing here. You have shown sqrt(2) is not
rational, but why does it follow that sqrt(2) is irrational? For example
sqrt(-1) is not rational AND not irrational.
Regards,
Rich Burge
G. Frege
Though one certainly could say that the argument is not really _obvious_
in this proof. In contrast to the argument in the other _short_ proof.
Moreover, the other proof allows a simple generalization:
sqrt(p) is irrational for any p prime. (!)
While the proof above breaks down for n > 3 (though it covers sqrt(2)
and sqrt(3)).
F.
G. Frege
<fourierr.n...@web2news.net> wrote:
> >
> > Another short proof: If sqrt(2) is rational, then there
> > exists a smallest positive integer k such that k*sqrt(2)
> > is an integer. However, k*sqrt(2) - k is a smaller such
> > integer, contradiction.
> >
>
> Neat! And it can be adjusted for any sqrt(n) where
> sqrt(n) is not an integer.
>
How would you adjust it to prove that sqrt(5) is irrational?
F.
Rouben Rostamian
You need to search for a flaw in your own arguement. The original
proof relies on the fact that the square of sqrt(2) is an integer.
This does not hold for 6/5.
--
Rouben Rostamian <rost...@umbc.edu>
Doug Norris
Fair enough. Accounting for the vagueness, I like the proof - it also
seems to work for any other irrational square root.
Doug
Rouben Rostamian
If sqrt(5) is rational, then there
exists a smallest positive integer k such that k*sqrt(5)
is an integer. However, k*sqrt(5) - 2k is a smaller such
integer, contradiction.
--
Rouben Rostamian <rost...@umbc.edu>
David C. Ullrich
wrote:
>On Sun, 18 May 2003 19:59:34 +0200, "Denis Feldmann"
><denis.f...@wanadoo.fr> wrote:
>
>> Stephen J. Herschkorn wrote:
>> >> Another short proof: If sqrt(2) is rational, then there exists a
>> >> smallest positive integer k such that k*sqrt(2) is an integer.
>> >> However, k*sqrt(2) - k is a smaller such integer, contradiction.
>> >>
>> >>
>> >
>> > As short as it is invalid.
>>
>> Perfectly valid : let's decompose it.
>>
>> n=k*sqrt(2)-k is a positive integer (if k*sqrt(2) is one) , because
>> 1<sqrt(2).(and n<k, because sqrt(2)<2) But then n*sqrt(2)=2k-ksqrt(2), and
>> (by hypothesis), this is an integer, so n is a smaller integer than k
>> *having the same property*
>>
>
>Though one certainly could say that the argument is not really _obvious_
One could say a lot of things. Which step was too hard for you,
showing that k*sqrt(2) - k was less than k or showing that
sqrt(2)*(k*sqrt(k) - k) was an integer? They're both utterly
straightforward.
>in this proof. In contrast to the argument in the other _short_ proof.
Actually I like this proof a lot, because it's much simpler than
the usual proof! You posted _this_ as the "short" proof:
>>Assume sqrt(2) = n/m for some n,m e N. Then 2m^2 = n^2. This is
>>impossible. (The power of 2 occurring in the prime factorization of the
>>left hand side of the equation would be _odd_, while it would be _even_
>>at the right hand side. This is not possible by the PF theorem.) qed.
That's using the uniqueness of the prime factorization for positive
integers, which is a _much_ less obvious fact than anything used
in the proof above! If you think it's more obvious that's just because
you're accustomed to it, and you're not accustomed to the sort
of reasoning used in the proof above - if you can write out a proof
of the uniqueness of prime factorization without looking it up,
and in as little time as it takes one to verify the details above,
I'll be amazed.
Of course it's possible to state the traditional proof in a way
that uses much less prior knowledge of number theory, but
the proof above still seems much simpler to me.
>Moreover, the other proof allows a simple generalization:
>
> sqrt(p) is irrational for any p prime. (!)
>
>While the proof above breaks down for n > 3
??? Let's see. Suppose that sqrt(43) is irrational. Then
there is a least positive integer k such that k*sqrt(43) is
an integer. Which is impossible because k*sqrt(43) - k
is a smaller such positive integer.
That's exactly the same, and it's correct for exactly
the same reason: 0 < k*sqrt(43) - k < k, and
sqrt(43)*(k*sqrt(43) - k) = 43*k - k*sqrt(43), which
is an integer since k*sqrt(43) is.
>(though it covers sqrt(2)
>and sqrt(3)).
>
>
>F.
******************
David C. Ullrich
David C. Ullrich
wrote:
>On Sun, 18 May 2003 20:30:12 +0200, "fourierr"
Yeah, forget what I said a second ago about how it works
for any prime...
Pete Klimek
>
> fourierr
> --
The proof appears in the Postscript to Chapter 2 of Martin Gardner's book
"Gardner's Workout". However, Gardner doesn't say whose proof it is.
Chapter 2, titled "The Square Root of 2 = 1.414 213 562 373 095 ...",
contains other proofs of the irrationality of sqrt(2), plus citations to 18
relevant articles in periodicals.
Pete Klimek
David C. Ullrich
wrote:
>On Sun, 18 May 2003 19:59:34 +0200, "Denis Feldmann"
I just made a post saying that the proof applies without change to
sqrt(p) for any prime p. That was wrong. Then I made a post saying
never mind. That was wrong as well:
Suppose that sqrt(43) is irrational. Then there is a least positive
integer k such that k*sqrt(43) is an integer. This is a
contradiction, because it implies that k*sqrt(43) - 6*k is a
smaller such integer.
(6 < sqrt(43) < 7 implies that 0 < k*sqrt(43) - 6*k < k.)
Chris Thompson
David C. Ullrich <ull...@math.okstate.edu> wrote:
>On Sun, 18 May 2003 20:34:18 +0200, G. Frege <g.f...@simple-line.de>
>wrote:
>>Moreover, the other proof allows a simple generalization:
>>
>> sqrt(p) is irrational for any p prime. (!)
>>
>>While the proof above breaks down for n > 3
>
>??? Let's see. Suppose that sqrt(43) is irrational. Then
>there is a least positive integer k such that k*sqrt(43) is
>an integer. Which is impossible because k*sqrt(43) - k
>is a smaller such positive integer.
>
>That's exactly the same, and it's correct for exactly
>the same reason: 0 < k*sqrt(43) - k < k, and
>sqrt(43)*(k*sqrt(43) - k) = 43*k - k*sqrt(43), which
>is an integer since k*sqrt(43) is.
k*sqrt(43) - k < k ? I don't think so ...
The proof needs to be adjusted to use k*sqrt(43) - 6*k,
of course. With a similar adjustment, the argument works
for the square root of any non-square integer.
Chris Thompson
Email: cet1 [at] cam.ac.uk
G. Frege
(Rouben Rostamian) wrote:
> >
> > How would you adjust it to prove that sqrt(5) is irrational?
> >
> If sqrt(5) is rational, then there
> exists a smallest positive integer k such that k*sqrt(5)
> is an integer. However, k*sqrt(5) - 2k is a smaller such
> integer, contradiction.
>
Right. This is nice! :-)
F.
G. Frege
<ull...@math.okstate.edu> wrote:
>
> I just made a post saying that the proof applies without change to
> sqrt(p) for any prime p. That was wrong.
>
"Which step was too hard for you...?"
:-)
F.
Bill Dubuque
>
> However, another useful theorem is that rational algebraic integers are
> integers (see http://www.whim.org/nebula/math/ratalint.html). Using
> this theorem, you can note that sqrt(2) is an algebraic integer since it
> satisfies x^2 - 2 = 0 to which there are no integer solutions. Thus,
> sqrt(2) is irrational.
Your theorem is simply the monic special case of the very well-known
RATIONAL ROOT TEST, which I mentioned last time around on this topic:
The Ridge <pmy...@nottingham.ac.uk> wrote on Mar 5, 2000:
: Is there a proof for proving that CubeRoot(2) is irrational? Would it
: go along the same lines as trying to prove that Sqrt(2) is irrational?
Rob Johnson <robj...@idt.net> wrote:
| A more general result that answers all of these sorts of questions
| is that all algebraic integers are either integers or irrational.
| See http://idt.net/~robjohn9/math/ratalint.html for a proof of this.
Les Wright <leslie...@yahoo.com> wrote:
> Run, don't walk, to Rob's link. The proof is brief, elegant, and
> requires only very basic number theory as a prerequisite [...]
The proof is actually much simpler and known since high-school, namely
RATIONAL ROOT TEST If a reduced rational a/b is a root of a poly
with integer coefs P(X) = d X^n + ... + c, then a|c and b|d.
Proof: 0 = b^n P(a/b) = d a^n + b(...) with (...) an integer,
hence b|(d a^n) => b|d via gcd(a,b) = 1 (since a/b is reduced).
a|c follows symmetrically. QED Note: x|y means x divides y
Specializing to the case where the leading coef d = +-1 yields
COROLLARY A rational root of a monic integral poly is an integer.
This specialized to P(X) = X^n - m yields a rationality test
COROLLARY The n'th root of an integer if not integral is irrational.
Take close note how the above proof depends crucially on divisibility
properties of the integers (in particular, employing gcd's). For
generalizations to other domains see some of my prior sci.math posts.
= http://groups.google.com/groups?threadm=y8zln3tyyhq.fsf%40nestle.ai.mit.edu
-Bill Dubuque
G. Frege
<ull...@math.okstate.edu> wrote:
>>
>> [...] one certainly could say that the argument is not really _obvious_
>>
> One could say a lot of things. Which step was too hard for you,
> showing that k*sqrt(2) - k was less than k or showing that
> sqrt(2)*(k*sqrt(k) - k) was an integer? They're both utterly
> straightforward.
>
Look, Ullrich, I didn't say that *I* have a problem with the _argument_
in this proof.
I just wanted to point out that at least 2 regular posters in this NG
DIDN'T immediately get it. (Which is actually rather remarkable, imho.)
Moreover, it s e e m s that even _you_ had a problems with the
argument, which actually might falsify your OWN claim.
Of course you might STILL claim that the argument is "straightforward"
and/or totally "obvious" - despite all evidence to the contrary. Well,
sure, you can do this. It just wouldn't be very reasonable, imho.
F.
Tim Smith
>>Another short proof: If sqrt(2) is rational, then there exists a smallest
>>positive integer k such that k*sqrt(2) is an integer. However, k*sqrt(2) -
>>k is a smaller such integer, contradiction.
>
> By that logic, consider 6/5. 6/5 is rational, therefore there exists a
> smallest positive integer (namely 5) such that 5 * 6/5 is an integer.
> However, (5 * 6/5 - 5) = (6 - 5) = 1, a smaller such integer.
When x satisfies these two properties:
1. x^2 is an integer.
2. 1<x<2
then the clever "kx-k" argument is correct. Without property #1, (kx-k)x is
not necessarily an integer.
Your 6/5 does not satisfy #1. sqrt(2) does. The proof is correct.
--
Evidence Eliminator is worthless: www.evidence-eliminator-sucks.com
--Tim Smith
Martin Cohen
Suppose sqrt(2) = m/n with m and n positive integers.
Then (2n-m)/(m-n) = (2-(m/n))/((m/n)-1)
= (2-sqrt(2))/(sqrt(2)-1)
= sqrt(2)*(sqrt(2)-1)/(sqrt(2)-1)
= sqrt(2).
But this fraction has a smaller denominator then m/n
(since 1 < sqrt(2) < 2).
Continuing this, there is no smallest denominator,
so sqrt(2) is not rational.
The neat thing about this proof, is
(a) that it is equivalent to
the continued fration expansion of sqrt(2),
(b) it was discovered by the Greeks,
and
(c) it can be done entirely geometrically.
We start with the definition that two line segments are
commensurable if there is a a segment that divide both
of them in an integer number of parts. Using the
geometric version of this argument, we show that
if 1 and sqrt(2) are commensurable with a certain segment,
so are (2-sqrt(2)) and (sqrt(2)-1).
Repeating this, we get smanner and smaller segments,
each having ration 1:sqrt(2), which are divisible by
the original common segment. This is a contradiction.
To do the same for an arbitrary integer k requires
the continued fraction for sqrt(k).
IIRC, the Freek mathematician Thales was reported to
have proved that sqrt(k) is irational for integer k
from 2 through 17. If he used this method, he would
have had to come up with a different proof (in the
same style) for each k. No wonder he stopped.
The proof using unique factorization is far more
general, but it uses concepts not in Euclid.
This proof is Euclidean.
A similar distinction can be made regarding the
proof of the Pythagorean theorem in Euclid's
proposition 47. This only uses
(a) the area of a triangle is half the area of a
rectangle with the same base and altitude
(you do not need a formula for the actual area);
(b) common notions of identity.
It does not need algebra, the moving about of areas,
or proportional triangles.
It also shows how to divide the square on the
hypotenuse into two rectangles each with the
area of the neighboring square.
Martin Cohen
Doug Norris
>I just wanted to point out that at least 2 regular posters in this NG
>DIDN'T immediately get it. (Which is actually rather remarkable, imho.)
If you're counting me amongst the two, then so be it, although I had trouble
with the phrasing (vaguenss) of the wording.
Doug
G. Frege
<ull...@math.okstate.edu> wrote:
>
> [...] You posted _this_ as the "short" proof:
>
Assume sqrt(2) = n/m for some n,m e N. Then 2*m^2 = n^2.
But his would contradict the UFT.
( The power of the prime factor 2 occurring in the prime
factorization of the left hand side of the equation
would be _odd_, while it would be _even_ at the right
hand side. )
qed.
Try to get that straight, Ullrich: I said _short_, not _elementary_.
Actually, the _argument_ in this proof is _extremely_ simple. IF you are
familiar with the "The Fundamental Theorem of Arithmetic" (uniqueness of
the prime factorization), of course.
F.
G. Frege
wrote:
>
> >I just wanted to point out that at least 2 regular posters in this NG
> >DIDN'T immediately get it. (Which is actually rather remarkable, imho.)
>
> If you're counting me amongst the two, then so be it, although I had trouble
> with the phrasing (vagueness) of the wording.
>
I see. Yes, the wording was slightly... tricky? (On the other hand, it
doesn't seem to be really "ambiguous" to me. Or am I wrong here?)
F.
Doug Norris
>Your 6/5 does not satisfy #1. sqrt(2) does. The proof is correct.
Here's the problem with Usenet - even several hours after posting a
retraction, I still have to read dozens of people's "you're wrong" posts.
Doug
Doug Norris
Well, now that I know what it's supposed to say, it's not ambiguous
to me either.
Doug
David C. Ullrich
Norris) wrote:
>G. Frege <g.f...@simple-line.de> writes:
>
>>On 18 May 03 20:58:55 GMT, norr...@rintintin.colorado.edu (Doug Norris)
>>wrote:
>
>>> >I just wanted to point out that at least 2 regular posters in this NG
>>> >DIDN'T immediately get it. (Which is actually rather remarkable, imho.)
>>>
>>> If you're counting me amongst the two, then so be it, although I had trouble
>>> with the phrasing (vagueness) of the wording.
>>>
>>I see. Yes, the wording was slightly... tricky? (On the other hand, it
>>doesn't seem to be really "ambiguous" to me. Or am I wrong here?)
>
>Well, now that I know what it's supposed to say, it's not ambiguous
>to me either.
I don't _think_ that there was anything even slightly vague about
the wording. I could be wrong:
I can't figure out more than one way to interpret "If sqrt(2) is
rational, then there exists a smallest positive integer k such
that k*sqrt(2) is an integer. However, k*sqrt(2) - k is a smaller
such integer, contradiction.". What's an incorrect way to read it?
>Doug
******************
David C. Ullrich
David C. Ullrich
wrote:
>On Sun, 18 May 2003 14:37:17 -0500, David C. Ullrich
Right. Here's an even _shorter_ proof:
Thm. Sqrt(2) is irrational.
Pf: There do not exist non-zero integers n and m such that n^2 = 2m^2.
If you're familiar with the fact used in that proof then it's very
simple.
David C. Ullrich
wrote:
>On Sun, 18 May 2003 14:58:39 -0500, David C. Ullrich
In case it's actually not clear, I overlooked the fact that we need
sqrt(2) < 2 to show that k*sqrt(2) - k < k.
In case you missed the rest of the post, the proof _does_ extend,
with minor modifications, to the general result:
Thm: If n is not a perfect square then sqrt(n) is irrational.
Pf: Choose a positive integer a with a^2 < n < (a+1)^2.
Suppose sqrt(n) is rational. Then there exists a least positive
integer k such that k*sqrt(n) is an integer. But k*sqrt(n) - a*k
is a smaller such integer (a < sqrt(n) < a+1 shows that
0 < k*sqrt(n) - a*k < k.) QED.
And that _is_ a much simpler proof than the traditional
proof of the result in this generality (unless we decide
that the "simplicity" of a proof is independent of how
simple prior results used in the proof are, in which case
the notion of how simple a proof is becomes meaningless,
since _any_ theorem then has a one-line proof.)
>:-)
David C. Ullrich
Norris) wrote:
You're wrong about that. (What you mention is _a_ problem with
Usenet, not _the_ problem.)
I've gotten corrections literally _years_ after posting a retraction.
Bill Dubuque
> Porker899 <pork...@aol.com> wrote:
>>
>> Has anyone seen a very short proof that sqrt(2) is irrational?
>
> Another short proof: If sqrt(2) is rational, then there exists
> a smallest positive integer k such that k*sqrt(2) is an integer.
> However k sqrt(2) - k is a smaller such integer, contradiction.
Some respondents expressed doubts about the validity of this proof.
In fact it's a well-known classical descent proof of irrationality.
The proof easily generalizes to show any rational algebraic integer
is an integer, i.e. Z is integrally closed in its quotient field
[as is any UFD by the rational root test, see my prior post here].
Below is an old post of mine that explains such descent proofs as
exploiting the dichotomy: DISCRETE integers vs. DENSE fractions
-----
One of my favorite irrationality proofs is below. It vividly
highlights the importance of the notion of algebraic integer,
and works by contrasting the DISCRETENESS of a ring of integers
versus the DENSENESS of a ring of fractions. I have presented
the proof in a very simple form - high-school algebra suffices.
THEOREM. Let Z := ring of integers. If an integer b in Z has
a rational square root: sqrt(b) = c/d, then c/d is an integer.
PROOF. Suppose, as hypothesized, w = sqrt(b) = c/d is rational.
d is a common denominator for all elts in the ring R = Z[w]
since if r = m + nw in R, m,n in Z, dr = dm + n(dw) is in Z
via dw = c in Z. So R is a subset of Z/d, i.e. every r in R
has form n/d for an integer n. Suppose r = n/d is nonintegral.
We will show this leads to a contradiction and, hence, that
every r in R = Z[w] must be an integer, including w = sqrt(b).
W.l.o.g we may assume 0 < r < 1 by taking the fractional part
of |r|, since this too lies in R and is nonintegral iff r is.
Since r has form n/d and 0 < r < 1, r is a member of the
finite set { 1/d, 2/d,...,(d-1)/d }. If r is the smallest
elt of R in this set then r^2 is an even smaller such elt
since 1 > r > r^2 > 0, contradicting the minimality of r. QED
This proof works for any algebraic *integer*, i.e. a root of
p(w) = w^n + a w^(n-1) + b w^(n-2) + ... + k, a,b,..,k in Z,
using d^(n-1) versus d as a common denominator for Z[w].
It proves any rational algebraic integer is an integer (in Z).
The proof above is simply the special case p(w) = w^2 - b.
Note the subtlety here. The proof depends crucially on the fact
that w is an algebraic *integer*, which implies that the ring
Z[w] = Z<1,w,w^2,..,w^(n-1)> is a finite dim Z-module, i.e.
w^n, w^(n+1),.. are Z-linear combin's of 1, w, w^2,.., w^(n-1)
This needn't be true if w is a root of a poly p(w) whose leading
coef c is not unity since then w^n = -1/c (a w^(n-1) + ... + k)
so that c may intrude as a nontrivial denominator when using this
equation to rewrite w^n, w^(n+1),... after multiplying two elts.
Essentially the proof shows that if R > Z is an ordered ring
extension which adjoins a new finite element then R is dense,
having infinite descending chains 1 > r > r^2 > r^3 > .. > 0
in a nbhd of 0 (hence everywhere by an additive shift), where
r > 0 is the fractional part of any newly adjoined finite elt.
But Z/d is discrete, not dense, hence the contradiction.
Note that I say "finite" above because it is possible to adjoin
infinite elts alone, e.g. consider Z[x] with x infinite, i.e.
polys in a nbhd of positive infinity = +oo, ordered by declaring
p(x) > q(x) iff this holds true eventually for all large x > 0,
i.e. in a nbhd of +oo. This is same as declaring p(x) positive
or negative as is its leading coef (the leading term eventually
dwarfs others as x-> +oo), and p > q <=> p - q > 0, as usual.
This ordered ring extension of Z adjoins no new finite elements.
However, if we additionally adjoin the infinitesimal 1/x then
we have 1 > 1/x > 1/x^2 > ... > 0, and adding c shifts this
infinitely descending chain to the nbhd of any elt c in Z[x,1/x].
Source: http://mathforum.org/epigone/historia_matematica/gosneyah/E15BPeK-...@nestle.ai.mit.edu
-Bill Dubuque
Bill Dubuque
between John Conway and I in my prior posted Historia-Matematica link:
http://mathforum.org/epigone/historia_matematica/gosneyah
Below I excerpt a couple of these messages, which themselves contain
links to other interesting threads discussing this irrational FAQ.
Of particular note is that the descent arises simply from the ancient
*vector* Euclidean algorithm -- which dates back to Euclid's time.
I explain a number of equivalent ways to view this descent below.
--------------------------------------------------------------------------
Subject: Re: [HM] sqrt(2) and reductio
Author: Bill Dubuque <w...@zurich.ai.mit.edu>
Date: Fri, 15 Jun 2001 04:58:29 -0400
John Conway wrote:
> Here's my own simple proof of the fact that if sqrt(N) isn't
> integral, then it isn't rational. Suppose it's a rational A/B;
> then it's equally the rational NB/A, so these two numbers are
> equal, as are their fractional parts, b/B and a/A say, where
> we obviously have 0 < b < B, 0 < a < A. Now sqrt(N) is also
> equal a/b (since it equals A/B), giving a strictly simpler form.
>
> [later] However, you have to remember [the standard proof]. It was
> by consciously thinking about how to express and recall this proof
> that I obtained "my" proof. Namely, the problem to be solved
> is how can one remember the analogs of the expressions t-u, 2u-t
> that appear in the proof for sqrt(N) ? The answer is that they're
> the denominators of the factional parts of t/u and Nu/t (which
> are the same number, so have the same fractional parts!).
> Equating these fractional parts then "codes" the desired descent.
You don't have to remember anything to reproduce the standard proof!
As explained in my prior post (below), applying the vector Euclidean
algorithm derives a smaller vector/fraction and hence achieves descent.
Most descent proofs in this area descend via Euclids algorithm, e.g.
your proof too can be recast as a simple (iterated) application of
the vector Euclidean algorithm. As I show below, taking the remainder
of the vector (a,b) mod (c,d) = (a mod c, b mod d) is essentially
equivalent to taking the fractional parts of a/c and b/d, as we
see as the vector Euclidean algorithm proceeds: (in fraction form)
a c a-c a-2c a-3c a mod c
- = - = --- = ---- = ---- = ... = -------
b d b-d b-2d b-3d b mod d
c a mod c a mod c b mod d
so - = ------- => ------- = -------
d b mod d c d
[ a ] [ b ]
but this simply says [ - ] = [ - ]
[ c ] [ d ]
where [r] denotes the fractional part of r.
Thus taking the fractional parts of two equivalent fractions is
equivalent to mod'ing out a larger vector/fraction by a smaller one,
i.e. a division algorithm step in the vector Euclidean algorithm.
Iterating such steps computes the shortest vector in the lattice line
y = a/b x or, equivalently, the irreducible fraction equivalent to
a/b. For descent proofs we start with the assumption that one such
vector (a,b) is the shortest vector (i.e. a/b is irreducible), then
deduce a contradiction by descending to a smaller vector/fraction by
applying one step of the vector Euclidean algorithm, either in the
slow subtractive form, or accelerated division/mod form (as above).
See my prior post for explicit examples.
It is rather puzzling that this powerful technique of Euclid has
somehow been lost in modern times. Most people who see these "direct"
proofs of irrationality or unique factorization seem to think that
they are magic, having eliminated any use of gcds or division etc. But
as we have seen, in actuality such proofs proceed simply by directly
inlining steps of the vector Euclidean algorithm, so are essentially
no different from more modern proofs that explicitly invoke Euclid's
algorithm or equivalent objects (gcds, ideals, modules, etc). Though
the vector form of Euclid's algorithm is easily accessible to the
novice, unfortunately most will not be exposed to it, unless they go
on to study advanced number theory - where it reappears in modern
form when one studies modules and normal forms (Hermite-Smith), etc.
Reflecting upon the stark contrast between the older techniques
and the streamlined modern techniques, one cannot help but be
amazed at the insight of Dedekind - who invented many of the
basic structures and abstractions around this area. Dedekind's
book "Theory of algebraic integers" has recently been translated
into English by John Stillwell. Read this and almost certainly
you will be impressed with Dedekind's insightfulness in abstracting
out the essential structures and concepts. Although written almost
125 years ago, the textbook still seems thoroughly modern - which
probably cannot be said of many textbooks of this era. Another
good reason to read the English translation is that John Stillwell
has written a superb 43 page introduction that will no doubt lure
many into the rich and tantalizing history of number theory.
--------------------------------------------------------------------------
Subject: Re: [HM] sqrt(2) and reductio
Author: Bill Dubuque <w...@zurich.ai.mit.edu>
Date: Thu, 14 Jun 2001 20:41:27 -0400
David Masunaga <masu...@koa.iolani.honolulu.hi.us> wrote:
>
> MAA's Selected Papers on Precalculus includes two short proofs on the
> irrationality of sqrt(2).
>
> In Robert Gauntt's proof (with Gustave Rabson; AMM, Vol.63(1956), p.247):
>
> "A^2 = 2B^2 cannot have a non-zero solution in integers because the last
> non-zero digit of a square, written in the base three, must be 1, whereas
> the last non-zero digit of twice a square is 2."
It is equivalent, and simpler, to analyze the equation modulo 3. Trivial
case analysis shows A^2 = 2B^2 is solvable mod 3 iff A = B = 0 mod 3.
Substituting A = 3a, B = 3b then yields a descent to a^2 = 3 b^2.
This is just the mod 3 analog of the standard mod 2 (parity) proof which,
being simpler, is usually preferred.
It is now a standard technique to use modular reduction to demonstrate
nonsolvability of Diophantine equations. For certain classes of
equations (most esp. of quadratic form), it is known that nonsolvability
can always be demonstrated in such a way - lookup the Hasse local-global
principle. In particular this implies that such modular irrationality
proofs exist for the square-root of any non-square integer, see
http://groups.google.com/groups?threadm=y8zogx1n6gh.fsf%40nestle.ai.mit.edu
I'm not sure just when such modular techniques started to become
exploited systematically. Fermat certainly made a start here.
For some of the history see Weyl's book Number Theory.
> In the first (from AMM, Vol.62(1955),p.437) Edwin Halfar says he does
> not use the usual assumption that the fraction n/m represents sqrt(2)
> such that n and m have no common factors:
>
> "Suppose sqrt(2)=(n/m), where n amd m are positive integers. Then n>m,
> and there is an integer p>0 such that n=m+p, and 2m^2 = m^2 + 2pm + p^2.
> This implies m>p. Consequently, for some integer a>0, m = p+a, n = 2p+a
> and 2(p+a)^2 = (2p+a)^2. The last equality implies a^2 = 2p^2 so that
> the entire process may be repeated indefinitely giving n>m>a>p..., but
> since every non-null set of positive integers has a smallest element,
> this is a contradiction and sqrt(2) is irrational."
This is simply a rewording of the well-known ancient descent proof
w = sqrt(2), w = n/m => w = 2m/n => w = (2m-n)/(n-m) [= a/p above]
see http://groups.google.com/groups?selm=y8zogrqm5f2.fsf%40berne.ai.mit.edu
In essence this really *does* utilize the Euclidean algorithm.
It employs the basic reduction step of vector subtraction when
computing the greatest common measure of two integral vectors:
(2m,n), (n,m) -> (2m,n) - (n,m) = (2m-n,n-m)
Proofs proceed either by descent to a shorter vector, as above,
or by assuming (n,m) the shortest vector in the lattice, then
(2m,n) must be an integer multiple of (n,m), say (2m,n) = (kn,km),
so n = km => sqrt(2) = n/m = k is an integer, contradiction.
*Precisely* the same descent yields the greatest common measure,
so, instead of invoking this concept, the proof has merely unrolled
or inlined the use of the Euclidean algorithm.
This has an equivalent reformulation in terms of fractions.
Fractions equivalent to a/b lie on the lattice line y = a/b x.
(n,m) is a shortest vector iff n/m is an irreducible fraction.
Every vector (y,x) on the line is an integer multiple of the
shortest vector: (y,x) = k(m,n) = (km,kn). In fraction-speak,
every equivalent fraction has form km/kn. This implies the
(essential) Uniqueness of Irreducible Fractions:
y n y kn y|n
gcd(n,m)=1 => - = - <=> - = -- => some integer k
x m x km x|m
The vector gcd algorithm not only proves this, but it gives
an algorithm to find the irreducible fraction corresponding
to two equivalent fractions, namely, continually subtract
the shorter from the longer (or speed it up using remainders).
The equivalent fraction-speak irrationality proof is thus:
If sqrt(2) is rational, say w = sqrt(2) = n/m irreducible,
then w^2 = 2 => n/m = 2m/n, so m|n by fraction uniqueness,
(i,e. the denominator of n/m divides the denominator of 2m/n)
so sqrt(2) = w = n/m is an integer, contradiction.
Uniqueness of fractions is essentially equivalent to unique
factorization since it easily yields Euclid's Lemma, namely
gcd(c,a)=1, c|ab => c|b, just look at a/c = d/b. Almost
all results in this area can be reformulated in fraction
form, e.g. Zermelo's direct proof of unique factorization,
or, more generally, in the language or modules, ideals, etc.
In modern language one is just computing in certain Z-modules, or PIDs,
or Bezout rings, using twists on the division or Euclidean algorithm,
say Hermite-Smith reduction, etc. The older "direct" proofs have gone
out of fashion because the newer algebraic concepts such as ideals,
modules, etc. provide more powerful techniques allowing one to abstract
away these messy inductions once and for all. For example, above the
set X of denominators x of all fractions y/x equivalent to a/b is an
ideal, i.e. if b,d in X then so is m b + n d in X for all integers
m,n, since if by = ax, dy = cx, then multiplying by m,n and adding
yields (mb+nd)y = (ma+nc)x. But every ideal in Z is principle, being
generated by its smallest member, obtainable by the Euclidean algorithm.
With this general result proved, all we need do is note that certain
sets are ideals, instead of inlining into every proof applications of
the division/euclidean algorithm, or descent, etc; see also this post
http://groups.google.com/groups?selm=y8zy91ndxs2.fsf%40nestle.ai.mit.edu
the power of modern structural techniques, they encapsulate useful
concepts and procedures once and for all so they can easily be reused
and efficiently applied whenever the relevant structures are recognized.
Thus one sees these "direct inlined" proofs in older texts (but not in
newer texts) because the more efficient modern ideas had not yet been
invented. Nowadays one simply remarks that a certain object has a
known structure (e.g. an ideal or module) and immediately resuses all
known results on such structures, instead of redeveloping them every
time they are needed - perhaps not even noticing the common structure.
The history of the evolution of related concepts and structures is very
fascinating and very complex. Even some of the most fundamental ideas
and structures still have not yet received a definitive treatment in
the literature, e.g. the evolution of the notion of algebraic integer,
unique factorization, integral closure, ideals, modules, orders, etc.
Hopefully some mathematical historians will soon rise to the challenge!
-Bill Dubuque
Doug Norris
>I can't figure out more than one way to interpret "If sqrt(2) is
>rational, then there exists a smallest positive integer k such
>that k*sqrt(2) is an integer. However, k*sqrt(2) - k is a smaller
>such integer, contradiction.". What's an incorrect way to read it?
Would it help if I'd mentioned that I had been up all night studing for
an actuarial exam? :-)
Doug
Doug Norris
>I've gotten corrections literally _years_ after posting a retraction.
That just means that I've got something to look forward to. :-)
Doug
G. Frege
<ull...@math.okstate.edu> wrote:
>
> Thm. Sqrt(2) is irrational.
> Pf: There do not exist non-zero integers n and m such that n^2 = 2m^2.
>
> If you're familiar with the fact used in that proof then it's very
> simple.
Fool.
G. Frege
wrote:
>
> "[...] one certainly could say that the argument is not really
> _obvious_ in this proof."
>
G. Frege
<ull...@math.okstate.edu> wrote:
> >
> > "Which step was too hard for you...?"
>
> In case it's actually not clear, I overlooked <bla and bla>
>
Well, probably you are just to dense to get that straight, I claimed:
"[...] one certainly could say that the argument is not really
in this proof."
Of course you well tell me now that you weren't wrong, but <bla bla>.
:-)
It's a simple fact that it was not OBVIOUS (at least to some of us) why
the argument is valid.
F.
Doug Norris
>Fool.
Signing your name as "Fool." isn't going to make us think that you're
any smarter.
Doug
G. Frege
wrote:
>
> Signing your name as "Fool." isn't going to make us think that you're
> any smarter.
>
> Doug
>
Oh, how clever you are! (Aren't you the guy who could not even get that
simple argument right? Like the other fool?)
F.
G. Frege
<ull...@math.okstate.edu> wrote:
>
> Thm: If n is not a perfect square then sqrt(n) is irrational.
>
> Pf: Choose a positive integer a with a^2 < n < (a+1)^2.
> Suppose sqrt(n) is rational. Then there exists a least positive
> integer k such that k*sqrt(n) is an integer. But k*sqrt(n) - a*k
> is a smaller such integer (a < sqrt(n) < a+1 shows that
> 0 < k*sqrt(n) - a*k < k.) QED.
>
> And that _is_ a much simpler proof than the traditional
> proof of the result in this generality (...)
>
Right.
Now my proof would be (accordingly):
Assume sqrt(n) is rational. Hence there are p,q e N with sqrt(n) = p/q.
And hence n*p^2 = q^2. By the UFT we *SEE* that all powers of the primes
in the factorization of n must be even. Hence n is a perfect square.
qed.
F.
Btw, the other proof for the irrationality of sqrt(2) was presented to
me (us) when I was a student by a guy with Erdös number 2. And _HE_
thought that this was a rather beautiful (and elegant) approach.
Doug Norris
>Oh, how clever you are! (Aren't you the guy who could not even get that
>simple argument right? Like the other fool?)
Look - you're rude, boorish, and as far as I can tell, contribute nothing
to this newsgroup. You may have the last word, as I'm done with you.
Plonk,
Doug
F. Fritsche
wrote:
>
> [...] You may have the last word, as I'm done with you.
>
> Plonk,
>
That's just fine for me. Thanx.
F.
David C. Ullrich
Norris) wrote:
If that means that now that you've got some rest you no longer
see anything vague or ambiguous about the statement then yes.
David C. Ullrich
wrote:
>On Mon, 19 May 2003 07:43:47 -0500, David C. Ullrich
Presumably by the "other" proof you mean the one using UFT.
What's your point? Nobody has said that it's _not_ a beautiful
and elegant approach. This has nothing to do with the fact
that the one that not everyone's seen before is simpler.
>Some info:
>http://www.acs.oakland.edu/~grossman/erdoshp.html
******************
David C. Ullrich
Doug Norris
>On 19 May 03 16:50:48 GMT, norr...@rintintin.colorado.edu (Doug
>Norris) wrote:
>If that means that now that you've got some rest you no longer
>see anything vague or ambiguous about the statement then yes.
Upon further reading, I see no real ambiguity in the proof.
Doug
Rouben Rostamian
Doug Norris <norr...@rintintin.colorado.edu> wrote:
>
>Upon further reading, I see no real ambiguity in the proof.
The ambiguity must be complex then.
--
Rouben Rostamian <rost...@umbc.edu>