5
$\begingroup$

Dario Alpern's Alpertron is convenient for solving Pell and Pell-like equations. It can even solve the one at the heart of Archimedes' cattle problem,

$$p^2-(4)(609)(7766)(4657^2)q^2=1$$

and give its 100000-digit fundamental solution in about a minute (and that's using an old computer). However, while testing the Pell-like equation for various integer $n$,

$$x^2 - 3\big(108(3n^2)^6 - 1\big)y^2 = 3n^2\tag{1}$$

the Alpertron can solve for some, but says that $n = 5$ (among others) has no solutions. But $(1)$ in fact has a parametric solution,

$$x,y = 486n^7, n$$

So why can it solve some $n$ of $(1)$, but not others? (There is a step-by-step button which may partly explain his algorithm.)

$\color{green}{Edit\, (Nov.\, 24)}$

As pointed out by Will Jagy in his answer below, the problem seems to be that $x,y$ of $(1)$ have a common factor. However, Alpertron also can't solve,

$$x^2-dy^2 = 32\tag{2}$$

for $d=761$ (co-prime $x,y = 469, 17$), $d=1489$ ($x,y = 39,1$), and many others. Thus while it is an excellent source, if it says "No solutions", let the user be aware that with its present code, it can be mistaken.

P.S. I've tried emailing Alpern about this bug, but he seems to be using an old comment/guestbook which retired April 2012.

$\endgroup$
  • 4
    $\begingroup$ I blame the parents. $\endgroup$ – Will Jagy Sep 8 '13 at 3:18
  • $\begingroup$ Does that title really mean what you want to ask? If a program "can't" "not" solve a problem, then it must solve the problem. $\endgroup$ – user940 Nov 24 '13 at 20:32
  • 1
    $\begingroup$ @Byron: Oops, there goes my English as a second language. I can't believe this question stood for 2 months without anyone pointing it out. I'll change it. :) $\endgroup$ – Tito Piezas III Nov 24 '13 at 20:35
  • $\begingroup$ @TitoPiezasIII Little things like that bug me. :) $\endgroup$ – user940 Nov 24 '13 at 20:40
  • $\begingroup$ You may want to also try this Pell equation solver, where the author gave a useful reference regarding the method. $\endgroup$ – Yong Hao Ng Mar 6 '14 at 3:44
5
$\begingroup$

I have answered on MSE many times about this: using Lagrange/Gauss method, you can find the cycle of "reduced" forms in the equivalence class of $x^2 - t y^2.$ Furthermore, the disciminant of this form being $4t,$ all primitively represented values with absolute value up to $$ \frac{1}{2} \sqrt {4t} = \sqrt t $$ is found as a first coefficient of one of the forms.

Perhaps the kicker is PRIMITIVE representations. For you, $\gcd(n,486 n^7) = n. $ I would say that any solution to your problem with $n=5$ must have both $x,y$ divisible by $5.$ That would throw off the usual method. I think you should expect the same trouble for $n=5,11,17,23,29,41,\ldots$

EDIT, 5 March 2014: I just noticed the trouble about 32 with d=761, 1489. Lagrange's method easily gives these, see below where 32 occurs as the first coefficient of one of the forms (triples).

  jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./Pell
Input n for Pell 
761

0  form   1 54 -32   delta  -1
1  form   -32 10 23   delta  1
2  form   23 36 -19   delta  -2
3  form   -19 40 19   delta  2
4  form   19 36 -23   delta  -1
5  form   -23 10 32   delta  1
6  form   32 54 -1   delta  -54
7  form   -1 54 32   delta  1
8  form   32 10 -23   delta  -1
9  form   -23 36 19   delta  2
10  form   19 40 -19   delta  -2
11  form   -19 36 23   delta  1
12  form   23 10 -32   delta  -1
13  form   -32 54 1   delta  54
14  form   1 54 -32

 disc   3044
Automorph, written on right of Gram matrix:  
-27201  -1484800
-46400  -2532801


 Pell automorph 
-1280001  -35310400
-46400  -1280001

Pell unit 
-1280001^2 - 761 * -46400^2 = 1 

=========================================

Pell NEGATIVE 
-800^2 - 761 * -29^2 = -1 

=========================================

761       761

jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$



jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ 
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./Pell
Input n for Pell 
1489

0  form   1 76 -45   delta  -1
1  form   -45 14 32   delta  1
2  form   32 50 -27   delta  -2
3  form   -27 58 24   delta  2
4  form   24 38 -47   delta  -1
5  form   -47 56 15   delta  4
6  form   15 64 -31   delta  -2
7  form   -31 60 19   delta  3
8  form   19 54 -40   delta  -1
9  form   -40 26 33   delta  1
10  form   33 40 -33   delta  -1
11  form   -33 26 40   delta  1
12  form   40 54 -19   delta  -3
13  form   -19 60 31   delta  2
14  form   31 64 -15   delta  -4
15  form   -15 56 47   delta  1
16  form   47 38 -24   delta  -2
17  form   -24 58 27   delta  2
18  form   27 50 -32   delta  -1
19  form   -32 14 45   delta  1
20  form   45 76 -1   delta  -76
21  form   -1 76 45   delta  1
22  form   45 14 -32   delta  -1
23  form   -32 50 27   delta  2
24  form   27 58 -24   delta  -2
25  form   -24 38 47   delta  1
26  form   47 56 -15   delta  -4
27  form   -15 64 31   delta  2
28  form   31 60 -19   delta  -3
29  form   -19 54 40   delta  1
30  form   40 26 -33   delta  -1
31  form   -33 40 33   delta  1
32  form   33 26 -40   delta  -1
33  form   -40 54 19   delta  3
34  form   19 60 -31   delta  -2
35  form   -31 64 15   delta  4
36  form   15 56 -47   delta  -1
37  form   -47 38 24   delta  2
38  form   24 58 -27   delta  -2
39  form   -27 50 32   delta  1
40  form   32 14 -45   delta  -1
41  form   -45 76 1   delta  76
42  form   1 76 -45

 disc   5956
Automorph, written on right of Gram matrix:  
-301402109537809  -23083652981172600
-512970066248280  -39287127144407089


 Pell automorph 
-19794264626972449  -763812428643688920
-512970066248280  -19794264626972449

Pell unit 
-19794264626972449^2 - 1489 * -512970066248280^2 = 1 

=========================================

Pell NEGATIVE 
99484332^2 - 1489 * 2578145^2 = -1 

=========================================

1489       1489

jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ 

  1. I wrote a program that displays the x,y values. Looking at the cycle above, we se that all solutions of $x^2 - 761 y^2 = 32$ are images of these under the automorphism indicated.

    jagy@phobeusjunior:~$ ./Pell_Target_Fundamental

    1280001^2 - 761 46400^2 = 1

    x^2 - 761 y^2 = 32

    Sun May 8 08:21:00 PDT 2016

    x: 469 y: 17 ratio: 27.58823529411764 SEED x: 43669 y: 1583 ratio: 27.58622867972204 SEED

    Sun May 8 08:22:00 PDT 2016

    x^2 - 761 y^2 = 32

    Pell automorph 1280001 35310400 46400 1280001

    jagy@phobeusjunior:~$

$\endgroup$
  • $\begingroup$ Will, how can I finish off here? $\endgroup$ – Pedro Tamaroff Sep 8 '13 at 3:31
  • $\begingroup$ Is the troublesome $n$ for primes $n = 3m-1$? $\endgroup$ – Tito Piezas III Sep 8 '13 at 3:48
  • $\begingroup$ @TitoPiezasIII, yes. A bit less predictable for composite $n$ divisible by some of those primes. Also, odd primes, so $n=6m-1$ $\endgroup$ – Will Jagy Sep 8 '13 at 3:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.