Results 1 to 6 of 6

Math Help - Simple proof for the infinitude of surds

  1. #1
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3

    Simple proof for the infinitude of surds

    I am teaching a student proofs this semester. I came across a problem in the text that I cannot think of a simple solution for.

    It is in the chapter on "Proof by Contradiction" (the text we are using, for those who are interested, is "Mathematical Proofs: A transition to advanced Mathematics" by Chartrand).

    Anyway, here is the problem and here is my proof, which I am pretty sure is valid.

    Result: Prove that there are infinitely many positive integers n such that \sqrt{n} is irrational.

    I will use the fact that if an integer is a perfect square, then it is equivalent to 0 mod 4 or 1 mod 4, as a lemma. (I would prove this separately, or better yet, ask the student to prove it.)

    Proof:

    Assume, to the contrary, that there are only finitely many integers n such that \sqrt{n} is irrational. Then, there is a largest such integer, call it x. By the above lemma, we have that x \equiv 2 ~(\text{mod }4) or x \equiv 3~( \text{mod }4). Say the former, then that means x + 4 \equiv 2 ~(\text{mod }4) also, and so \sqrt{x + 4} is irrational as well, since x + 4 is not a perfect square. But x + 4 > x, and so we have found a larger integer than our largest, a contradiction. Assuming x \equiv 3 ~(\text{mod }4) yields a similar contradiction.

    QED

    So here's the thing: I know it's a famous result, but the book has not mentioned the lemma I used. And it is not something I think a person who is a beginner when it comes to proofs (and is also a novice when it comes to set theory and number theory) can come up with. I can't really think of any simple ways to prove it though. Do you guys know any easier way?

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    This is what Euclid would do. Say there are finitely many of them: a_1,...,a_N. So that \sqrt{a_j} is rational. Then a=a_1...a_N has property that \sqrt{a} is rational. However, a\not \in \{a_1,...,a_N\} because a>a_j. A contradiction!
    Follow Math Help Forum on Facebook and Google+

  3. #3
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by ThePerfectHacker View Post
    This is what Euclid would do. Say there are finitely many of them: a_1,...,a_N. So that \sqrt{a_j} is rational. Then a=a_1...a_N has property that \sqrt{a} is rational. However, a\not \in \{a_1,...,a_N\} because a>a_j. A contradiction!
    Yes, that proof does have a Euclid feel to it.

    do you think that's something that a 308 student should be able to come up with?

    by the way, what is a_j here. and did you mean to say "irrational" when you said "rational"?

    Thanks.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    Quote Originally Posted by ThePerfectHacker View Post
    This is what Euclid would do. Say there are finitely many of them: a_1,...,a_N. So that \sqrt{a_j} is rational. Then a=a_1...a_N has property that \sqrt{a} is rational. However, a\not \in \{a_1,...,a_N\} because a>a_j. A contradiction!
    Quote Originally Posted by Jhevon View Post
    by the way, what is a_j here. and did you mean to say "irrational" when you said "rational"?
    Yes, it should be "irrational", and that causes the proof to fail: \sqrt{2} and 2\sqrt{2} are distinct irrational numbers, yet their product is not.

    In order to prove the theorem, I would give an easy and well-worth knowing proof that \sqrt{2} is irrational, and then say that n\sqrt{2}=\sqrt{n^22} is irrational for all n (otherwise, \sqrt{2} would be rational). This is a constructive proof, which perhaps is not what you want, but after all the fact that \sqrt{2} is irrational is a must-know one (both historically and since proof is elementary).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by Laurent View Post
    Yes, it should be "irrational", and that causes the proof to fail: \sqrt{2} and 2\sqrt{2} are distinct irrational numbers, yet their product is not.

    In order to prove the theorem, I would give an easy and well-worth knowing proof that \sqrt{2} is irrational, and then say that n\sqrt{2}=\sqrt{n^22} is irrational for all n (otherwise, \sqrt{2} would be rational). This is a constructive proof, which perhaps is not what you want, but after all the fact that \sqrt{2} is irrational is a must-know one (both historically and since proof is elementary).
    Ah, thanks. that is a nice way.

    whether the proof is constructive or not doesn't matter to me. as long as it is a simple one that a beginner can understand. if anything, i can offer hints along with the question so the student knows what direction i want them to think in
    Follow Math Help Forum on Facebook and Google+

  6. #6
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by ThePerfectHacker View Post
    ...Then a=a_1...a_N has property that \sqrt{a} is irrational....
    in light of what Laurent said (it had occured to me when i read the proof at first) how does this follow? since if \sqrt{x} is irrational and \sqrt{y} is irrational, it does not imply that \sqrt{xy} is irrational.

    i am thinking of doing a combination of the proofs you and Laurent posted, but that might be too complicated. a constructive proof is perhaps best for the level this student is at. i will be asking them to prove \sqrt{2} is irrational--it's a famous result, i have to make sure they can do it--so maybe using that somehow would be good.


    EDIT: Ah, it seems TPH's proof was about rational square roots, not irrational ones.
    Last edited by Jhevon; March 8th 2009 at 05:53 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Simple proof
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: September 5th 2010, 07:30 PM
  2. Simple surds question I can't work out!!
    Posted in the Algebra Forum
    Replies: 1
    Last Post: May 4th 2010, 03:22 AM
  3. simple proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 17th 2008, 04:15 PM
  4. Rearranging Surds / Proof
    Posted in the Algebra Forum
    Replies: 21
    Last Post: February 12th 2008, 05:12 PM
  5. Complexity based proof of infinitude of Primes
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: February 10th 2007, 01:29 PM

Search Tags


/mathhelpforum @mathhelpforum