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.
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.
--
> 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.
> --
> 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.
> 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
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.
-- Timothy Murphy
e-mail: gayleard /at/ eircom.net
tel: +353-86-2336090, +353-1-2842366
s-mail: School of Mathematics, Trinity College Dublin
> > 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.rgt.a282...@lxhri01.lrz.lrz-muenchen.de>; I did not double-check now).
>> 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
>> > 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.rgt.a282...@lxhri01.lrz.lrz-muenchen.de>; I
> did not double-check now).
> 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.rgt.a282...@lxhri01.lrz.lrz-muenchen.de>; I
> did not double-check now).
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?
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
>> > 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?
> 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 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?
-- Timothy Murphy
e-mail: gayleard /at/ eircom.net
tel: +353-86-2336090, +353-1-2842366
s-mail: School of Mathematics, Trinity College Dublin
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.
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.
>> 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.
It is many years since I touched on modulo arithmetic. So thanks once again for your time Helmut, it is much appreciated.
