Discussion about math, puzzles, games and fun. Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ π -¹ ² ³ °

You are not logged in.

- Topics: Active | Unanswered

**Leroy****Guest**

Could you please help me solve- x^2-11y^2=1?

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 105,657

HI Leroy;

You want to solve it for x? Solve it for y? What?

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.****No great discovery was ever made without a bold guess. **

Offline

**zetafunc.****Guest**

Do you mean integer solutions? It may help if you consider that equation mod 11...

**Leroy****Guest**

I need integer value for both x and y

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 105,657

Hi Leroy;

Could you please help me solve- x^2-11y^2=1?

If this is your equation

then there are no integer solutions.

If that - sign in front of the x^2 does not belong there then you are dealing with a Pell equation. This will require continued fractions to understand.

Three solutions are (1,0),(10,3) and (199,60).

There are infinitely more.

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.****No great discovery was ever made without a bold guess. **

Offline

**zetafunc.****Guest**

How did you find those solutions? I have seen a continued fraction before (such as one for the golden ratio) but how do you use them to find solutions to a Pell equation like Leroy's?

I know x = 1 and y = 0 will solve any Pell equation, but how do I go about finding more integer solutions by hand?

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 105,657

Hi zetafunc.;

The process of getting the first non trivial solution ( fundamental solution )does involve continued fractions. But I was able to get the next solution called the fundamental solution by trial and error. After that it is a simple means to get as many solutions as you like.

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.****No great discovery was ever made without a bold guess. **

Offline

**zetafunc.****Guest**

How do you get the fundamental solution via continued fractions?

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 105,657

Hi;

Please hold on it is lengthy. I will post it right here.

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.****No great discovery was ever made without a bold guess. **

Offline

**zetafunc.****Guest**

Thank you. Sorry if it is very long, I am very interested though.

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 105,657

First compute the continued fraction of

The sequence is periodic with length 2 (6,3...) The nice part is that a theorem by

Lagrange assures us that every square root like this will always have a repeating

form.

Then you get the convergents:

You pick the 2nd one ( because the period is 2 ) in the sequence 10/3 and check it in the equation with x = 10 and y = 3

so that is the fundamental solution. x = 10 and y = 3. From there you use two recurrences to get as many as you need.

I know you have many questions. This is the prettiest part of number theory. Computational Number Theory!

You might want to look at other problems I worked on:

http://www.mathisfunforum.com/viewtopic … 12#p115912

post#3.

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.****No great discovery was ever made without a bold guess. **

Offline

**zetafunc.****Guest**

Thanks for the post.

How do you know that the continued fraction of the square root of 11 = {3, 3, 6, 3, 6, 3 ...}? How do we know there are 3s and 6s involved?

I understand where you got the convergents from (from the above sequence), but I just need help understanding why you know you have the set {3, 3, 6, 3, 6, 3, ...}.

This looks very neat... so, you are generating all the convergences, and then taking every nth convergent (where n is the cycle length). Is the cycle length always 2 for square roots?

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 105,657

See this link and you will know more.

http://www.mathisfunforum.com/viewtopic … 12#p115912

Post #3.

This is one of my favorite posts!

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.****No great discovery was ever made without a bold guess. **

Offline

**zetafunc.****Guest**

I read that post, but I am not understanding how you got the sets of repeating forms for √11, √14, √61, etc... sorry if I am missing something obvious.

Why is the repeating form for √11 = {3, 3, 6, 3, 6, 3, 6, 3, ...}?

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 105,657

Hi;

Each part of the solution can be easily computed. Hold on I will provide the answer.

The most naive algorithm is also the simplest.

Start with:

Repeat steps 2 and 3.

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.****No great discovery was ever made without a bold guess. **

Offline

**zetafunc.****Guest**

That looks quite easy... but, I am stuck. How do I find

?**zetafunc.****Guest**

Oh, I guess I could just rationalise the denominator...

**zetafunc.****Guest**

But, how can I convince myself that my answer is correct for

? I can see this will get very complicated with further iterations...**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 105,657

c = floor(√11) = 3 ( number you hold )

Now repeat.

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.****No great discovery was ever made without a bold guess. **

Offline

**zetafunc.****Guest**

I mean, if I am computing all of this by hand.

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 105,657

Hi;

You are using a calculator of course. Better if you are using a CAS.

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.****No great discovery was ever made without a bold guess. **

Offline

**zetafunc.****Guest**

But can the repeating form be found using only pen and paper?

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 105,657

For the simple one like √11 maybe. But working with symbolic radicals is even harder than working with

floating point arithmetic. What is the period is 100 or so?

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.****No great discovery was ever made without a bold guess. **

Offline

**zetafunc.****Guest**

How does the length of the period vary depending on the number?

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 105,657

For √14 there is an easy theorem to tell you what the fundamental solution is.

For √11 it does not apply. Generally the bigger the number the longer the period.

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.****No great discovery was ever made without a bold guess. **

Offline