二次剩余中的完全平方与连续两个整数积的关系

scsongls

本文介绍合数的二次剩余中的完全平方与连续两个整数积的相关性及与因子中1、2的关系(本文只讨论n=4k-1，n=4k+1有相同性质，这里不讨论) ：
一、二次剩余值中完全平方与连续整数积之间的关系
设n=4k-1，n=ab  b>a>1,  n为整数  
    对于k，有c^2-k=i(i+1) => (2c)^2≡(2i+1)^2 (mod n)    ①
    其中c与k同奇同偶，i≥0
    对于①式中的c和2i+1，以下看看其它的一些性质
   ①式两边同时除以4得  c^2≡(1/2+i)^2 (mod n)  ②
    ②式两边乘以偶数2j或奇数2j+1，j>0，如得到如下公式:
1、②式两边同时乘以偶数(2j)^2得  (2jc)^2≡(2ji+j)^2 (mod n)   与2jc相差2i+1的二次剩余值正好相对于c的完全平对称方值:
   (2jc-(2i+1))^2≡(c-(2ji+j-c))^2 (mod n)
2、②式两边同时乘以奇数(2j+1)^2得  ((2j+1)c)^2≡(1/2*(2j+1)+(2j+1)i)^2 (mod n) ，该二次剩余值为一个二次剩余的后序序列值，与(2j+1)c相差2i+1的二次剩余值   ((2j+1)c-(2i+1))^2也在后序序列上
  (具体证明可参考之前本人的伪单元e^2≡1(mod n)相关证明，此时把e换成2c，1换成2i+1即能证明)
    而乘以奇数 (2j+1)c 与乘以偶数的两个值 2jc相差 (a-1)/2或(a+1)/2，即为1/2的值，
    ①式中c与k最近的值和2i+1与a、b的关系为:  c=(a+b)/2    2i+1=(b-a)/2
以下举例说明。

例如：n=299=13*23=4*75-1   9^2-75=2*3  => 18^2≡5^2 (mod 299)
    可得  c=9 和 2i+1=5  
  两边同时乘以偶数4^2得  (9*2*2)^2≡(2*5)^2 => 36^2≡10^2      (36-5)^2≡(9-(10-9)^2 => 31^2≡8^2 (mod 299)
  即以c=9两边的对称
  两边同时乘以偶数6^2得  (9*2*3)^2≡(5*3)^2 => 54^2≡15^2 (mod 299)     (54-5)^2≡(9-(15-9))^2 => 49^2≡3^2 (mod 299)
  两边同时乘以奇数3^2得  (9*3)^2≡(3/2+3*5)^2 => 27^2≡131 (mod 299)     (27-5)^2≡185 => 22^2≡185 (mod 299)   131与185在后序序列中相差1+2=3(25^2≡27 => 25^2≡25+1*2(mod 299)
  两边同时乘以奇数5^2得  (9*5)^2≡(5/2+5*5)^2 => 45^2≡231(mod 299)      (45-5)^2≡105 => 40^2≡105 (mod 299)  231与105在后序序列中相差3+4=7(43^2≡55 => 43^2≡43+3*4 (mod 299)
        而  25-18=7=(13+1)/2

  以下举例说明d^2≡d+j(j+1)(mod n)与n=ab中，a和b的1/2关系(因连续整数积与1/2相关):
        43^2≡55=43+3*4   (43-5)^2≡38^2≡248≡38+210≡38+14*15 (mod 299)
        对于36^2≡10^2和49^2≡3^2(mod 299)两个前序序列的二次剩余与43^2≡55(mod 299)的关系为  49-43=6=(13-1)/2    43-36=7=(13+1)/2 即为小数a的1/2处
          同时这两个平法剩余值的和为n的小因子a： 10+3=13
          而36-3=33和 49-3=46 正好为a/2  
        对于31^2≡8^2(mod 299)和54^2≡15^2(mod 299)两个前序序列的二次剩余与43^2≡55(mod 299)的关系为  54-43=11=(23-1)/2    43-31=12=(23+1)/2 即为大数b的1/2处
          同时这两个平法剩余值的和为n的大因子b： 8+15=23
          而31+4=35和 54+4=58 正好为b/2   
        对于31^2≡8^2(mod 299)和44^2≡21^2(mod 299)两个前序序列的二次剩余与38^2≡248(mod 299)的关系为  44-38=6=(13-1)/2    38-31=7=(13+1)/2 即为小数a的1/2处
        对于26^2≡78(mod 299)和49^2≡3^2(mod 299)两个前序序列的二次剩余与38^2≡248(mod 299)的关系为  49-38=11=(23-1)/2    38-26=12=(23+1)/2 即为大数b的1/2处

二、完全平方与连续整数积在(sqrt(n),sqrt(3n))的关系及与a得相关性
设 n=4k-1 n=ab  2a>b>a>1   n为整数，二次剩余范围n<d^2<3n
  在上述设定条件下，在a值不变情况下，b值的变化，对完全平方及该连续两个整数积的变化。这里先设定b值为一个特殊值:
   b=a+(a+1)/2或者 b=a+(a-1)/2
   此时，可以得到如下值:
   在(n，2n)范围内有完全平方数:
        (2c)^2≡((a-1)/4)^2(mod n)
     或 (2c)^2≡((a-1)/4)^2(mod n)
   在(2n，3n)范围内有连续两个整数积:
        d^2≡d+((a+1)/4 -1)((a+1)/4)((mod n)
     或 d^2≡d+((a-1)/4)((a-1)/4 +1)(mod n)
      改成一般式为  d^2≡d+j(j+1) (mod n) ( j ≥ 0
    即完全平方值与其中一个连续整数积值的和等于a的1/2(注:在上述设定中有b<2a，如果2a<b，则完全平方值与其中一个连续整数积值的差等于a的1/2)
  如果b值在(a，2a)范围内变动时，完全平方值与其中一个连续整数积值的和等于a的1/2是不变，b值往a方向变动时，完全平方值变小，而其中一个连续整数积的值变大，b值往2a方向变动时，完全平方变大，其中一个连续整数积的值变小，但其和仍然等于a的1/2。按一般式可得  2c+(j+1) = a/2 。(a/2、b/2与n/2同余相同，一般的，a/j、 b/j与n/j同余相同  j≥2)
  以下举例说明
   例如以a=131为例，按上述设定有:
     b=131+(131+1)/2=197
n=131*197=25807
   (2c)^2=164^2≡(131+1)/4)^2=33^2(mod 25807)
   230^2≡230+32*33(mod 25807)
   其中33+33=66正好等于a/2
   164+33=197正好等于a/2
   根据上节，也可以算出另一个二次剩余完全平方值为：
   (230+65)^2≡(131-33)^2 => 295^2≡98^2(mod 25807)

   n=20567=131*157
    此时b=157，往a方向变动
     (2c)^2=144^2≡13^2(mod 20567)
     210^2≡210+52*53(mod 20567)
     其中13+53=66正好等于a的1/2
     144+53=197 正好等于a的1/2   
    根据上节，也可以算出另一个二次剩余完全平方值为：
    (210+65)^2≡(131-13)^2 => 275^2≡118^2(mod 20567)

    n=29999=131*229
      此时b=229，往向变2a方向变动
      (2c)^2=180^2≡49^2(mod 29999)
      246^2≡246+16*17(mod 29999)
      其中49+17=66正好等于a的1/2
      180+17=197 正好等于a的1/2
     根据上节，也可以算出另一个二次剩余完全平方值为：
     (246+65)^2≡(131-49)^2 => 311^2≡82^2(mod 29999)

三、总结
   对于上述合数二次剩余完全平方与两个连续整数积的关系，可能存在问题和不足，欢迎大家批评指正（附件为上述内容的pdf，便于阅读）。