# Thread: Pell equation (pigeonhole argument)

1. ## 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

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

3. 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?

4. Also, it doesnt matter if its qx -p or q-px because the equation I have is a-bx?

5. Originally Posted by learn18
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.

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

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

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

9. I guess I really wouldnt even need these steps with your version of the proof?

10. Originally Posted by ThePerfectHacker
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

11. Originally Posted by topsquark
If you are having problems with Trojans and infection perhaps you should consider another method of birth control.
I am already married.

12. 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)