整数分解随笔(k与3同余关系得到二次剩余值与3的同余)

scsongls

       根据k与3的同余得到二次剩余值与3的同余
     本次文介绍n=4k-1，费马分解的两个值与后序序列的连续两个整数枳的关系，以及在k≡0(mod 3)、k&#8802;0(mod 3)时，a^2≡b(mod n)，√n<a<√(2n)，b与3的整除关系。

一、后序序列连续两个整数积与费马分解值的关系
设n=4k-1，n=ab，1<a<b，根据费马分解有:t^2≡s^2(mod n)，其中:
  t=(a+b)/2，s=(b-a)/2     
因n=4k-1，则a=4ka+1，b=4kb-1，或者a=4ka-1，b=4kb+1
  n=ab=(4ka+1)(4kb-1)=16ka*kb-4ka+4kb-1=4(4ka*kb-ka+kb)-1，即
  k=4ka*kb-ka+kb，上式必为4k-1型
又因为根据后序序列有:
  c^2-k=i(i-1)   ⅰ≥1    ①  
=﹥ (2c)^2≡(2ⅰ-1)^2(mod n)
   此时2c、2ⅰ-1与t、s的关系为
   2c=t，2ⅰ-1=s
以下来证明
  ∵  k=4ka*kb-ka+kb，要想①式的右边为连续整数积，则:
  c=ka+kb，代入上式左边有:
  (ka+kb)^2-(4ka*kb-ka+kb) =
(ka)^2+2ka*kb+(kb)^2-4ka*kb+ka-kb  =
(ka-kb)^2-(kb-kba ) =
  (kb-ka)(kb-ka-1)为连继两个整数积
∴ (2(ka+kb))^2≡2(kb-ka)-1)^2(mod n)
  ∵t=(a+b)/2=(4ka+1+4kb-1)/2=2(ka+kb)
  s=(b-a)/2=(4kb-1-4ka-1)/2=2(kb-ka)-1
  也即2c=t ，  2i-1=s


二、k≡0(mod 3)及k&#8802;0(mod 3)时，t与s和3的整除关系
㈠ 、从后序序列证明t、s与3的同余关系
设n=4k-1，n=ab，1<a<b，根据费马分解有: t^2≡s^2(mod n)，其中:
    t=(a+b)/2   s=(b-a)/2
  再设定(n，3)=1，(t，s)=1，有
   如果k≡0(mod 3)，则t≡0(mod 3)
   如果k&#8802;0(mod 3)，则s≡0(mod 3)
  证明如下:
  1、当k≡0(mod 3)，可表示为k=3d
则c可表示为3g、3g±1，分别代入①式中有:
   ⑴、c≡0(mod 3)，即c=3g有
    (3g)^2-3d，可知①式右边必为3的倍数3f，即:
  (3g)^2-3d=3f(3f±1)，等式两边都存在3的倍数，上式成立
  根据笫一段可得: (6g)^2≡(6f±1)^2(mod n)，也即:
  t=6g  => t≡0(mod 3)
  ⑵、c&#8802;0(mod 3)，可令c=3g±1，代入①式可表示为:
(3g±1)^2-3d=(9g^2±6g-3d)+1，该式不为3的倍数，而ⅰ不为3的倍数连续两个整数积的表达为:
  (3f+1)(3f+2)=9f^2+9f+2   =>
(9g^2±6g-3d)+1≠9f^2+9f+2 =>
  9g^2±6g-3d≠9f^2+9f+1
左边为3的倍数，右边不是3的倍数，该等式不成立
  ∴ 根据上述情况可知:
     当k≡0(mod 3)，则t≡0(mod 3)
2、当k&#8802;0(mod 3)时，s≡0(mod 3)
  此时k分别表示为3d+1，3d-1，
  ⑴、当 k=3d+1，代入n得:
   4(3d+1)-1=12d+3，n必为3的倍数，与题设(n，3)=1不符，舍去。
  ⑵、当k=3d-1时，根据c与3是否能整除，可分为以下情况:
  Ⅰ、当c≡0(mod 3)时，可令c=3g，代入①式得:
(3g)^2-(3d-1)，结果不是3的倍数，等式右边必为(3f+1)(3f+2)，可得:
  9g^2-3d=9f^2+9f+3，该式可以成立。根据第一段可得
  (6g)^2≡(6f+3)^2(mod n)
此时(t，s)=3，与题设不符，舍去。
  Ⅱ、当c&#8802;0(mod 3)时，可令c=3g±1，代入①式
  (3g±1)^2-(3d-1)=9g^2±6g-3d+2
结果不为3的倍数，等式右边只能为(3f+1)(3f+2)=9f^2+9f+2，即:
  9g^2±6g-3d+2=9f^2+9f+2，该结果成立
根据笫一段可得:
  (6g±2)^2≡(6f+3)″2 (mod n)
   此时:s=6f+3 => s≡0(mod 3)
  ∴∴综上述可知:
     当k&#8802;0(mod 3)，则s≡0(mod 3)


㈡、从前序序列证明c^2≡d(mod n)中d与3的同余关系
  设n=4k-1，n=ab，1<a<b，(n，3)=1，c^2≡d(mod n)，√n<c<√(2n)
以下分别讨论当d≥0和d<0这两种情况下，d与3的整除结果。
   ⑴ 、当d≥0时
   Ⅰ、如果 k≡0(mod 3)， 则有d&#8802;0(mod 3)
   Ⅱ、如果k&#8802;0(mod 3)，根据c与3的整关系，有以下两种结果:
      当c≡0(mod 3)，有d&#8802;0(mod 3)   
      当c&#8802;0(mod 3)，有d≡0(mod 3)
下面来分别证明。
二次剩余值: d=c^2-n=c^2-(4k-1) ②
1、当k≡0(mod 3)，可设k=3f
     Ⅰ、当c≡0(mod 3)，令c=3g，代入②式得:
  (3g)^2-(12f-1)=3(3g^2-4f)+1，即
  c^2-(4k-1)≡1(mod 3)  =>
      d≡1(mod 3)   即:
       d&#8802;0(mod 3)
    Ⅱ、当c&#8802;0(mod 3)时，令c=3g±1，代入②式得
(3g±1)^2-(12f-1)=3(3g^2±2g-4f)+2，即
  c^2-(4k-1)≡2(mod 3)  =>
     d≡2(mod 3)，  即:
      d&#8802;0(mod 3)
综合上述两种情况，得:
   当k≡0(mod 3)时， 有d&#8802;0(mod 3)

   当k&#8802;0(mod 3) 时， k可分别表示为:3f-1和3f+1，以下分别证明
2、当k=3f-1时，即k≡-1(mod 3)
   Ⅰ、当c≡0(mod 3时，令c=3g，代入②式得:
(3g)^2-(12f-5)=3(3g^2-4f)+5，即
  c^2-(4k-1)≡2(mod 3)
  即   d&#8802;0(mod 3)
   Ⅱ、当c&#8802;0(mod 3)时，  c=3g±1，代入②式得
  (3g±1)^2-(12f-5)&#8802;=3(3g^2±2g-4f+2) 即
  c^2-(4k-1)≡0(mod 3)
   即  d≡0(mod 3)
3、当k=3f+1，即k≡1(mod 3)，4(3f+1)-1=12f-3，此时(n，3)=3，与题设不符，舍去。
  根据上述可知:
  当k&#8802;0(mod 3)  时，分为以下两种情况:
   当c≡0(mod 3)时，有d&#8802;0(mod 3)   
   当c&#8802;0(mod 3)时，有d≡0(mod 3)
⑵、当d<0时，则有:
Ⅰ、如果k≡0(mod 3)，有以下两种结果:
      当c&#8802;0(mod 3)，有d≡0(mod 3)
      当c≡0(mod 3)，有d&#8802;0(mod 3)
Ⅱ、如果k&#8802;0(mod 3)，则d&#8802;0(mod 3)
证明略。

三、小结
  以上分别就n=4k-1型整数时，说明了k与3的整除关系，可得到二次剩值与3的整除结果，当然上述论述也会存在不足，欢迎大家批评指正。