## 1. Solution by brute force method

### Searching the solution by brute force method

For first try, compute n = (x2-1)/y2, (x2+1)/y2 for x, y less than 1000,
and find the solutions for n less than 100 which does not have the square factors.

When we find the solution of x2 - ny2 = -1,
then we can construct the solution for x2 - ny2 = +1 by

X = x2 + ny2
Y = 2xy

### Program

10   ' pell1
20   dim M(100)
30   for I=2 to 100
40     if moeb(I)=0 then M(I)=1 else M(I)=0
50   next I
60   '
70   for X=1 to 1000:X2=X^2
80     for Y=1 to 1000:Y2=Y^2
90       if (X2+1)@Y2=0 then W=(X2+1)\Y2 else 120
100       if or{W<1,W>=100} then 120
110       if M(W)=0 then print W;X;Y;X2-W*Y2:M(W)=1
120       if (X2-1)@Y2=0 then W=(X2-1)\Y2 else 150
130       if or{W<1,W>=100} then 150
140       if M(W)=0 then print W;X;Y;X2-W*Y2:M(W)=1
150     next Y
160   next X
170   '
180   for I=2 to 100
190     if M(I)=0 then print I;
200   next I

moeb(I) in line 40 denotes the moebius function, which returns 0 when I has square factors.

### Results

nxyx2 - ny2
211-1
3211
521-1
6521
7831
1031-1
111031
13185-1
141541
15411
1741-1
19170391
2155121
22197421
232451
2651-1
297013-1
301121
332341
343561
35611
3761-1
383761
392541
41325-1
421321
474871
515071
5318225-1
5589121
57151201
589913-1
59530691
626381
6581-1
666581
70251301
74435-1
77351401
785361
798091
8291-1
838291
8537841-1
872831
8950053-1
953941

In this primitive search, we cannot find the solutions for n equal

31, 43, 46, 61, 67, 69, 71, 73, 86, 91, 93, 94, 97

Next, expand the search range for x, y up to 10000.

10   ' pell2
20   input N:if moeb(N)=0 then 20
30   '
40   for Y=2 to 10000:Y2=Y^2
50     W=N*Y2-1:X=isqrt(W):if res=0 then print N;X;Y;W-N*Y2:end
60     W=N*Y2+1:X=isqrt(W):if res=0 then print N;X;Y;W-N*Y2:end
70   next Y

Results are following.

nxyx2 - ny2
3115202731
4334825311
462433535881
61297183805-1
674884259671
6977759361
7134804131
731068125-1
861040511221
9115741651
931215112601
975604569-1

Extend the upper bound for y up to 109 and try to find n=94.

94 : 2143295 , 221064 : 1

So, for all n less than 100, we could find the solutions x, y.

previous index next

E-mail : kc2h-msm@asahi-net.or.jp
Hisanori Mishima