[原创]整数分解随笔(五)

设a^2≡b (mod n),(a+1)^2≡c (mod n),则(a+b)^2≡bc (mod n)
证明：∵ (a+1)^2≡c (mod n)   
                    a^2≡b (mod n)
   上面两式相乘：(a(a+1))^2≡bc (mod n)
         ==>        (a^2+a)^2≡bc (mod n)
         ==>        (a+b)^2≡bc (mod n)
      证毕。（该公式在以后中将直接引用）
   
本次文中我们来探讨一类整数平方剩余的规律，该类整数平方剩余都有一个特点，必有一个数的平方剩余为2，即a^2≡2 (mod n)，该类数最典型的代表为梅森数，因为这类整数平方剩余都有一定的规律，希望从这些规律中去寻找分解的方法或公式，更希望能从这类整数的分解方法或公式中去找寻一般的分解方法。本次文中n=2^j-1，其中j=2m+1，m>=1。当j为素数时，n为梅森数，但n不为梅森素数。平方剩余范围未加说明，均在[1,(n-1)/2]。本次文中未加说明的字母均为大于等于1。
一、n平方剩余的一些公式
    对于n这类的整数，皆为4k-1型，其中k=2^(j-2)，有如下的平方剩余公式(因书写原因，以下公式不提供证明，在后面的示例中加以说明，还有一些公式未列出，一并在示例中说明)：
      公式1、(2^((j+1)/2)))^2≡ 2 (mod n)
      公式2、(h*2^((j+1)/2))-1)^2≡ 2*(2^((j-1)/2))-h)^2 (mod n)
            (h*2^((j+1)/2))+1)^2≡ 2*(2^((j-1)/2))+h)^2 (mod n)
     公式3、设(t*2^((j+1)/2)+s)^2≡b (mod n)
        则 2(t+s*2^((j-1)/2))^2≡b (mod n)
          .
          .
          .
    证明略。
   
  二、以例说明上述公式
     
    例1  511=2^9-1(见后面所附平方剩余)
    ①  这里n=511， j=9
      k=2^(9-2)=2^7=128
     ((n-1)/2)^2≡((511-1)/2)^2≡255^2≡128 (mod 511)(请参考随笔1)
     (9+1)/2=5，2^5=32
     32^2≡2 (mod 511)   公式1
     (9-1)/2=4，  2^4=16
     (9-3)/2=3，  2^3=8
     2^((j-1)/2)=2^((9-1)/2)=2^4=16
     2^((j-3)/2)=2^((9-3)/2)=2^3=8
    ② 由公式2得到如下的平方剩余：
     当h=1   (32*1)^2≡2*1 (mod 511)
      第1个公式左边： (1*32-1)^2=31^2
      第1个公式右边：2*(16-1)^2=2*15^2=2*225=450  (mod 511)
      即  31^2≡450  (mod 511)
      第2个公式左边： (1*32+1)^2=33^2
      第2个公式右边：2*(16+1)^2=2*17^2=2*289=578≡67 (mod 511)
      即  33^2≡67 (mod 511)
      把这三个数整理得：
      31^2≡450 , 32^2≡2 , 33^2≡67
      当然根据上面三式观察可得：
              31^2≡450=2*15^2 (mod 511)
              33^2≡67  (mod 511)  =>
              33^2≡67+511  (mod 511)  =>
              33^2≡578   (mod  511)  =>
              33^2≡2*289  (mod  511)  =>
              33^2≡2*17^2 (mod 511)
              其中15+17=32
     当h=2   (32*2)^2≡2*4 (mod 511)
       (2*32-1)^2=65^2≡2*(16-2)^2=2*14^2=2*144=288  (mod 511)
   (2*32+1)^2=67^2≡2*(16+2)^2=2*18^2=2*324=648≡137 (mod 511)
           其中 14+18=32
     当h=3   (32*3)^2≡2*9 (mod 511)
       (3*32-1)^2=95^2≡2*(16-3)^2=2*13^2=2*169=338  (mod 511)
   (3*32+1)^2=97^2≡2*(16+3)^2=2*19^2=2*361=722≡211 (mod 511)
          其中 13+19=32
     .
     .
     .
     请看以下所附数据：
     31^2≡450 , 32^2≡2 , 33^2≡67
     63^2≡392 , 64^2≡8 , 65^2≡137
     95^2≡338 , 96^2≡18 , 97^2≡211
     127^2≡288 , 128^2≡32 , 129^2≡289
     159^2≡242 , 160^2≡50 , 161^2≡371
     191^2≡200 , 192^2≡72 , 193^2≡457
     223^2≡162 , 224^2≡98 , 225^2≡36
     255^2≡128 , 256^2≡128 , 257^2≡130
  
      这里129^2≡289 (mod 511)，而289+511=800=400*2，这个完全平方该如何找，目前还不清楚，当然这种情况也未证明。
       再列举一组数据:
        31^2≡450=2*15^2，32^2≡2，33^2≡67≡578=2*17^2
        63^2≡392=8*7^2，64^2≡8，65^2≡137≡648=8*9^2
        127^2≡288=32*3^2，128^2≡32，129^2≡289≡800=32*5^2
         (证明略)