整数分解随笔(六)

scsongls

         整数分解随笔(六)

本次文中未注明处，n≥3，且为奇数。
一、平方剩余相邻两数除法的唯一性及互逆间的相互相关性:

  1、相邻两数除法的唯一性
      在随笔word版中，曾经推出相邻两数平方剩余除法的一个公式，这里把公式重新整理一下。
     设a^2≡b(mod n)，根据公式可知:
      c≡(a-1)/(b-1) (mod n)     =>
      c^2≡d，(c+1)^2≡bd (mod n)
      即根据a^2≡b(mod n)可以反推出该平方剩余是由哪两个相邻数相除得到，其中a、b、c∈(1，n-1)，而且是唯一的。
    以下证明唯一性:
    设a^2≡b(mod n)，(c+1)/c≡a(mod n)，如果不唯一，即还存在另外一个相邻数的平方剩余(d+1)/d≡a(mod n)，可得:
    (c+1)/c≡(d+1)/d (mod n)   =>
    c≡d (mod n)
    这里a、b、c、d∈[1，n-1]
    即平方剩余的除法具有唯一性。
    现在再对相邻两数平方剩余的除法进行相应的变化。
    设a^2≡b(mod n)，(a+1)^2≡c(mod n)，两式相除得:
    ((a+1)/a)^2≡c/b(mod n)    =>
    (1+1/a)^2≡j(mod n)  这里j≡c/b(mod n)
   
   如果两式相乘得:
    (a^2+a)^2≡bc(mod n)     =>
    (a+b)^2≡bc(mod n)
    又∵j≡c/b(mod n)
    ∴上式变为:  (a+b)^2≡jb^2(mod n)  =>
       (1+a/b)^2≡j(mod n)
     当然也可以由a^2≡b(mod n)   =>
       a/b≡1/a(mod n)，其中(a，n)=1
     得到上面两式是相等的。
     举例说明三个公式:
     例1、60^2≡12(mod 299)
      a≡(60-1)/(12-1)≡59/11≡250(mod 299)
      250^2≡9(mod 299)
      251^2≡108(mod 299)
      其中  9*12≡108(mod 299)

     1+1/a≡60(mod 299)    =>
     a≡1/59(mod 299)        =>
     a≡223(mod 299)
     223^2≡95(mod 299)
     224^2≡243(mod 299)
     其中 95*12≡243(mod 299)

     1+a/b≡60(mod 299)    =>
     a≡59b(mod 299)
     ∵a^2≡b(mod 299)
     ∴59^2*b≡b(mod 299)  =>
       192b≡1(mod 299)      =>
       b≡95(mod 299)
       a≡59*95≡223(mod 299)
     
   2、互逆间相互相关性
      在上例中，60^2≡12(mod 299)，与该平方剩余互逆的为 5^2≡25(mod 299)，因为5*60≡1(mod 299)，25*12≡1(mod 299)，所以这组平方剩余是互逆。
      设(a-1)^2≡b1(mod n)  a^2≡b2(mod n)  (a+1)^2≡b3(mod n)
      (c-1)^2≡d1(mod n)  c^2≡d2(mod n)  (c+1)^2≡d3(mod n)
       如果a^2≡b2(mod n)与c^2≡d2(mod n)是互逆，即a*c≡1(mod n)  b2*d2≡1(mod n)，那么b2*d1≡b1(mod n)，b2*d3≡b3(mod n)
      d2*b1≡d1(mod n)，d2*b3≡d3(mod n)
    即a-1，a，a+1与c-1，c，c+1是相互相关的(证明略)。
     现在举例说明(为节省篇幅，省略(mod 299)):
     例2: n=299=13*23
      4^2≡16   5^2≡25  6^2≡36
      59^2≡192  60^2≡12  61^2≡133
      因为5^2≡25与60^2≡12是互逆的，可以得到以下式子:
     25*192≡16     25*133≡36
     12*16≡192     12*36≡133
     这样可以把(4，5，6)与(59，60，61)称为互逆间相互相关性。

    53^2≡118   54^2≡225   55^2≡35
    71^2≡257   72^2≡101   73^2≡246
    ∵54*72≡1    225*101≡1
    ∴225*257≡118   225*246≡35
         101*118≡257   101*35≡246
     即(53，54，55)与(71，72，73)具有相互相关性。

     以上是相邻间相互相关性，如果不相邻(以例说明，不推公式)，看以下例(以60^2≡12(mod 299)为例):
    58^2≡75   60^2≡12  62^2≡256，与60相差2
   相互关联性为:
    9^2≡81   10^2≡100   11^2≡121，即60的互逆数5的倍数，10=5*2
   12*81≡75    12*121≡256
   25*75≡81    25*256≡121
   因此(60-2，60，60+2)与(2*5-1，2*5，2*5+1)是相互相关的。
   也可以推出60与5互逆相间之间的关系:
   (60-j，60，60+j)与(j*5-1，j*5，j*5+1)是互逆间的相互相关性，j≥1。
   一般式为:
   (a-j，a，a+j)与(j*c-1，j*c，j*c+1)是相互相关性，其中a*c≡1(mod n)，j≥1
   a^2*(j*c-1)^2≡(a-j)^2(mod n)
   a^2*(j*c+1)^2≡(a+j)^2(mod n)
   c^2*(a-j)^2≡(j*c-1)^2(mod n)  
   c^2*(a+j)^2≡(j*c+1)^2(mod n)
   

scsongls

  二、相邻两平方剩余的乘法
  设a^2≡b(mod n)，(a+1)^2≡c(mod n)，a+b≡d(mod n)，其中d=j(j+1)，d^2≡f(mod n)，相邻两平方剩余相乘得:
  (a(a+1))^2≡bc(mod n)    =>
  (a+b)^2≡bc(mod n)
  而c≡2a+1+b(mod n)  代入得:
  (a+b)^2≡b(2a+1+b)(mod n)   =>
  (a+b)^2≡2ab+b+b^2 (mod n)
  又∵d=a+b =>a=d-b   且d^2≡f(mod n)，代入上式得:
  2ab+b+b^2≡f(mod n)   =>
  b^2-(2d+1)b+f≡0(mod n)  =>
  b^2-(2j(j+1)+1)b+f≡0(mod n)  ①
  对于上式，一定有一个已知解，即s^2≡s^2(mod n)，s<√n，但根据上面一元二次方程在平方剩余中如何求另外一个解，目前不清楚，以下举例说明:
   n=299:
   72^2≡101(mod 299)
   72=8*9 其中一个解为:
   8^2≡64(mod 299)，代入①得
   b^2-145b+101≡0 (mod 299)
   当b=64时，上式成立，但另一解d=12也成立，但无法求出。

scsongls

  三、连续两整数之和与之积的性质
   1、相邻两整数之和与n因子的关系
    先看例，再说明。
    例1、n=299=13*23
     6+7=13       11+12=23
     19+20=39   32+33=65
     …
     上述相邻两整数之和皆与299有因子关系，这样的原因是什么?下面来说明:
     设n为奇数(这里只证明n=4k-1，4k+1也是相同情况，不再证明)，n=4k-1，a∈[1，(n-1)/2]，a^2≡b(mod n)，如果gcd(a，n)>1，则其对称数及其对称数减1之和与n也必有因子。
   证明:  a^2≡b(mod n)
       其对称数为: 2k-a
       其对称数减1为: 2k-a-1
       相邻两数之和为:2k-a+2k-a-1=4k-1-2a
       4k-1-2a≡-2a(mod n)
       ∵gcd(a，n)>1
       ∴gcd(-2a，n)>1
      证毕。
      上例中，19+20=39与299有13的因子，是因为20的对称数130与299有13的同子关系，其它数请自行验证。
     2、一定条件下整数分解
     以下讨论在一定条件下部份整数的分解方法，暂时只讨论n=4k-1，不讨论n=4k+1。
     ⑴  设n为合数且n=4k-1，a^2≡b(mod n)，如果a+b≡k(mod n)，或者a(a+1)≡k(mod n)，则(2a+1)^2≡2(mod n)
    证明:  ∵ a+b≡k(mod n)  => b=k-a(mod n)  
         代入 a^2≡b(mod n)  得
          a^2≡k-a(mod n)      (同乘4)    =>
          4a^2≡4k-4a(mod n)     =>
          4a^2+4a+1≡4k+1(mod n)   =>
          (2a+1)^2≡1+1=2(mod n) 证毕。
          例2: n=527=4*132-1  
            k=132=11*12   =>
            (11+12)^2=23^2≡2(mod 527)

     ⑵  设n为合数且n=4k-1，a^2≡b(mod n)，如果a+b≡2k(mod n)，或者a(a+1)≡2k(mod n)，则(2a+1)^2≡3(mod n)
    证明:  ∵ a+b≡2k(mod n)  => b=2k-a(mod n)  
         代入 a^2≡b(mod n)  得
          a^2≡2k-a(mod n)      (同乘4)    =>
          4a^2≡2*4k-4a(mod n)     =>
          4a^2+4a+1≡2*4k+1(mod n)   =>
          (2a+1)^2≡2+1=3(mod n) 证毕。
       例3:n=1403=4*351-1
       2k=2*351=702=26*27     =>
       (26+27)^2=53^2≡3(mod 1403)
   
     可以推出更一般的公式:
     ⑶ 设n为合数且n=4k-1，如果jk=a(a+1)，j≥1，则(2a+1)^2≡j+1(mod n)
    证明略。

    在上面一般式中，当j=3时，可得(2a+1)^2≡4(mod n)，对这种条件下的整数是可以进行分解的，即:
    对于连续两个整数之积，只要其中一个整数是3的倍数，都可以表式为:
   a(a+1)=3k   或者k=(a(a+1))/3
   又∵n=4k-1，这种条件下这类整数就能分解，下面举例来说明:
    例4:
    ①  8*9=72=3*24   =>
         n=4*24-1=95
         (8+9)^2≡4(mod 95)   =>  
         17^2≡4(mod 95)
    ②  9*10=90=3*30  =>
         n=4*30-1=119
       (9+10)^2≡4(mod 119)   =>
         19^2≡4(mod 119)
    ③  24*25=600=3*200  =>
         n=4*200-1=799
         (24+25)^2≡4(mod 799)   =>
         49^2≡4(mod 799)
       …

     如果在一般式中，j=8，根据公式得2a+1)^2≡9(mod n)
      例5:
       ① n=299，k=75
        8*75=600=24*25
        ∴(24+25)^2=49^2≡9(mod 299)
       ② n=527，k=132
         8*132=1056=32*33
         ∴(32+33)^2=65^2≡9(mod 527)
          …

      例6: n=1199=4*300-1
       ∵(n+1)^2≡k(mod n)
       ∴600^2≡300(mod 1199)   =>
            60^2≡3(mod 1199)
         2k=600=24*25     =>
         (24+25)^2=49^2≡3(mod 1403)
         ∴60^2≡49^2(mod 1403)
      目前只能得到连续整数积为3、8、15…j^2-1这类倍数条件下的分解，当然该方法只限于n=4K-1型，对于n=4k+1还在探索中，有结果将尽快补充，如果你有什么好的建议，请提出来，本人十分感谢!