Author |
Topic: Special case Pell equation (Read 2941 times) |
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender: 
Posts: 1825
|
 |
Special case Pell equation
« on: Jul 11th, 2008, 2:24am » |
 Quote  Modify
|
Does anyone know if the special case Pell equation, x2 - 2y2 = N, where N is square, has been studied?
Basically I am looking for a general solution to the Diophantine equation:
x2 - 2y2 = k2
Any insights or references would be gratefully received.
|
|
 IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Special case Pell equation
« Reply #1 on: Jul 11th, 2008, 9:09am » |
Quote Modify
|
I don't know if it's any simpler than the case where N is not a square.
Basically you are looking for all elements x+y 2   (2) which have norm N. Since (2) is a principal ideal domain, it suffices to find all ideals (x+y2) of norm N; for each such ideal we have the sequence of solutions  (3+22)n(x+y2).
For each prime power q || N, we take an element wq of norm q, and then multiply them all together to get an element of norm N. Say q=pa.
For p=2 (p ramified), wq = (2)a is the only possibility.
For p=1 mod 8 (p split), there exists z = x+y2 with x2-2y2=p. The other prime ideal of norm p is generated by z' = x-y2. So wq = ziz'a-i for some i, 0  i a.
For p=3 mod 8 (p inert), (p) is prime of norm p2. So wp = pa/2 is the only possibility (there is no solution if a is odd).
So the total number of ideals is  (1+a), where the product is over all prime powers pa || N where p=1 mod 8, and each ideal gives a sequence of solutions by taking all the generators of positive norm.
It is very similar to, say, x2+y2 = N, except there of course the unit group is finite. But the procedure is the same: factor N; for each split prime (here p=1 mod 4) write p as a norm (sum of two squares); then use this to find all ideals of norm N (again (1+a), where now we run through p=1 mod 4). Then each ideal gives 4 solutions since there are 4 units of norm 1.
|
| « Last Edit: Jul 11th, 2008, 9:11am by Eigenray » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Special case Pell equation
« Reply #2 on: Jul 14th, 2008, 11:25am » |
Quote Modify
|
Would it not be simpler to rewrite the equation as:
x2-k2=2y2
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Special case Pell equation
« Reply #3 on: Jul 14th, 2008, 12:05pm » |
Quote Modify
|
Ah, I was thinking k was fixed and we wanted to find x and y. We can also give a parameterization for all primitive solutions:
x = u2+2v2
y = 2uv
k = (u2-2v2)
where u,v are relatively prime and u is odd.
|
| « Last Edit: Jul 14th, 2008, 12:08pm by Eigenray » |
IP Logged |
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Special case Pell equation
« Reply #4 on: Jul 14th, 2008, 2:37pm » |
Quote Modify
|
Thanks for the feedback.
Unfortunately k is fixed. I was looking for a slick parametrisation of the special case Pell equations equations:
x2 - 2y2 = 1
x2 - 2y2 = 4
x2 - 2y2 = 9
et cetera.
I know that Euler dealt with parametrisation of x4 - 2y4 = k2, but I've never seen, what you would expect, the more basic second degree form dealt with. However, my experience and texts are all limited to (basic) elementary number theory and I have little experience with advanced number theory, so it is quite possible that these special cases have been dealt with in more recent years.
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Special case Pell equation
« Reply #5 on: Jul 14th, 2008, 3:17pm » |
Quote Modify
|
At first glance, it seems that given the first two solution, you can just apply
x(n+2) = 6x(n+1)-x(n)
y(n+2) = 6y(n+1)-y(n)
to get the rest. (For added slickness, you can find the closed form)
k=1:
3 2
17 12
99 70
577 408
k=2:
6 4
34 24
198 140
1154 816
k=3:
9 6
51 36
297 210
1731 1224
And really, the first series is enough, just multiply by k to get the others. Not sure how to prove this covers all solutions though.
However, if this is all, then it explains why Euler skipped straight to x4 - 2y4 = k2.
|
| « Last Edit: Jul 14th, 2008, 3:20pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: Special case Pell equation
« Reply #6 on: Jul 14th, 2008, 3:46pm » |
Quote Modify
|
on Jul 14th, 2008, 3:17pm, towr wrote:| And really, the first series is enough, just multiply by k to get the others. Not sure how to prove this covers all solutions though. |
|
I don't think it does. For k = 7, the smallest solution you'd find by that method would be (x, y) = (21, 14). However, (9, 4) and (11, 6) also work.
Edit: not that I have a better idea...
|
| « Last Edit: Jul 14th, 2008, 3:47pm by pex » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Special case Pell equation
« Reply #7 on: Jul 14th, 2008, 4:41pm » |
Quote Modify
|
Was what I said too abstract? Here is an example: k=3*7*17. We first solve x2-2y2 = p for each prime p dividing N. There is only a solution if p = 1 mod 8 (and this solution is unique up to conjugation and units):
For p=7, we have (3,1).
For p=17, we have (5,2).
Otherwise, we have only the solution (p,0) for x2-2y2=p2.
Now we take our prime solutions and multiply them together to get solutions for N: if (a,b) is a solution for A, and (x,y) is a solution for X, then (a,b)*(x,y) = (ax+2by, ay+bx) is a solution for A*X.
For N=3272172, we can take
(3,0)*(3,1)2*(5,2)2 = (1809, 1254)
(3,0)*(3,1)2*(5,2)(5,-2) = (561, 306)
(3,0)*(3,1)2*(5,-2)2 = (369, -66)
(3,0)*(3,1)(3,-1)*(5,2)2 = (693, 420)
(3,0)*(3,1)(3,-1)*(5,2)(5,-2) = (357, 0)
(3,0)*(3,1)(3,-1)*(5,-2)2 = (693, -420)
(3,0)*(3,-1)2*(5,2)2 = (369, 66)
(3,0)*(3,-1)2*(5,2)(5,-2) = (561, -306)
(3,0)*(3,-1)2*(5,-2)2 = (1809, -1254)
Now any other solution can be obtained from exactly one of these by multiplying by a power of (3,2) (or (3,2)-1=(3,-2)). E.g.,
(3,2)(1809, 1254) = (10443, 7380)
(3,2)-1(1809, 1254) = (411, 144)
[ The solution (x,y) is really the element x+y2  [2]. An element has norm N iff it generates an ideal of norm N. There are only finitely many such ideals; two elements generates the same ideal iff they differ by a unit, and the group of units with norm 1 is generated by the elements -1 and 3+22. ]
Finding the complete set of solutions requires solving congruences x2-2y2=p for each p|k, but I don't see how there could be any way around this.
For practical purposes, the worse part is probably factoring k. Then, for each p, there is a standard algorithm for finding x such that x2=2 mod p. This means that  =x+2 has norm divisible by p, so it is divisible by an element  of norm p. Since [2] is a Euclidean domain, we can use the Euclidean algorithm to quickly find ~ gcd(, p).
|
| « Last Edit: Jul 15th, 2008, 6:18am by Eigenray » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Special case Pell equation
« Reply #8 on: Jul 14th, 2008, 5:18pm » |
Quote Modify
|
on Jul 14th, 2008, 2:37pm, Sir Col wrote:| I know that Euler dealt with parametrisation of x4 - 2y4 = k2, but I've never seen, what you would expect, the more basic second degree form dealt with. |
|
Do you know his result? We can start with (3,2,7), and then if (x,y,k) is a solution, so is (x', y', k'), where x' = x4+2y4, y' = 2xyk, k' = 2k4 - x'2. But I'm not sure if this gives this doesn't give all (primitive) solutions.
Key fact: if X2 - 2Y2 = K2 is a primitive solution, then
X = u2+2v2,
Y = 2uv,
K = |u2-2v2|,
where u,v are relatively prime with u odd.
If (x2,y2,k) is a solution, we can assume it is primitive because p|x,y implies p2|k. Taking u,v as above, (x,v,u) is a solution, which is primitive because u,v are relatively prime. Therefore
x = a2+2b2
v = 2ab
u = |a2-2b2|.
Since y2 = 2uv = 4abu is a square, and a,b,u are relatively prime, we know that a=A2, b=B2, and u=U2 are all squares. But now there are two cases.
In the first case, A4-2B4 = U2, i.e., (A,B,U) is a solution which is smaller than the original one [ since a < x unless b=0, a=1, which is the solution (1,0,1) ], and so we are done by induction (with whatever we're proving, not that I know what that is yet).
But in the second case we have A4 - 2B4 = -U2. This leads to
A2 = m2 - n2 + 2mn
B2 = m2 + n2.
We can write (m,n) = (r2-s2, 2rs) and stick that back into the formula for A2, but I don't know if that goes anywhere*.
One solution to the above is (r,s) = (1,0), (A,B,U)=(1,1,1), giving us the solution (x,y,k) = (3,2,7). But there is also the solution (r,s) = (3,2), (m,n) = (5, 12), (A,B,U) = (1, 13, 239), and finally (x,y,k) = (57123, 6214, 3262580153). Similarly, (r,s) = (2,39) gives (A,B,U) = (1343, 1525, 2750257), and (x,y,k) = (14070212996451, 11265465210550, 83545316896178428367654599).
*(Edit): Let C = r2+2rs-s2. Then we have
(C+A)(C-A) = C2 - A2 = 8(rs)2.
Since r,s are relatively prime and of opposite parity, A,C are odd and relatively prime, and gcd(C+A,C-A)=2. If C>0, then {C+A, C-A} = {2f2, 4g2} for integers f, g, with fg=rs, and
r2+2rs-s2 = C = [(C+A)+(C-A)]/2 = f2 + 2g2,
so
2g4-s4 = (gr - fs + gs)2,
meaning (s, g, gr-fs+gs) is a solution, and smaller because g <= rs = n/2 < B, unless f=0, in which case n=0, and A=B=1. Or if C<0, we have
2g4-r4 = (gs - fr - gr)2,
so (r, g, gs-fr-gr) is a smaller solution.
We should be able to work backwards then and obtain all solutions this way.
|
| « Last Edit: Jul 14th, 2008, 9:09pm by Eigenray » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Special case Pell equation
« Reply #9 on: Jul 15th, 2008, 1:21am » |
Quote Modify
|
on Jul 14th, 2008, 4:41pm, Eigenray wrote:| Was what I said too abstract? |
|
It was a little bit. It's starting to dawn now though.
Quote:Now we take our prime solutions and multiply them together to get solutions for N: if (a,b) is a solution for A, and (x,y) is a solution for X, then (a,b)*(x,y) = (ax+2by, ay+bx) is a solution for A*X.
For N=3272172, we can take
(3,0)*(3,1)2*(5,2)2 = (1809, 1254)
(3,0)*(3,1)2*(5,2)(5,-2) = (561, 306)
(3,0)*(3,1)2*(5,-2)2 = (369, -66)
(3,0)*(3,1)(3,-1)*(5,2)2 = (693, 420)
(3,0)*(3,1)(3,-1)*(5,2)(5,-2) = (357, 0)
(3,0)*(3,1)(3,-1)*(5,-2)2 = (693, -420)
(3,0)*(3,-1)2*(5,2)2 = (369, 66)
(3,0)*(3,-1)2*(5,2)(5,-2) = (561, -306)
(3,0)*(3,-1)2*(5,-2)2 = (1809, -1254)
|
|
Is there a good way to avoid getting both (x,y) and (x,-y) here? Because once we have (x,y), we already know (x,-y), (-x,y) and (-x,-y) are solutions as well.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Special case Pell equation
« Reply #10 on: Jul 15th, 2008, 6:13am » |
Quote Modify
|
on Jul 15th, 2008, 1:21am, towr wrote:| Is there a good way to avoid getting both (x,y) and (x,-y) here? Because once we have (x,y), we already know (x,-y), (-x,y) and (-x,-y) are solutions as well. |
|
Yes. Note that these symmetries come from two distinct operations: multiplication by -1, which takes (x,y) to (-x,-y), and conjugation, which takes (x,y) to (x,-y). Multiplication by -1 gives the same ideal, which is only counted once. Conjugation, however, usually gives a different ideal. (For the purposes of this problem you can replace 'ideal' with 'element of [2] modulo multiplication by units'.)
Say N = 2ipa qb, where each p = 1 mod 8, and q = 3 mod 8. If some b is odd there are no solutions. Otherwise, there are (1+a) 'basic' solutions (ideals), namely:
(0,1)i zpuzp'a-u (q,0)b/2.
Conjugating replaces each u with a-u. So we can lexicographically order the (u) vectors and only take the first 'half'. That is, require u1 a1/2; if u1=a1/2, require u2 a2/2; etc.
Note that there is an even number of ideals unless all ai are even, in which case N is a square and the odd solution is (N,0), which is the only one preserved by conjugation. (Note that zpzp' = (p,0) by definition.)
|
| « Last Edit: Jul 15th, 2008, 6:27am by Eigenray » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print