The old Google Groups will be going away soon, but your browser is incompatible with the new version.
Pell type equations
 There are currently too many topics in this group that display first. To make this topic appear first, remove this option from another topic. There was an error processing your request. Please try again. Standard view   View as tree
 Messages 1 - 25 of 28 Newer >

From:
To:
Cc:
Followup To:
Subject:
 Validation: For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon.

More options Apr 26 2012, 2:12 pm
Newsgroups: sci.math
From: "Terry M" <h...@home.net>
Date: Thu, 26 Apr 2012 19:12:23 +0100
Local: Thurs, Apr 26 2012 2:12 pm
Subject: Pell type equations
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.

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.

To post a message you must first join this group.
You do not have the permission required to post.
More options Apr 26 2012, 3:09 pm
Newsgroups: sci.math
From: bert <bert.hutchi...@btinternet.com>
Date: Thu, 26 Apr 2012 12:09:05 -0700 (PDT)
Local: Thurs, Apr 26 2012 3:09 pm
Subject: Re: Pell type equations

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.
--

To post a message you must first join this group.
You do not have the permission required to post.
More options Apr 26 2012, 4:27 pm
Newsgroups: sci.math
From: "Terry M" <h...@home.net>
Date: Thu, 26 Apr 2012 21:27:40 +0100
Local: Thurs, Apr 26 2012 4:27 pm
Subject: Re: Pell type equations

"bert" <bert.hutchi...@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,

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

To post a message you must first join this group.
You do not have the permission required to post.
More options Apr 26 2012, 5:09 pm
Newsgroups: sci.math
From: amzoti <amz...@gmail.com>
Date: Thu, 26 Apr 2012 14:09:10 -0700 (PDT)
Local: Thurs, Apr 26 2012 5:09 pm
Subject: Re: Pell type equations

To post a message you must first join this group.
You do not have the permission required to post.
More options Apr 26 2012, 8:12 pm
Newsgroups: sci.math
From: Timothy Murphy <gayle...@eircom.net>
Date: Fri, 27 Apr 2012 01:12:58 +0100
Local: Thurs, Apr 26 2012 8:12 pm
Subject: Re: Pell type equations

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

To post a message you must first join this group.
You do not have the permission required to post.
More options Apr 27 2012, 6:48 am
Newsgroups: sci.math
From: "Terry M" <h...@home.net>
Date: Fri, 27 Apr 2012 11:48:06 +0100
Local: Fri, Apr 27 2012 6:48 am
Subject: Re: Pell type equations
Hi

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

news:jncoab\$5cd\$1@dont-email.me...

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

To post a message you must first join this group.
You do not have the permission required to post.
More options Apr 27 2012, 7:57 am
Newsgroups: sci.math
From: Helmut Richter <hh...@web.de>
Date: Fri, 27 Apr 2012 13:57:36 +0200
Local: Fri, Apr 27 2012 7:57 am
Subject: Re: Pell type equations

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

To post a message you must first join this group.
You do not have the permission required to post.
More options Apr 27 2012, 8:51 am
Newsgroups: sci.math
From: "Terry M" <h...@home.net>
Date: Fri, 27 Apr 2012 13:51:58 +0100
Local: Fri, Apr 27 2012 8:51 am
Subject: Re: Pell type equations
Hi

"Helmut Richter" <hh...@web.de> wrote in message

> 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

Many thanks Helmut ;-)

To post a message you must first join this group.
You do not have the permission required to post.
More options Apr 28 2012, 3:41 am
Newsgroups: sci.math
From: Helmut Richter <hh...@web.de>
Date: Sat, 28 Apr 2012 09:41:12 +0200
Local: Sat, Apr 28 2012 3:41 am
Subject: Re: Pell type equations

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

To post a message you must first join this group.
You do not have the permission required to post.
More options Apr 28 2012, 6:03 am
Newsgroups: sci.math
From: "Terry M" <h...@home.net>
Date: Sat, 28 Apr 2012 11:03:44 +0100
Local: Sat, Apr 28 2012 6:03 am
Subject: Re: Pell type equations
Hi Helmut

"Helmut Richter" <hh...@web.de> wrote in message

> 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

To post a message you must first join this group.
You do not have the permission required to post.
More options Apr 28 2012, 8:39 am
Newsgroups: sci.math
From: Timothy Murphy <gayle...@eircom.net>
Date: Sat, 28 Apr 2012 13:39:21 +0100
Local: Sat, Apr 28 2012 8:39 am
Subject: Re: Pell type equations

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

To post a message you must first join this group.
You do not have the permission required to post.
More options Apr 28 2012, 10:58 am
Newsgroups: sci.math
From: Helmut Richter <hh...@web.de>
Date: Sat, 28 Apr 2012 16:58:11 +0200
Local: Sat, Apr 28 2012 10:58 am
Subject: Re: Pell type equations

On Sat, 28 Apr 2012, Terry M wrote:
> "Helmut Richter" <hh...@web.de> wrote in message

> > 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).

--
Helmut Richter

To post a message you must first join this group.
You do not have the permission required to post.
More options Apr 28 2012, 10:58 am
Newsgroups: sci.math
From: "Terry M" <h...@home.net>
Date: Sat, 28 Apr 2012 15:58:10 +0100
Local: Sat, Apr 28 2012 10:58 am
Subject: Re: Pell type equations
Hi Timothy,

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

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

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

Terry

To post a message you must first join this group.
You do not have the permission required to post.
More options Apr 28 2012, 11:03 am
Newsgroups: sci.math
From: "Terry M" <h...@home.net>
Date: Sat, 28 Apr 2012 16:03:11 +0100
Local: Sat, Apr 28 2012 11:03 am
Subject: Re: Pell type equations

To post a message you must first join this group.
You do not have the permission required to post.
More options Apr 28 2012, 2:21 pm
Newsgroups: sci.math
From: "Terry M" <h...@home.net>
Date: Sat, 28 Apr 2012 19:21:34 +0100
Local: Sat, Apr 28 2012 2:21 pm
Subject: Re: Pell type equations

"Helmut Richter" <hh...@web.de> wrote in message

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.

To post a message you must first join this group.
You do not have the permission required to post.
More options Apr 28 2012, 3:33 pm
Newsgroups: sci.math
From: Helmut Richter <hh...@web.de>
Date: Sat, 28 Apr 2012 21:33:42 +0200
Local: Sat, Apr 28 2012 3:33 pm
Subject: Re: Pell type equations

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.

http://djm.cc/library/Algebra_Elementary_Text-Book_Part_II_Chrystal_e...
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

--
Helmut Richter

To post a message you must first join this group.
You do not have the permission required to post.
More options Apr 28 2012, 3:42 pm
Newsgroups: sci.math
From: Helmut Richter <hh...@web.de>
Date: Sat, 28 Apr 2012 21:42:07 +0200
Local: Sat, Apr 28 2012 3:42 pm
Subject: Re: Pell type equations

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

To post a message you must first join this group.
You do not have the permission required to post.
More options Apr 28 2012, 4:20 pm
Newsgroups: sci.math
From: "Terry M" <h...@home.net>
Date: Sat, 28 Apr 2012 21:20:54 +0100
Local: Sat, Apr 28 2012 4:20 pm
Subject: Re: Pell type equations

"Helmut Richter" <hh...@web.de> wrote in message

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.

To post a message you must first join this group.
You do not have the permission required to post.
More options Apr 28 2012, 5:23 pm
Newsgroups: sci.math
From: "Terry M" <h...@home.net>
Date: Sat, 28 Apr 2012 22:23:22 +0100
Local: Sat, Apr 28 2012 5:23 pm
Subject: Re: Pell type equations

"Helmut Richter" <hh...@web.de> wrote in message

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

Yes, I have come acroos Dario's website

To post a message you must first join this group.
You do not have the permission required to post.
More options Apr 29 2012, 6:07 am
Newsgroups: sci.math
From: "Terry M" <h...@home.net>
Date: Sun, 29 Apr 2012 11:07:32 +0100
Local: Sun, Apr 29 2012 6:07 am
Subject: Re: Pell type equations

"Helmut Richter" <hh...@web.de> wrote in message

> 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 ?

To post a message you must first join this group.
You do not have the permission required to post.
More options Apr 29 2012, 6:14 am
Newsgroups: sci.math
From: "Terry M" <h...@home.net>
Date: Sun, 29 Apr 2012 11:14:27 +0100
Local: Sun, Apr 29 2012 6:14 am
Subject: Re: Pell type equations

"Terry M" <h...@home.net> wrote in message

news:Csidnbi0pcV7jwDSnZ2dnUVZ8nqdnZ2d@bt.com...

> "Helmut Richter" <hh...@web.de> wrote in message
>> 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)

To post a message you must first join this group.
You do not have the permission required to post.
More options Apr 29 2012, 6:32 am
Newsgroups: sci.math
From: Timothy Murphy <gayle...@eircom.net>
Date: Sun, 29 Apr 2012 11:32:38 +0100
Local: Sun, Apr 29 2012 6:32 am
Subject: Re: Pell type equations

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

To post a message you must first join this group.
You do not have the permission required to post.
More options Apr 29 2012, 7:13 am
Newsgroups: sci.math
From: Helmut Richter <hh...@web.de>
Date: Sun, 29 Apr 2012 13:13:48 +0200
Local: Sun, Apr 29 2012 7:13 am
Subject: Re: Pell type equations

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

To post a message you must first join this group.
You do not have the permission required to post.
More options Apr 29 2012, 7:23 am
Newsgroups: sci.math
From: Helmut Richter <hh...@web.de>
Date: Sun, 29 Apr 2012 13:23:47 +0200
Local: Sun, Apr 29 2012 7:23 am
Subject: Re: Pell type equations

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

To post a message you must first join this group.
You do not have the permission required to post.
More options Apr 29 2012, 7:26 am
Newsgroups: sci.math
From: "Terry M" <h...@home.net>
Date: Sun, 29 Apr 2012 12:26:09 +0100
Local: Sun, Apr 29 2012 7:26 am
Subject: Re: Pell type equations

"Helmut Richter" <hh...@web.de> wrote in message

> 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.

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