在不用连分数展开根号d的情况下，如何知道它的连分数周期的奇偶性？

mathematica

初等数论教材，
上面有
$x^2-dy^2=\pm1$
的解答，
上面用到了连分数的办法，
说是周期是偶数，那么$x^2-dy^2=-1$无解，
如果周期是奇数，那么$x^2-dy^2=-1$有解，
但是有时候，周期很长，计算量很大，有没有简单的办法给出根号d的连分数展开的奇偶性的判定呢？

mathematica

我只知道如果d含有4k+3的因子，那么由二次互反律，-1不是d的剩余，
所以那么周期肯定是偶数，但是这是全部情形吗？
x^2-8y^2=-1
也没有整数解
x^2-20y^2=-1
也没有整数解
没有4k+3因子的数却没解的我列举一下
d可以是
8
20
32
34
40
68
80
99
似乎只要是d=k^2-1就没有解
我就想知道这些数有什么规律？


我猜测d=k^2-1的时候无解，我猜测d=2^k无解，其中k是大于1的奇数

mathematica

mathematica 发表于 2019-3-19 14:27
我只知道如果d含有4k+3的因子，那么由二次互反律，-1不是d的剩余，
所以那么周期肯定是偶数，但是这是全部 ...

1. Clear["Global`*"];(*Clear all variables*)
   
2. (*判定d有无4k+3的因子,如果有,则返回False,否则true*)
   
3. fun[n_]:=Module[{},
   
4.     a=FactorInteger[n];
   
5.     b=#[[1]]&/@a;(*提取素数因子*)
   
6.     c=If[Mod[#,4]==3,1,0]&/@b;(*如果素数因子模4余3,则1,否则0*)
   
7.     If[Total[c]>0,Return[False],Return[True]]
   
8. ]
   
9. Do[out=Reduce[x^2-d*y^2==-1&&x>0&&y>0,{x,y},Integers];
   
10.   (*如果d不是完全平方,且pell无解,且无4k+3因子,则打印出d,并且分解*)
    
11.   If[Not@IntegerQ[Sqrt[d]]&&out==False&&fun[d],Print[{d,FactorInteger[d]}]],
    
12. {d,2,2000}]
    

复制代码

我编写了一个程序，把这些不含有4k+3且不是平方数，且pell方程-1情况下无解的整数都输出了，
大家看看有什么规律！

{8,{{2,3}}}
{20,{{2,2},{5,1}}}
{32,{{2,5}}}
{34,{{2,1},{17,1}}}
{40,{{2,3},{5,1}}}
{52,{{2,2},{13,1}}}
{68,{{2,2},{17,1}}}
{80,{{2,4},{5,1}}}
{104,{{2,3},{13,1}}}
{116,{{2,2},{29,1}}}
{128,{{2,7}}}
{136,{{2,3},{17,1}}}
{146,{{2,1},{73,1}}}
{148,{{2,2},{37,1}}}
{160,{{2,5},{5,1}}}
{164,{{2,2},{41,1}}}
{178,{{2,1},{89,1}}}
{194,{{2,1},{97,1}}}
{200,{{2,3},{5,2}}}
{205,{{5,1},{41,1}}}
{208,{{2,4},{13,1}}}
{212,{{2,2},{53,1}}}
{221,{{13,1},{17,1}}}
{232,{{2,3},{29,1}}}
{244,{{2,2},{61,1}}}
{260,{{2,2},{5,1},{13,1}}}
{272,{{2,4},{17,1}}}
{292,{{2,2},{73,1}}}
{296,{{2,3},{37,1}}}
{305,{{5,1},{61,1}}}
{320,{{2,6},{5,1}}}
{328,{{2,3},{41,1}}}
{340,{{2,2},{5,1},{17,1}}}
{356,{{2,2},{89,1}}}
{377,{{13,1},{29,1}}}
{386,{{2,1},{193,1}}}
{388,{{2,2},{97,1}}}
{404,{{2,2},{101,1}}}
{410,{{2,1},{5,1},{41,1}}}
{416,{{2,5},{13,1}}}
{424,{{2,3},{53,1}}}
{436,{{2,2},{109,1}}}
{452,{{2,2},{113,1}}}
{464,{{2,4},{29,1}}}
{466,{{2,1},{233,1}}}
{482,{{2,1},{241,1}}}
{488,{{2,3},{61,1}}}
{500,{{2,2},{5,3}}}
{505,{{5,1},{101,1}}}
{512,{{2,9}}}
{514,{{2,1},{257,1}}}
{520,{{2,3},{5,1},{13,1}}}
{544,{{2,5},{17,1}}}
{545,{{5,1},{109,1}}}
{548,{{2,2},{137,1}}}
{562,{{2,1},{281,1}}}
{578,{{2,1},{17,2}}}
{580,{{2,2},{5,1},{29,1}}}
{584,{{2,3},{73,1}}}
{592,{{2,4},{37,1}}}
{596,{{2,2},{149,1}}}
{628,{{2,2},{157,1}}}
{640,{{2,7},{5,1}}}
{650,{{2,1},{5,2},{13,1}}}
{656,{{2,4},{41,1}}}
{674,{{2,1},{337,1}}}
{680,{{2,3},{5,1},{17,1}}}
{689,{{13,1},{53,1}}}
{692,{{2,2},{173,1}}}
{706,{{2,1},{353,1}}}
{712,{{2,3},{89,1}}}
{724,{{2,2},{181,1}}}
{725,{{5,2},{29,1}}}
{740,{{2,2},{5,1},{37,1}}}
{745,{{5,1},{149,1}}}
{772,{{2,2},{193,1}}}
{776,{{2,3},{97,1}}}
{788,{{2,2},{197,1}}}
{793,{{13,1},{61,1}}}
{800,{{2,5},{5,2}}}
{802,{{2,1},{401,1}}}
{808,{{2,3},{101,1}}}
{820,{{2,2},{5,1},{41,1}}}
{832,{{2,6},{13,1}}}
{848,{{2,4},{53,1}}}
{850,{{2,1},{5,2},{17,1}}}
{866,{{2,1},{433,1}}}
{872,{{2,3},{109,1}}}
{884,{{2,2},{13,1},{17,1}}}
{890,{{2,1},{5,1},{89,1}}}
{898,{{2,1},{449,1}}}
{904,{{2,3},{113,1}}}
{905,{{5,1},{181,1}}}
{916,{{2,2},{229,1}}}
{928,{{2,5},{29,1}}}
{932,{{2,2},{233,1}}}
{964,{{2,2},{241,1}}}
{976,{{2,4},{61,1}}}
{1000,{{2,3},{5,3}}}
{1028,{{2,2},{257,1}}}
{1040,{{2,4},{5,1},{13,1}}}
{1060,{{2,2},{5,1},{53,1}}}
{1076,{{2,2},{269,1}}}
{1088,{{2,6},{17,1}}}
{1096,{{2,3},{137,1}}}
{1108,{{2,2},{277,1}}}
{1124,{{2,2},{281,1}}}
{1154,{{2,1},{577,1}}}
{1160,{{2,3},{5,1},{29,1}}}
{1168,{{2,4},{73,1}}}
{1172,{{2,2},{293,1}}}
{1184,{{2,5},{37,1}}}
{1186,{{2,1},{593,1}}}
{1192,{{2,3},{149,1}}}
{1202,{{2,1},{601,1}}}
{1205,{{5,1},{241,1}}}
{1220,{{2,2},{5,1},{61,1}}}
{1234,{{2,1},{617,1}}}
{1252,{{2,2},{313,1}}}
{1256,{{2,3},{157,1}}}
{1268,{{2,2},{317,1}}}
{1280,{{2,8},{5,1}}}
{1282,{{2,1},{641,1}}}
{1300,{{2,2},{5,2},{13,1}}}
{1312,{{2,5},{41,1}}}
{1345,{{5,1},{269,1}}}
{1346,{{2,1},{673,1}}}
{1348,{{2,2},{337,1}}}
{1352,{{2,3},{13,2}}}
{1360,{{2,4},{5,1},{17,1}}}
{1384,{{2,3},{173,1}}}
{1394,{{2,1},{17,1},{41,1}}}
{1396,{{2,2},{349,1}}}
{1405,{{5,1},{281,1}}}
{1412,{{2,2},{353,1}}}
{1424,{{2,4},{89,1}}}
{1448,{{2,3},{181,1}}}
{1460,{{2,2},{5,1},{73,1}}}
{1469,{{13,1},{113,1}}}
{1480,{{2,3},{5,1},{37,1}}}
{1492,{{2,2},{373,1}}}
{1508,{{2,2},{13,1},{29,1}}}
{1513,{{17,1},{89,1}}}
{1517,{{37,1},{41,1}}}
{1537,{{29,1},{53,1}}}
{1538,{{2,1},{769,1}}}
{1544,{{2,3},{193,1}}}
{1552,{{2,4},{97,1}}}
{1556,{{2,2},{389,1}}}
{1576,{{2,3},{197,1}}}
{1588,{{2,2},{397,1}}}
{1604,{{2,2},{401,1}}}
{1616,{{2,4},{101,1}}}
{1636,{{2,2},{409,1}}}
{1640,{{2,3},{5,1},{41,1}}}
{1664,{{2,7},{13,1}}}
{1684,{{2,2},{421,1}}}
{1690,{{2,1},{5,1},{13,2}}}
{1696,{{2,5},{53,1}}}
{1700,{{2,2},{5,2},{17,1}}}
{1717,{{17,1},{101,1}}}
{1732,{{2,2},{433,1}}}
{1744,{{2,4},{109,1}}}
{1762,{{2,1},{881,1}}}
{1768,{{2,3},{13,1},{17,1}}}
{1780,{{2,2},{5,1},{89,1}}}
{1796,{{2,2},{449,1}}}
{1802,{{2,1},{17,1},{53,1}}}
{1808,{{2,4},{113,1}}}
{1828,{{2,2},{457,1}}}
{1832,{{2,3},{229,1}}}
{1844,{{2,2},{461,1}}}
{1856,{{2,6},{29,1}}}
{1858,{{2,1},{929,1}}}
{1864,{{2,3},{233,1}}}
{1874,{{2,1},{937,1}}}
{1885,{{5,1},{13,1},{29,1}}}
{1924,{{2,2},{13,1},{37,1}}}
{1928,{{2,3},{241,1}}}
{1940,{{2,2},{5,1},{97,1}}}
{1945,{{5,1},{389,1}}}
{1952,{{2,5},{61,1}}}
{1954,{{2,1},{977,1}}}
{1961,{{37,1},{53,1}}}
{1972,{{2,2},{17,1},{29,1}}}
{2000,{{2,4},{5,3}}}

mathematica

mathematica 发表于 2019-3-19 15:17
我编写了一个程序，把这些不含有4k+3且不是平方数，且pell方程-1情况下无解的整数都输出了，
大家看 ...

除掉偶数，就剩下下面的情况
{205,{{5,1},{41,1}}}
{221,{{13,1},{17,1}}}
{305,{{5,1},{61,1}}}
{377,{{13,1},{29,1}}}
{505,{{5,1},{101,1}}}
{545,{{5,1},{109,1}}}
{689,{{13,1},{53,1}}}
{725,{{5,2},{29,1}}}
{745,{{5,1},{149,1}}}
{793,{{13,1},{61,1}}}
{905,{{5,1},{181,1}}}
{1205,{{5,1},{241,1}}}
{1345,{{5,1},{269,1}}}
{1405,{{5,1},{281,1}}}
{1469,{{13,1},{113,1}}}
{1513,{{17,1},{89,1}}}
{1517,{{37,1},{41,1}}}
{1537,{{29,1},{53,1}}}
{1717,{{17,1},{101,1}}}
{1885,{{5,1},{13,1},{29,1}}}
{1945,{{5,1},{389,1}}}
{1961,{{37,1},{53,1}}}
可是这些数有什么规律呢？

mathematica

我就是想知道，在不展开连分数的情况下，有没有类似二次互反律判定二次同余方程是否有解的简单办法

kastin

mathe 曾在求sqrt(n)连分数展开的周期的奇偶性这个帖子中（你当时也参与讨论过这个问题）提到了一篇论文研究了这个问题：The continued fractions of the square roots of integers：on the parity of the length of their period