Pell type equations

[Terry M]

Hi,

5x^2 + 20 = y^2

I can get valid integer values for x and y using brute force (1, 5), (4,
10), (11, 25) etc.

I've been going through the work on this page...

http://www-history.mcs.st-andrews.ac.uk/HistTopics/Pell.html

which covers the work of Brahmagupta and Bhaskara II on Pell type equations.
I can't seem to figure if this is any use for calculating integer roots for
the above equation.

Any help would be greatly appreciated.

[bert]

On Thursday, April 26, 2012 7:12:23 PM UTC+1, Terry M wrote:
> Hi,
>
> 5x^2 + 20 = y^2

That's not the so-called Pell equation.

The usual form of your equation would be
y^2 - Ax^2 = M

First solve z^2 = A mod M, which is pretty elementary
for prime M, otherwise solve it for each prime factor
of M and combine by the Chinese Remainder Theorem.
Composite M will provide multiple solutions z.

Then expand M/z as a continued fraction to obtain
p^2 - Aq^2 = k.M for progressively smaller k to
the middle of the expansion then larger to the end.
However, there is (I think) no guarantee that there
will be any convergent which gives k = 1. I shall
be watching to see if I am wrong about that.
--

[Terry M]

"bert" <bert.hu...@btinternet.com> wrote in message
news:10715757.1501.1335467345792.JavaMail.geo-discussion-forums@vbqq1...

> On Thursday, April 26, 2012 7:12:23 PM UTC+1, Terry M wrote:
>> Hi,
>>
>> 5x^2 + 20 = y^2
>
> That's not the so-called Pell equation.
>
> The usual form of your equation would be
> y^2 - Ax^2 = M
>

Hi,

Thanks for the reply.
The reason I was looking at the Pell related info was this part of the
mentioned page

103x^2 + 1 = y^2.
Choosing a = 1, b = 10 Narayana obtains
*** 103×1^2 - 3 = 10^2.
Choose m so that m + 10 is divisible by -3 with m^2 - 103 as
small as possible leads to m = 11 and we obtain
103×7^2 - 6 = 71^2.
Next we must choose m so that 7m + 71 is divisible by -6 and
m^2 - 103 as small as possible. Take m = 7 to get the equation
103×20^2 + 9 = 203^2.

Since the last 3 of these equations aren't Pell, I thought I may be able to
'plug' my equation in at *** and continue from there.

> First solve z^2 = A mod M, which is pretty elementary
> for prime M, otherwise solve it for each prime factor
> of M and combine by the Chinese Remainder Theorem.
> Composite M will provide multiple solutions z.
>
> Then expand M/z as a continued fraction to obtain
> p^2 - Aq^2 = k.M for progressively smaller k to
> the middle of the expansion then larger to the end.
> However, there is (I think) no guarantee that there
> will be any convergent which gives k = 1. I shall
> be watching to see if I am wrong about that.
> --

I'll give the above a try and see where I get.

Thanks again

[amzoti]

http://www.wolframalpha.com/input/?i=integer+solutions+5x%5E2+%2B+20+%3D+y%5E2+

[Timothy Murphy]

Terry M wrote:

> 5x^2 + 20 = y^2

It is clear that 5 | y.
Writing y = 5z,

x^2 - 5z^2 = -4.

This has the trivial solution (x,z) = (1,1).
We can write this as

(1 + sqrt5)(1 - sqrt5) = -4,
or
e e* = -1,
where
e = (1 + sqrt5)/2, e* = (1 - sqrt5)/2.

It follows that

e^2 (e^2)* = 1.
with
e^2 = (3 + sqrt5)/2.

It follows from the theory of Pell's equation,
or the theory of units in Q(sqrt5),
that the general solution of the given equation is (x,z), where

(x + sqrt5 z)/2 = e^n

where n is an odd integer (positive or negative).

[See eg Hardy & Wright, Introduction to Number Theory]

--
Timothy Murphy
e-mail: gayleard /at/ eircom.net
tel: +353-86-2336090, +353-1-2842366
s-mail: School of Mathematics, Trinity College Dublin

[Terry M]

Hi

"Timothy Murphy" <gayl...@eircom.net> wrote in message
news:jncoab$5cd$1...@dont-email.me...

> Terry M wrote:
>
>> 5x^2 + 20 = y^2
>
> It is clear that 5 | y.
> Writing y = 5z,
>
> x^2 - 5z^2 = -4.
>
> This has the trivial solution (x,z) = (1,1).
> We can write this as
>
> (1 + sqrt5)(1 - sqrt5) = -4,
> or
> e e* = -1,
> where
> e = (1 + sqrt5)/2, e* = (1 - sqrt5)/2.
>
> It follows that
>
> e^2 (e^2)* = 1.
> with
> e^2 = (3 + sqrt5)/2.
>
> It follows from the theory of Pell's equation,
> or the theory of units in Q(sqrt5),
> that the general solution of the given equation is (x,z), where
>
> (x + sqrt5 z)/2 = e^n
>
> where n is an odd integer (positive or negative).
>
> [See eg Hardy & Wright, Introduction to Number Theory]
>

Thanks for the above.

The reason I was hoping there was a way to plug this type of equation into
Brahmagupta's method of composition is that I can find many solutions for

5x^2 + 20 = y^2

where x and y are coprime but can find no such solutions for 5x^2 + 45 = y^2

[Helmut Richter]

On Fri, 27 Apr 2012, Terry M wrote:

> where x and y are coprime but can find no such solutions for 5x^2 + 45 = y^2

Without the restriction of coprimeness there are solutions, e.g. x=6, y=15

With this restriction, there are none:

A square is 0, 1, 4, or 7 (mod 9)
Five times a square os 0, 5, 2, or 8 (mod 9)

So the equation can only be fulfilled when both 5x^2 and y^2 are 0 (mod 9).

--
Helmut Richter

[Terry M]

Hi

"Helmut Richter" <hh...@web.de> wrote in message
news:alpine.LNX.2.00.1...@badwlrz-clhri01.ws.lrz.de...

So I was making hard work of it, lol

Many thanks Helmut ;-)


> --
> Helmut Richter

[Helmut Richter]

On Fri, 27 Apr 2012, Terry M wrote:

> "Helmut Richter" <hh...@web.de> wrote in message
> news:alpine.LNX.2.00.1...@badwlrz-clhri01.ws.lrz.de...
> > On Fri, 27 Apr 2012, Terry M wrote:
> >
> > > where x and y are coprime but can find no such solutions for 5x^2 + 45 =
> > > y^2
> >
> > Without the restriction of coprimeness there are solutions, e.g. x=6, y=15
> >
> > With this restriction, there are none:
> >
> > A square is 0, 1, 4, or 7 (mod 9)
> > Five times a square os 0, 5, 2, or 8 (mod 9)
> >
> > So the equation can only be fulfilled when both 5x^2 and y^2 are 0 (mod 9).
> >
>
> So I was making hard work of it, lol

Whenever you see a Diophantine equation of the form

ax² + by² + c = 0

you should, before thinking, see what happens if taken modulo m for each m
which is:

- the number 8

- p² for a prime p>2 if p² ist a factor of a, b, or c or if p is a
factor of more than one of these

- a prime p>2 that is a simple factor of one of a, b, or c

Often, the complexity reduces or it can be shown that there are no
solutions.

--
Helmut Richter

[Terry M]

Hi Helmut

"Helmut Richter" <hh...@web.de> wrote in message
news:alpine.LNX.2.00.1...@badwlrz-clhri01.ws.lrz.de...

> Whenever you see a Diophantine equation of the form
>
> ax² + by² + c = 0
>
> you should, before thinking, see what happens if taken modulo m for each m
> which is:
>
> - the number 8
>

I think I understand the following two, but why the number 8 ?

Thanks again,

Terry

[Timothy Murphy]

Terry M wrote:

> The reason I was hoping there was a way to plug this type of equation into
> Brahmagupta's method of composition is that I can find many solutions for
>
> 5x^2 + 20 = y^2
>
> where x and y are coprime but can find no such solutions for 5x^2 + 45 =
> y^2

As before, 5 | y, and writing y = 5z we get

x^2 - 5z^2 = -9.

An equation of the form x^2 - dy^2 = c
(where d is not a perfect square)
may have no solution;
but if you can find one you can find an infinite number
by combining this solution with the general solution
of Pell's equation x^2 - dy^2 = 1
(which always has an infinity of solutions),
in the way I suggested.

The equation x^2 - dy^2 = c has a solution
if it has a solution modulo 8d, I think.

In your case this means there must be solutions mod 8 and mod 5,
which there are.

Actually, in this case it is sufficient to find a solution of

u^2 - 5v^2 = -1

since then x = 3u, z = 3v
(and it's not difficult to see that every solution
must be of this form, ie x and z must be divisible by 3).

This has the trivial solution (u,v) = (2,1),
or (x,z) = (6,3) or (x,y) = (6,15)

So there are an infinity of solutions,
which you can get in the way I suggested.
Eg if e = 2 + sqrt5 then e^3 = 38 + 17 sqrt5,
so (u,v) = (38,17) is a solution of u^2 - 5y^2 = -1,
giving (3 x 38, 15 x 17) as a solution of the original equation.

[Helmut Richter]

On Sat, 28 Apr 2012, Terry M wrote:

> "Helmut Richter" <hh...@web.de> wrote in message
> news:alpine.LNX.2.00.1...@badwlrz-clhri01.ws.lrz.de...
>
> > Whenever you see a Diophantine equation of the form
> >
> > ax² + by² + c = 0
> >
> > you should, before thinking, see what happens if taken modulo m for each m
> > which is:
> >
> > - the number 8
> >
>
> I think I understand the following two, but why the number 8 ?

Just because 8 has so few quadratic residues (0, 1, and 4) that you have a
chance that ax² + by² cannot get all values, with good luck not the value
of -c, e.g. 3x² + 7y² is never 6 (mod 8). A test modulo 4 would not have
sufficed.

Needless to say that passing all tests does not mean that there are
solutions. An example is x² + 378y² + 6 = 0 with no solutions (from an old
posting of mine <slrnc5ld51....@lxhri01.lrz.lrz-muenchen.de>; I
did not double-check now).

--
Helmut Richter

[Terry M]

Hi Timothy,

"Timothy Murphy" <gayl...@eircom.net> wrote in message

news:jngodq$fmc$1...@dont-email.me...

> Terry M wrote:
>
>> The reason I was hoping there was a way to plug this type of equation
>> into
>> Brahmagupta's method of composition is that I can find many solutions for
>>
>> 5x^2 + 20 = y^2
>>
>> where x and y are coprime but can find no such solutions for 5x^2 + 45 =
>> y^2
>
> As before, 5 | y, and writing y = 5z we get
>
> x^2 - 5z^2 = -9.
>
> An equation of the form x^2 - dy^2 = c
> (where d is not a perfect square)
> may have no solution;
> but if you can find one you can find an infinite number
> by combining this solution with the general solution
> of Pell's equation x^2 - dy^2 = 1
> (which always has an infinity of solutions),
> in the way I suggested.
>
> The equation x^2 - dy^2 = c has a solution
> if it has a solution modulo 8d, I think.
>

Do you have any idea as to where I can find out more about this?

> In your case this means there must be solutions mod 8 and mod 5,
> which there are.
>
> Actually, in this case it is sufficient to find a solution of
>
> u^2 - 5v^2 = -1
>
> since then x = 3u, z = 3v
> (and it's not difficult to see that every solution
> must be of this form, ie x and z must be divisible by 3).
>
> This has the trivial solution (u,v) = (2,1),
> or (x,z) = (6,3) or (x,y) = (6,15)
>
> So there are an infinity of solutions,
> which you can get in the way I suggested.
> Eg if e = 2 + sqrt5 then e^3 = 38 + 17 sqrt5,
> so (u,v) = (38,17) is a solution of u^2 - 5y^2 = -1,
> giving (3 x 38, 15 x 17) as a solution of the original equation.
>

Yes, but these solutions do not satisfy the requirement that x and y are
coprime

Thanks for your input ;-)

Terry

[Terry M]

Ok, thanks for clarifying that Helmut

> --
> Helmut Richter

[Terry M]

"Helmut Richter" <hh...@web.de> wrote in message
news:alpine.LNX.2.00.1...@badwlrz-clhri01.ws.lrz.de...
> On Sat, 28 Apr 2012, Terry M wrote:
>
>> "Helmut Richter" <hh...@web.de> wrote in message
>> news:alpine.LNX.2.00.1...@badwlrz-clhri01.ws.lrz.de...
>>
>> > Whenever you see a Diophantine equation of the form
>> >
>> > ax² + by² + c = 0
>> >
>> > you should, before thinking, see what happens if taken modulo m for
>> > each m
>> > which is:
>> >
>> > - the number 8
>> >
>>
>> I think I understand the following two, but why the number 8 ?
>
> Just because 8 has so few quadratic residues (0, 1, and 4) that you have a

Aren't the quadratic residues of 8 only 1 and 2?

I thought for the quadratic residue

x^2 = a (mod n)

a and n have to be coprime.

[Helmut Richter]

On Sat, 28 Apr 2012, Terry M wrote:

> > An equation of the form x^2 - dy^2 = c
> > (where d is not a perfect square)
> > may have no solution;
> > but if you can find one you can find an infinite number
> > by combining this solution with the general solution
> > of Pell's equation x^2 - dy^2 = 1
> > (which always has an infinity of solutions),
> > in the way I suggested.
> >
> > The equation x^2 - dy^2 = c has a solution
> > if it has a solution modulo 8d, I think.
> >
>
> Do you have any idea as to where I can find out more about this?

For the elementary treatment of such equations see also Chrystal's book
http://djm.cc/library/Algebra_Elementary_Text-Book_Part_II_Chrystal_edited02.pdf
on page 478ff where you need some terminology introduced in the preceding
chapters on continued fractions.

It is from another era when the actual handling of equations was the aim
of the algebraists, and not so much the structure of the solution.

Do you know Dario Alpern's calculator which does not only compute the
solutions but also explains the steps taken? See
http://www.alpertron.com.ar/QUAD.HTM

--
Helmut Richter

[Helmut Richter]

On Sat, 28 Apr 2012, Terry M wrote:

> > Just because 8 has so few quadratic residues (0, 1, and 4) that you have a

I meant the a where x² = a (mod 8) has a solution.

> Aren't the quadratic residues of 8 only 1 and 2?
>
> I thought for the quadratic residue
>
> x^2 = a (mod n)
>
> a and n have to be coprime.

You are right. Only the a that are coprime with n are called quadratic
residues.

In what way did you mean 1 and 2?

--
Helmut Richter

[Terry M]

"Helmut Richter" <hh...@web.de> wrote in message
news:alpine.LNX.2.00.1...@badwlrz-clhri01.ws.lrz.de...

Sorry, my mistake, I meant 0 and 1.

0^2 = 0 Mod 8
1^2 = 1 Mod 8
2^2 = 4 Mod 8 not coprime
3^2 = 1 Mod 8
4^2 = 0 Mod 8
5^2 = 1 Mod 8
6^2 = 4 mod 8 not coprime
7^2 = 1 Mod 8

So the only quadratic residues of 8 are 0 and 1
not 0, 1 and 4 as you state, unless I'm missing something.



> --
> Helmut Richter

[Terry M]

"Helmut Richter" <hh...@web.de> wrote in message
news:alpine.LNX.2.00.1...@badwlrz-clhri01.ws.lrz.de...

> On Sat, 28 Apr 2012, Terry M wrote:
>
>> > An equation of the form x^2 - dy^2 = c
>> > (where d is not a perfect square)
>> > may have no solution;
>> > but if you can find one you can find an infinite number
>> > by combining this solution with the general solution
>> > of Pell's equation x^2 - dy^2 = 1
>> > (which always has an infinity of solutions),
>> > in the way I suggested.
>> >
>> > The equation x^2 - dy^2 = c has a solution
>> > if it has a solution modulo 8d, I think.
>> >
>>
>> Do you have any idea as to where I can find out more about this?
>
> For the elementary treatment of such equations see also Chrystal's book
> http://djm.cc/library/Algebra_Elementary_Text-Book_Part_II_Chrystal_edited02.pdf
> on page 478ff where you need some terminology introduced in the preceding
> chapters on continued fractions.

Thanks, I'll check it out

>
> It is from another era when the actual handling of equations was the aim
> of the algebraists, and not so much the structure of the solution.
>
> Do you know Dario Alpern's calculator which does not only compute the
> solutions but also explains the steps taken? See
> http://www.alpertron.com.ar/QUAD.HTM
>

Yes, I have come acroos Dario's website

> --
> Helmut Richter

[Terry M]

"Helmut Richter" <hh...@web.de> wrote in message
news:alpine.LNX.2.00.1...@badwlrz-clhri01.ws.lrz.de...
> On Sat, 28 Apr 2012, Terry M wrote:

> e.g. 3x² + 7y² is never 6 (mod 8).

Hi Helmut,

The more I reread your posts, the more I'm getting confused :(

possible values of 3x² (Mod 8) are 0, 3 and 4
possible values of 7y² (Mod 8) are 0, 4 and 7

so 3x² + 7y² can only be 0, 3, 4 or 7 (Mod 8)

so 3x² + 7y² is never 1, 2, 5 or 6 (Mod 8)

I think I'm correct in this ?
> Helmut Richter

[Terry M]

"Terry M" <he...@home.net> wrote in message
news:Csidnbi0pcV7jwDS...@bt.com...

>
> "Helmut Richter" <hh...@web.de> wrote in message
> news:alpine.LNX.2.00.1...@badwlrz-clhri01.ws.lrz.de...
>> On Sat, 28 Apr 2012, Terry M wrote:
>
>> e.g. 3x² + 7y² is never 6 (mod 8).
>
> Hi Helmut,
>
> The more I reread your posts, the more I'm getting confused :(
>
> possible values of 3x² (Mod 8) are 0, 3 and 4
> possible values of 7y² (Mod 8) are 0, 4 and 7
>
> so 3x² + 7y² can only be 0, 3, 4 or 7 (Mod 8)

correction: so 3x² + 7y² can only be 0, 2, 3, 4, 7 (Mod 3)

>
> so 3x² + 7y² is never 1, 2, 5 or 6 (Mod 8)

correction: so 3x² + 7y² is never 1, 5 or 6 (Mod 8)

[Timothy Murphy]

Helmut Richter wrote:

> It is from another era when the actual handling of equations was the aim
> of the algebraists, and not so much the structure of the solution.

What exactly (or even vaguely) does that mean?

[Helmut Richter]

On Sun, 29 Apr 2012, Terry M wrote:

> correction: so 3x² + 7y² is never 1, 5 or 6 (Mod 8)

This is 100% correct.

I mentioned only the 6 as example but the others are correct as well.
The 1 and 5 could have been caught modulo 4, but for the 6 it is necessary
to check modulo 8.

--
Helmut Richter

[Helmut Richter]

On Sun, 29 Apr 2012, Timothy Murphy wrote:

> Helmut Richter wrote:
>
> > It is from another era when the actual handling of equations was the aim
> > of the algebraists, and not so much the structure of the solution.
>
> What exactly (or even vaguely) does that mean?

It has only a vague meaning. It means that I have yet to see an algebra
book (beyond grammar school level) of the last 70 years where the author
takes the pain of explaining how to transform equations in order to get
them solved. Today the focus is on algebraic structures. The modern
approach, as for instance in van der Waerden's book which originally had
the title "Modern Algebra" and later "Algebra" is, of course, in general
much more fruitful for mathematics, but if someone has an equation and
wants to find its solutions, he may be better off with an old book.

--
Helmut Richter

[Terry M]

"Helmut Richter" <hh...@web.de> wrote in message
news:alpine.LNX.2.00.1...@badwlrz-clhri01.ws.lrz.de...

It is many years since I touched on modulo arithmetic. So thanks once again
for your time Helmut, it is much appreciated.


> --
> Helmut Richter

[Terry M]

"Helmut Richter" <hh...@web.de> wrote in message
news:alpine.LNX.2.00.1...@badwlrz-clhri01.ws.lrz.de...

ok.

The equation I am working on is (a^2 + b^2)(c^2 + d^2) = x^2
with d > c >= b > a > 0, a and b are coprime, c and d are coprime
and I am aware of the Brahmagupta-Fibonacci identity.

If a and b are known, what (if anything) can be deduced about c and d.

My original examples were where a=1, b=2 and c=2 and 3 respectively
It has now been shown that where c=2 there are many (infinite) values for d
and where c=3 there are no possible values for d within the constraints.

> --
> Helmut Richter

[Terry M]

My deductions so far...

of a², b², c² and d²

no solutions if exactly three of these = 1 mod 8

if exactly one of a² and b² = 1 mod 8 and exactly one of c² and d² = 1 mod
8, then the two remaining must be equal mod 8

e.g if a² = 1 mod 8 and c²=1 mod 8 then if b² <> d² mod 8 there are no
solutions.

[Timothy Murphy]

Helmut Richter wrote:

> On Sun, 29 Apr 2012, Timothy Murphy wrote:
>
>> Helmut Richter wrote:
>>
>> > It is from another era when the actual handling of equations was the
>> > aim of the algebraists, and not so much the structure of the solution.
>>
>> What exactly (or even vaguely) does that mean?
>
> It has only a vague meaning. It means that I have yet to see an algebra
> book (beyond grammar school level) of the last 70 years where the author
> takes the pain of explaining how to transform equations in order to get
> them solved.

OK, thanks, I see what you mean now.
I was baffled by the phrase "structure of the solution".