整数分解随笔(六)

本次文中未注明处，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)

[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课