整数分解随笔(二)

scsongls · 发表于 2014-12-22 20:35

本文中的一些概念请参考  http://www.mathchina.com/bbs/for ... w=my&type=reply

   整数分解随笔(二)

一、对中间数的证明
① n=4k-1
Sj=1+2+3+…+2j-1=j^2
Si=i(i+1)+k
当Sj=Si时，即j^2=i(i+1)+k，要使该式成立，当j=k，i=k-1时，该式成立
  j^2-i(i+1)=k
  j^2-i^2 - i= k
  (j+i)(j-i) = k+i
  当 j-i =1,且j=k时上式成立
即中间数相交于k
② n=4k+1
Sj=1+2+3+…+2j-1=j^2
Si=i(i+1)+n-k-2k=i(i+1)+n-3k
  j^2 - i(i+1)=n-3k
  (j+i)(j-i)=n-3k+i
  当j-i=1,j=n-3k时上式成立
  即中间数相交于n-3k=4k+1-3k=k+1

二、整数的完全平方数
  完全平方数的判断目前都没有最直接的方法，都是先开方得到一个数，然后该数平方看是否与原来的数相等，如果相等则为完全平方教，否则不是完全平方数。
  本节只讨论奇完全平方数，偶数的完全平方数本文不讨论。
  设n=2k+1 (k>0)，则
n^2=(2k+1)^2=(k+k+1)^2=4k^2+4k+1=4k(k+1)+1       Ⅰ
  从上式可以知道了，奇数的完全平方必为8m+1，因为上式中k(k+1)是连续两个整数的积，必然一个为奇数，一个为偶数。从上式也知道连续两个数和的平方必为这两个连续整数积的4倍加1，来看以下例：
5+6=11^2=121=4*5*6+1
10+11=21^2=441=4*10*11+1
15+16=31^2=961=4*15*16+1

如果要判断一个数是否为完全平方数，可以把该数减1除4，再对该结果进行开方，对开方结果的相邻两数积，即可知道是否为完全平方数。如：
729=4×182+1
∵182：√182≈13 ,13×(13+1)=182
∴729=(13+14)^2=27^2

5929=4×1482+1
∵1482:√1482≈38 ,38×(38+1)=1482
∴5929=(38+39)^2=77^2

   1361=4×340+1
∵340:√340≈18 ,18×(18+1)=342
∴1361不是完全平方数

scsongls · 发表于 2014-12-22 20:36

三、平方剩余的一些性质
  以下文中n为奇数。
① n=4k-1
当n=4k-1时，a^2≡b (mod n)，先看一个例91，91的平方剩余如下(91=4×23-1，9<a≤45)：
91
10^2≡9 , 11^2≡30 , 12^2≡53 , 13^2≡78
14^2≡14 , 15^2≡43 , 16^2≡74 , 17^2≡16
18^2≡51 , 19^2≡88 , 20^2≡36 , 21^2≡77
22^2≡29 , 23^2≡74 , 24^2≡30 , 25^2≡79
26^2≡39 , 27^2≡1 , 28^2≡56 , 29^2≡22
30^2≡81 , 31^2≡51 , 32^2≡23 , 33^2≡88
34^2≡64 , 35^2≡42 , 36^2≡22 , 37^2≡4
38^2≡79 , 39^2≡65 , 40^2≡53 , 41^2≡43
42^2≡35 , 43^2≡29 , 44^2≡25 , 45^2≡23

根据以上中间数的介绍，前序与逆序相交之处为k，这里k=23
观察以上范围内平方剩余，特别是中间数k=23，与23相差±1的两个数22和24的平方剩余：
22^2≡29 mod 91
24^2≡30 mod 91
22与24的平方剩余相差为30-29=1，这是因为上式相减得：
30–29≡24^2–22^2( mod 91)
1≡(23+1)^2–(23–1)^2 ( mod 91)
1≡4*23 ( mod 91)
  正好为4×23≡1 mod 91
再看与23相差±2的两个数21和25的平方剩余：
21^2≡77 mod 91
25^2≡79 mod 91
21与25平方剩余相差为79-77=2，且21的平方剩余77与23的平方剩余74相差3，25的平方剩余79与23的平方剩余74相差5(与中间数平方剩余相差3、5的证明见后)，这是因为上式相减得：
79–77≡25^2–21^2( mod 91)
2≡(23+2)^2–(23–2)^2 ( mod 91)
2≡4*23*2 ( mod 91)
正好为(4×23)*2≡2 mod 91
.
.
.
以此类推，20与26的平方剩余相差3，19与27的平方剩余相差4……(证明见后)
再来证明21(k-2)与23(k)的平方剩余为什么相差3？
证明一：
设n=4k-1，k为中间数
   k^2≡k/4=b (mod n) ①
   (k-2)^2≡c (mod n)    ②
   ①-②：b-c≡k^2-(k-2)^2 (mod n)
         b-c≡ 4k–4 (mod n)
   ∵ 4k≡1 (mod n)
   ∴ b-c≡ 1–4 (mod n)
         b-c≡–3 (mod n)
         c–b≡3 (mod n)  证毕

   证明二：
   同理可以证明k与k+2相差5。
   设n=4k-1，k为中间数
   k^2≡k/4=b (mod n)    ③
   (k+2)^2≡d (mod n)    ④
   ④-③：d-b≡(k+2)^2-k^2 (mod n)
         d-b≡ 4k+4 (mod n)
   ∵ 4k≡1 (mod n)
   ∴ d-b≡ 1+4 (mod n)
         d-b≡5 (mod n) 证毕

Ⅰ、观察23,21,19,17…的平方剩余差为3,11,19…(也可以通过证明一得到该数列)，即平方剩余差是一个等差数列，公差为8。
   a(m)=a(1)+(m-1)*8  a(1)=3  m>0
   s1=3+11+19+…+3+8(m-1)
      =3m+4m(m-1)
      =m(4m-1)

Ⅱ、观察23,25,27,29…的平方剩余差为5,13,21…(也可以通过证明二得到该数列)，即平方剩余差是一个等差数列，公差为8。
   a(m)=a(1)+(m-1)*8  a(1)=5  m>0
   s2=5+13+21+…+5+8(m-1)
      =5m+4m(m-1)
      =m(4m+1)

Ⅲ、观察22,20,18,16…的平方剩余差为7,15,23…(也可以通过证明得到该数列)，即平方剩余差是一个等差数列，公差为8。
   a(m)=a(1)+(m-1)*8  a(1)=7  m>0
   s3=7+15+23+…+7+8(m-1)
      =7m+4m(m-1)
      =m(4(m+1)-1)

Ⅳ、观察24,26,28,30…的平方剩余差为9,17,25…(也可以通过证明得到该数列)，即平方剩余差是一个等差数列，公差为8。
   a(m)=a(1)+(m-1)*8  a(1)=9  m>0
   s4=9+17+25+…+9+8(m-1)
      =9m+4m(m-1)
      =m(4(m+1)+1)

根据以上，以中间数k为中心向中间数的两边共形成4个数列：
   小于k方向数列ⅠⅢ：
   m(4m-1)、m(4(m+1)-1)
   大于k方向数列 Ⅱ Ⅳ：
   m(4m+1)、m(4(m+1)+1)

   Ⅰ、Ⅲ数列往小于k方向必然与a^2各有一个交点，且两个交点是相邻的。
   Ⅱ、Ⅳ往大于K方向必然与i(i+1)+k各有一个交点，且这两个交点也是相邻的，与Ⅰ、Ⅲ数列的两个交点正好是与K为中心的对称点。
如91，k=23，m=5
Ⅰ数列：74+5(4*5-1)=169=13^2
Ⅲ数列：29+5(4*6-1)=144=12^2
12、13与23相差11、10

Ⅱ数列：74+5(4*5+1)=179=12*(12+1)+23
   得45-12=33
Ⅳ数列：29+5(4*6+1)=155=11*(11+1)+23
   得45-11=34
   34、33与23相差11、10

现在证明Ⅰ数列往减方向与a^2的交点：
证明：设交点处为a，因为Ⅰ数列以k、k-2、k-4…的平方剩余减小的，每个值相隔2，所以m为：
   m=(k-a)/2，k^2≡k/4=b (mod n)
Ⅰ数列可以变为以下：
   k/4+4((k-a)/2)^2-(k-a)/2  (mod n)
≡k/4+k^2-2ka+a^2-(k-a)/2 (mod n)
≡k/4+k/4-2ka+a^2-k/2+a/2(mod n)
≡a^2-2ka+a/2 (mod n)
≡a^2-((4k-1)/2)*a (mod n)
≡a^2 (mod n)
a的值为：
k为奇数且(k+1)/2为奇数时：a=(k+1)/2，否则(k+1)/2为偶数时：a=(k+1)/2+1
k为偶数且k/2为偶数时：a=k/2，否则k/2为奇数时：a=k/2+1

  Ⅱ、Ⅲ、Ⅳ数列也可以按此证明。

scsongls · 发表于 2014-12-22 20:38

本帖最后由 scsongls 于 2014-12-22 12:44 编辑

  ② n=4k+1
当n=4k+1时，a^2≡b (mod n)，先看一个例93，93的平方剩余如下(93=4×23+1，9<a≤46)：

93
10^2≡7 , 11^2≡28 , 12^2≡51 , 13^2≡76
14^2≡10 , 15^2≡39 , 16^2≡70 , 17^2≡10
18^2≡45 , 19^2≡82 , 20^2≡28 , 21^2≡69
22^2≡19 , 23^2≡64 , 24^2≡18 , 25^2≡67
26^2≡25 , 27^2≡78 , 28^2≡40 , 29^2≡4
30^2≡63 , 31^2≡31 , 32^2≡1 , 33^2≡66
34^2≡40 , 35^2≡16 , 36^2≡87 , 37^2≡67
38^2≡49 , 39^2≡33 , 40^2≡19 , 41^2≡7
42^2≡90 , 43^2≡82 , 44^2≡76 , 45^2≡72
46^2≡70

根据以上中间数的介绍，前序与逆序相交之处为k，这里k=24
观察以上范围内平方剩余，特别是中间数k=24，与24相差±1的两个数23和25的平方剩余：
23^2≡64 mod 93
25^2≡67 mod 93
23与25的平方剩余相差为67-64=3，这是因为上式相减得：
67–64≡25^2–23^2( mod 93)
3≡(24+1)^2–(24–1)^2 ( mod 93)
3≡4*24 ( mod 93)
  正好为4×24≡3 mod 93
再看与24相差±2的两个数22和26的平方剩余：
22^2≡19 mod 93
26^2≡25 mod 93
22与26平方剩余相差为25-19=6，且22的平方剩余19与24的平方剩余18相差1，26的平方剩余25与24的平方剩余18相差7(与中间数平方剩余相差1、7的证明见后)，这是因为上式相减得：
25–19≡26^2–22^2( mod 93)
6≡(24+2)^2–(24–2)^2 ( mod 93)
6≡4*24*2 ( mod 93)
正好为(4×24)*2≡6 mod 93
.
.
.
以此类推，21与27的平方剩余相差9，20与28的平方剩余相差12……(证明见后)
再来证明22(k-1)与24(k+1)的平方剩余为什么相差1？
证明一：
设n=4k+1，则k+1为中间数
   (k+1)^2≡b (mod n)    ①
   (k-1)^2≡c (mod n)    ②
   ①-②：b-c≡(k+1)^2-(k-1)^2 (mod n)
         b-c≡ 4k (mod n)
   ∵ 4k≡-1 (mod n)
   ∴ b-c≡ -1 (mod n)
         c–b≡1 (mod n)  证毕

   证明二：
   同理可以证明k+1与k+3相差7。
   设n=4k+1，k+1为中间数
   (k+1)^2≡b (mod n)    ③
   (k+3)^2≡d (mod n)    ④
   ④-③：d-b≡(k+3)^2-(k+1)^2 (mod n)
         d-b≡ 4k+8 (mod n)
   ∵ 4k≡-1 (mod n)
   ∴ d-b≡ -1+8 (mod n)
         d-b≡7 (mod n) 证毕

Ⅴ、观察24,22,20,18…的平方剩余差为1,9,17…(也可以通过证明一得到该数列)，即平方剩余差是一个等差数列，公差为8。
   a(m)=a(1)+(m-1)*8  a(1)=1  m>0
   s5=1+9+17+…+1+8(m-1)
      =m+4m(m-1)
      =m(4m-3)

Ⅵ、观察24,26,28,30…的平方剩余差为7,15,23…(也可以通过证明二得到该数列)，即平方剩余差是一个等差数列，公差为8。
   a(m)=a(1)+(m-1)*8  a(1)=7  m>0
   s6=7+15+23+…+7+8(m-1)
      =7m+4m(m-1)
      =m(4m+3)

Ⅶ、观察23,21,19,17…的平方剩余差为5,13,21…(也可以通过证明得到该数列)，即平方剩余差是一个等差数列，公差为8。
   a(m)=a(1)+(m-1)*8  a(1)=5  m>0
   s7=5+13+21+…+5+8(m-1)
      =5m+4m(m-1)
      =m(4m+1)

Ⅷ、观察25,27,29,31…的平方剩余差为11,19,27…(也可以通过证明得到该数列)，即平方剩余差是一个等差数列，公差为8。
   a(m)=a(1)+(m-1)*8  a(1)=11  m>0
   s8=11+19+27+…+11+8(m-1)
      =11m+4m(m-1)
      =m(4m+7)

根据以上，以中间数k+1为中心向中间数的两边共形成4个数列：
   小于k+1方向数列Ⅴ、Ⅶ：
   m(4m-3)、m(4m+1)
   大于k+1方向数列Ⅵ 、Ⅷ：
   m(4m+3)、m(4m+7)

   Ⅴ、Ⅶ数列往小于k+1方向必然与a^2各有一个交点，且两个交点是相邻的。
   Ⅵ 、Ⅷ往大于K+1方向必然与i(i+1)+(n-k/2)各有一个交点，且这两个交点也是相邻的，与Ⅴ、Ⅶ数列的两个交点正好是与K+1为中心的对称点。
如93，k=24，m=6
Ⅴ数列：18+6(4*6-3)=144=12^2
Ⅶ数列：64+5(4*5+1)=169=13^2
12、13与24相差12、11

Ⅵ 数列：18+6(4*6+3)=180=10*(10+1)+70
   得46-10=36
Ⅷ数列：67+5(4*5+7)=202=11*(11+1)+70
   得46-11=35
   36、35与24相差12、11

现在证明Ⅴ数列往减方向与a^2的交点：
证明：设交点处为a，因为Ⅴ数列以k+1、k-1、k-3…的平方剩余减小的，每个值相隔2，所以m为：
   m=(k+1-a)/2，(k+1)^2≡b (mod n)
Ⅴ数列可以变为以下：
   b+4(((k+1)-a)/2)^2-3*((k+1)-a)/2  (mod n)
≡b+(k+1)^2-2(k+1)a+a^2-3*((k+1)-a)/2 (mod n)
≡2b-2(k+1)a+a^2-3(k+1)/2+3a/2 (mod n)
≡2(k+1)^2+a^2-a(4(k+1)-3)/2-3(k+1)/2 (mod n)
≡(k+1)(4(k+1)-3)/2+a^2 (mod n)
≡a^2 (mod n)
a的值为：
k+1为奇数且(k+2)/2为奇数时：a=(k+2)/2，否则(k+2)/2为偶数时：a=(k+2)/2+1
k+1为偶数且(k+1)/2为偶数时：a=(k+1)/2，否则(k+1)/2为奇数时：a=(k+1)/2

   Ⅵ、Ⅶ、Ⅷ数列也可按此证明。

scsongls · 发表于 2014-12-22 20:45

  四、以下来证明一般式：
设n为奇数，n的平方剩余取值范围为[√n]<a≤(n-1)/2，[√n]为不大于√n的整数，n>0。设a^2≡b (mod n)，以a为中心前后按相等的数i(1≤i<a)各取一个数：
(a-i)^2≡c (mod n)    ⑴
a^2≡b (mod n)       ⑵
(a+i)^2≡d (mod n) ⑶
  上述 ⑶-⑴得：
d-c≡4ai (mod n)    ⑷
当a=k，上式变为d-c≡4ki (mod n)，进行以下计算：
ⅰ、n=4k-1，得4k≡1 (mod n)，此时以中间数a=k为中心
   ⑷式变为：d-c≡i (mod n)
   当i=1,2,3…时，d-c的平方剩余差为1,2,3…，则k-1,k+1平方剩余相差1，k-2,k+2平方剩余相差2，k-3,k+3平方剩余相差3……
ⅱ、n=4k+1，得4k≡–1 (mod n)，4(k+1)≡3 (mod n)，此时以中间数a=k+1为中心
      ⑷式变为：d-c≡3i (mod n)
   当i=1,2,3…时，d-c的平方剩余差为3,6,9…，则k,k+2平方剩余相差3，k-1,k+3平方剩余相差6，k-3,k+3平方剩余相差9……

五、平方剩余为完全平方数的分布情况
通过观察91=7*13平方剩余的几个完全平方数
10^2≡9  17^2≡16
27^2≡1  34^2≡64
30^2≡81 37^2≡4  44^2≡25
10与17相差7
27与34相差7
30、37、44相差7

再来观察93=3*31平方剩余的几个完全平方数
23^2≡64  26^2≡25  29^2≡4
32^2≡1 35^2≡16  38^2≡49
23、26、29、32、35、38都相差3

这样我们大概可以知道平方剩余为完全平方数分布的一些情况：
设n=fe，n为奇数，[√n]<a≤(n-1)/2，[√n]为不大于√n的整数，f<e，a的平方剩余为完全平方数。
当f与e相差不大，a比较均匀分布在上述范围内，差值为f。
当f与e相差较大，a比较均匀分布在上述范围内的一段区间内，相差越大，区间范围越小，且差值为f。

  本文没有具体算法。

重生888 · 发表于 2014-12-23 18:16

此研究值得向大家推广！

重生888 · 发表于 2014-12-23 18:16

此研究值得向大家推广！

moranhuishou · 发表于 2014-12-23 18:50

整数分解必须有重大理论创新才可能有突破，这是非常之难的。指望修修补补是没有出路的。

		自动登录	找回密码
密码			注册