Math Is Fun Forum

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

You are not logged in.

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

Leroy
Guest

Equation

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

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Equation

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.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

zetafunc.
Guest

Re: Equation

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

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

Leroy
Guest

Re: Equation

I need integer value for both x and y

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Equation

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.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

zetafunc.
Guest

Re: Equation

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?

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Equation

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.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

zetafunc.
Guest

Re: Equation

How do you get the fundamental solution via continued fractions?

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Equation

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.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

zetafunc.
Guest

Re: Equation

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

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Equation

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.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

zetafunc.
Guest

Re: Equation

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?

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Equation

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.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

zetafunc.
Guest

Re: Equation

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, ...}?

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Equation

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.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

zetafunc.
Guest

Re: Equation

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

?

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

zetafunc.
Guest

Re: Equation

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

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

zetafunc.
Guest

Re: Equation

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

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

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Equation

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.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

zetafunc.
Guest

Re: Equation

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

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Equation

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.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

zetafunc.
Guest

Re: Equation

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

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Equation

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.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

zetafunc.
Guest

Re: Equation

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

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Equation

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.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

Board footer

Powered by FluxBB