Results 1 to 12 of 12

Math Help - Pell equation (pigeonhole argument)

  1. #1
    Newbie
    Joined
    Mar 2007
    Posts
    21

    Pell equation (pigeonhole argument)

    I am doing a presentation over the pell equation and specifically the pigeonhole argument....I am getting hung up on proving Dirichlet's approximation theorem...my professor wrote out the proof for me and I am not following the way he did it..everyone is so good about explaining stuff on this forum I figured I would post and hope someone knows how to do this..

    Dirichlet's approximation theorem:
    for any irrational sqrt(n) and integer B>0 there are integers a, b with
    0<b<B and
    | a - b(sqrt(n)) | < 1/B

    Hopefully the proof of whoever helps will be alot clearer than my professors
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Here is a stronger version.
    Note: This is what made the Pigeonhole Principle famous.

    This is a hard proof because there is much going on. I will not mention each detail which needs to be mentioned because I do not have enough space. See if you figure it out from there.

    It is interesting that the existence of solutions to the Pellian equation depends on diophantine approximation. Both the classic version by Euler/Lagrange, and the more modern version by Dirichlet. I happen to like the Euler/Lagrange approach more because they actually provide an algorithm with continued fractions. Unlike, Dirichlet, who just provides existence. But anyway, both proofs are complicated if you happen to learn them.
    Attached Thumbnails Attached Thumbnails Pell equation (pigeonhole argument)-picture2.gif  
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2007
    Posts
    21
    You do such a better job than my professor at explaining things, and I cannot even talk to you, kinda sad, lol.........I do have one more thing for that portion of the proof.......
    okay, so you gave me the proof, I am confused what the purpose of the approximation is used for? I mean the equation is x^2 -ny^2 = 1.......so im doing the pigeon hole which is meaning that for the equation I listed above, it is not always to find say an answer were n=61
    What is the approximation used for, im confused with that.

    Also, could you give an example using this approximation. So I can give a few others on the class presentation.....I do have a question with proving the indeterminate version of this also, but lets go step by step....so giving the example on the approximation would help the most right now

    P.S. Are you a professor somewere?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Mar 2007
    Posts
    21
    Also, it doesnt matter if its qx -p or q-px because the equation I have is a-bx?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by learn18 View Post
    I am confused what the purpose of the approximation is used for?
    Okay, this is from an area of mathematics called "diophantine approximation". That is, we approximate (find inequalities and upper/lower bounds) in terms of integers. Why do we do this. We can sometime show that if a certain diophantine equation can be approximated well enough with certain integers then we can conclude sometime about those integers. For example, say we want to show the Pellian equation has at least one solution: we can show that there are infinitely many integers which satisfy some approximation and conclude, by some theorem (which can be complicated) that they must satisfy the diophantine equation. That is the idea that Dirichlet, I think, uses in his proof.

    Also, could you give an example using this approximation.
    Not now. Later on when I have more time I can. (I accidently unleashed a trojan on my computer, now I need to fix it. And am using a different computer. Do not worry, I am an expert with trojans it should not take so long to stop the infection).

    P.S. Are you a professor somewere?
    I am not a professor. I am a fashion designer.

    Also, it doesnt matter if its qx -p or q-px because the equation I have is a-bx?
    No, I just use different charachers to represent integers.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Mar 2007
    Posts
    21
    Your really good a mathematics exp being a fashion person.....Thanks for your help, I have another proof I will post for us to figure out once I see how the examples work....take your time, your computer comes first
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    It seems I fixed the problem.

    Let x=pi.

    Choose n=10

    And we want to find integers p,q such that,

    |qx-p|<1/10

    That is,

    |pi*q-p|<1/10 with the condition 1<=q<=10

    Can we find such p and q.

    Yes!

    Chose q=7 and p=22 then we have,

    |pi*q-p|=|pi*7-22|=|21.99.... - 22|= .0088... <1/10

    Those numbers, if you paid attention, where not just abitrary. There is a special reason why those appears. I am sure you know that 22/7 is a good approximation for pi. Thus, as a fraction 22/7=p/q with p=22 and q=7 is some of the reasoning behind this.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Mar 2007
    Posts
    21
    Congrats on fixing your computer!!
    So how would the way you used the formula with the steps towards application in the infinite pigeonhole principle:
    here are the steps I have for the equation | a - b(sqrt(n)) |< 1/B....so how would these steps being using your formula?
    1) Since Dirichlet's approximation theorem holds for all B > 0, we can make 1/B arbitarily small, thus forcing the choice of new values a and b. Thus there are infinitely many integer pairs (a,b) with | a - b(sqrt(n)) |. Since 0<b<B we have
    | a - b(sqrt(n)) | < 1/b
    2) It follows from step 1 that
    | a + b(sqrt(n)) | <= | a - b(sqrt(n)) | + | 2b(sqrt(n)) | <= | 3b(sqrt(n)) |,
    and therefore
    | a^2 - nb^2 | <= 1/b * 3b(sqrt(n)) = 3(sqrt(n))
    Hence there are infinitely many a - b(sqrt(b)) is an element of Z[sqrt(n)] with norm of size <= 3(sqrt(n))

    3) By the infinite pigeonhole principle we obtain in turn
    - infinitely many a - b(sqrt(n)) with the same norm, N say,
    - infinitely many of these with a in the same congruence class, mod N,
    - infinitely many of these with b in the same congruence class, mod N
    4) From step 3 we get two positive numbers, a1 - b1(sqrt(n) and a2 - b2(sqrt(n)), with
    - the same norm N,
    - a1 = a2(mod N),
    - b1 = b2(modN)


    The final step uses the quotient a - b(sqrt(n)) of the two numbers just found. Its norm a^2 - n(b^2) is clearly 1 by the multiplicative property norm. It is not so clear that a and b are integers, but this now follows from the congruence conditions in step 4
    How do I do this step, step 5?
    Okay, then I have the proof of the nontrivial solution, but lets look at these five steps and see how they change to your formula first.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Mar 2007
    Posts
    21
    I guess I really wouldnt even need these steps with your version of the proof?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,184
    Thanks
    403
    Awards
    1
    Quote Originally Posted by ThePerfectHacker View Post
    I accidently unleashed a trojan on my computer, now I need to fix it. And am using a different computer. Do not worry, I am an expert with trojans it should not take so long to stop the infection).
    Hmmm....

    If you are having problems with Trojans and infection perhaps you should consider another method of birth control.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by topsquark View Post
    If you are having problems with Trojans and infection perhaps you should consider another method of birth control.
    I am already married.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Newbie
    Joined
    Mar 2007
    Posts
    21
    I figured I would put down the second form of the proof...was waiting on your computer to get up to speed but looks like it may be


    Nontrivial solution of the pell equation: When n is a non square positive integer, the equation x^2 - n(y^2) = 1
    (a,b) cannot equal (+ or - 1, 0)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Pell's equation
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: April 25th 2010, 06:22 PM
  2. Question to Pell Equation
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: April 2nd 2010, 07:45 PM
  3. Pell's equation
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: June 4th 2009, 07:32 AM
  4. simple Pell's Equation
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: May 3rd 2009, 09:42 PM
  5. Pell equation
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 10th 2008, 01:00 PM

Search Tags


/mathhelpforum @mathhelpforum