Equation

Leroy · 2012-10-14 18:41:27

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

bobbym · 2012-10-14 19:08:42

HI Leroy;

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

zetafunc. · 2012-10-14 19:13:01

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

Leroy · 2012-10-14 20:32:49

I need integer value for both x and y

bobbym · 2012-10-15 01:05:35

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.

zetafunc. · 2012-10-17 22:14:16

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 · 2012-10-17 22:26:14

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.

zetafunc. · 2012-10-17 22:33:24

How do you get the fundamental solution via continued fractions?

bobbym · 2012-10-17 22:36:52

Hi;

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

zetafunc. · 2012-10-17 22:38:32

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

bobbym · 2012-10-17 22:44:33

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.

zetafunc. · 2012-10-17 23:02:35

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 · 2012-10-17 23:05:02

See this link and you will know more.

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

Post #3.

This is one of my favorite posts!

zetafunc. · 2012-10-17 23:08:32

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 · 2012-10-17 23:10:09

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.

zetafunc. · 2012-10-17 23:40:19

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

?

zetafunc. · 2012-10-17 23:41:35

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

zetafunc. · 2012-10-17 23:43:56

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

? I can see this will get very complicated with further iterations...

bobbym · 2012-10-17 23:52:46

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

Now repeat.

zetafunc. · 2012-10-18 00:07:25

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

bobbym · 2012-10-18 00:09:01

Hi;

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

zetafunc. · 2012-10-18 00:13:51

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

bobbym · 2012-10-18 00:16:53

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?

zetafunc. · 2012-10-18 00:17:41

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

bobbym · 2012-10-18 00:20:45

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.

Math Is Fun Forum

#1 2012-10-14 18:41:27

Equation

#2 2012-10-14 19:08:42

Re: Equation

#3 2012-10-14 19:13:01

Re: Equation

#4 2012-10-14 20:32:49

Re: Equation

#5 2012-10-15 01:05:35

Re: Equation

#6 2012-10-17 22:14:16

Re: Equation

#7 2012-10-17 22:26:14

Re: Equation

#8 2012-10-17 22:33:24

Re: Equation

#9 2012-10-17 22:36:52

Re: Equation

#10 2012-10-17 22:38:32

Re: Equation

#11 2012-10-17 22:44:33

Re: Equation

#12 2012-10-17 23:02:35

Re: Equation

#13 2012-10-17 23:05:02

Re: Equation

#14 2012-10-17 23:08:32

Re: Equation

#15 2012-10-17 23:10:09

Re: Equation

#16 2012-10-17 23:40:19

Re: Equation

#17 2012-10-17 23:41:35

Re: Equation

#18 2012-10-17 23:43:56

Re: Equation

#19 2012-10-17 23:52:46

Re: Equation

#20 2012-10-18 00:07:25

Re: Equation

#21 2012-10-18 00:09:01

Re: Equation

#22 2012-10-18 00:13:51

Re: Equation

#23 2012-10-18 00:16:53

Re: Equation

#24 2012-10-18 00:17:41

Re: Equation

#25 2012-10-18 00:20:45

Re: Equation

Board footer