[原创]整数分解随笔

整数分解随笔
     以下是我对整数分解的一些想法，主要基于Fermat分解法，也不知道对与错，且还有很多东西搞不清楚，望大家批评指证，并提出宝贵意见，本人十分感谢。
一、先看两个式子：
1+3+5+…+(2n-3)+(2n-1)=n^2  …… ①
2+4+6+…+2(n-1)+2n=n(n+1)   …… ②
以上两式的证明请参考相关书籍。
二、对于((n-1)/2)^2余的求法，即((n-1)/2)^2的平方剩余的求法：（n为奇数）
对于((n-1)/2)^2的平方剩余，我们有以下的求法：
1、当n=4k-1时：余为：
    ((n-1)/2)^2≡((n-1)/2+1)/2 (mod n)                         ③
    商为：((n-1)/2+1)/2-1
    如35=4*9-1
    则((35-1)/2)^2=17^2≡(17+1)/2=9 (mod 35)
    商为：9-1=8
   
    39=4*10-1
    则((39-1)/2)^2=19^2≡(19+1)/2=10 (mod 39)
    商为：10-1=9
   证明：当n=4k-1
    ③式左边为：
    ((n-1)/2)^2=((4k-1-1)/2)^2=(2k-1)^2
    ③式右边为：
     商：((n-1)/2+1)/2-1=((4k-1-1)/2+1)/2-1=k-1
     余：((n-1)/2+1)/2=((4k-1-1)/2+1)/2=k
    则(k-1)*n+k=(k-1)(4k-1)+k=(2k-1)^2
       商        余
      ③式左边=右边，证毕
2、当n=4k+1时；余为：
    ((n-1)/2)^2≡n-((n-1)/4) (nod n)  ④
    商为：((n-1)/4)-1
    如57=4*14+1
    则((57-1)/2)^2=28^2≡57-(28/2)=43 (mod 57)
    商为：((57-1)/2)/2-1=(28/2)-1=13
   
    77=4*19+1
    则((77-1)/2)^2=38^2≡77-(38/2)=58 (mod 77)
    商为：((77-1)/2)/2-1=(38/2)-1=18
    证明：当n=4k+1
        ④式左边为:
         ((n-1)/2)^2=((4k+1-1)/2)^2=(2k)^2
        ④式右边为:
         n*(((n-1)/4)-1)+n-((n-1)/4)=(4k+1)*((4k+1-1)/4)-1)+4k+1-((4k+1-1)/4)=(2k)^2
               商           余
        ④的左边=右边，该式成立。
三、??我们来看以下三个数的平方剩余：
，平方剩余的取值范围为[√n]<a≤(n-1)/2，其中n>0，且为奇数，[√n]为不大于√n的整数。a^2≡d(mod n)
35   
√35≈5.91   (35-1)/2=17
则6≤a≤17
6^2≡1,7^2≡14,8^2≡29,9^2≡11
10^2≡30,11^2≡16,12^2≡4,13^2≡29
14^2≡21,15^2≡15,16^2≡11,17^2≡9
对以上的平方剩余，按相反的方向进行排列得：
17^2≡9，16^2≡11，15^2≡15，14^2≡21，13^2≡29，12^2≡4，…
观察上述得：
17与16的平方剩余相差2(11–9=2)，16与15的平方剩余相差4(15–11=4)，15与14的平方剩余相差6(21–14=6)，14与13的平方剩余相差8(29–21=8)，12与13的平方剩余相差10(4+35–29=10)，…
按逆序方向的平方剩余差可得：
2    4    6     8    10 …20  22
33 31  29   27  25 …15  13
上排式子中的33 31 29…是两个数的平方差，如33=17^2–16^2，具体见①式，当然也可以按16^2+1=33或17^2–1=33，但上下两式相加一定等于35，即平方剩余差与相关联两个数的平方差之和一定等于该数n(35)，或者说平方剩余差的正序与逆序之和等于n(35)。
39
√39≈6.24
7^2≡10,8^2≡25,9^2≡3,10^2≡22
11^2≡4,12^2≡27,13^2≡13,14^2≡1
15^2≡30,16^2≡22,17^2≡16,18^2≡12
19^2≡10
对以上的平方剩余，按相反的方向进行排列得：
19^2≡10，18^2≡12，17^2≡16，16^2≡22，15^2≡30，14^2≡1，…
观察上述得：
19与18的平方剩余相差2(12–10=2)，18与17的平方剩余相差4(16–12=4)，17与16的平方剩余相差6(22–16=6)，16与15的平方剩余相差8(30–22=8)，15与14的平方剩余相差10(1+39–30=10)，…
按逆序方向的平方剩余差可得：
2    4    6     8    10 …22  24
37 35  33   31  29 …17  15
上排式子中的37 35 33…是两个数的平方差，如37=19^2–18^2，具体见①式，当然也可以按18^2+1=37或19^2–1=37，但上下两式相加一定等于39，即平方剩余差与相关联两个数的平方差之和一定等于该数n(39)，或者说平方剩余差的正序与逆序之和等于n(39)。
77
√77≈8.77
9^2≡4,10^2≡23,11^2≡44,12^2≡67
13^2≡15,14^2≡42,15^2≡71,16^2≡25
17^2≡58,18^2≡16,19^2≡53,20^2≡15
21^2≡56,22^2≡22,23^2≡67,24^2≡37
25^2≡9,26^2≡60,27^2≡36,28^2≡14
29^2≡71,30^2≡53,31^2≡37,32^2≡23
33^2≡11,34^2≡1,35^2≡70,36^2≡64
37^2≡60,38^2≡58
对以上的平方剩余，按相反的方向进行排列得：
38^2≡58，37^2≡60，36^2≡64，35^2≡70，34^2≡1，…
观察上述得：
38与37的平方剩余相差2(60–58=2)，37与36的平方剩余相差4(64–60=4)，36与35的平方剩余相差6(70–64=6)，35与34的平方剩余相差8(1+77–70=8)，…
按逆序方向的平方剩余差可得：
2    4    6     8    10 …56  58
75 73  71   69  67 …21  19
上排式子中的75 73 71…是两个数的平方差，如75=38^2–37^2，具体见①式，当然也可以按37^2+1=75或38^2–1=75，但上下两式相加一定等于77，即平方剩余差与相关联两个数的平方差之和一定等于该数n(77)，或者说平方剩余差的正序与逆序之和等于n(77)。
我们来证明从(n-1)/2向√n的逆序方向为什么会相差2k?
设n为奇数，[√n]<a≤(n-1)/2
((n-1)/2)^2≡d (mod n)
((n-1)/2-1)^2≡c (mod n)
我们先证明c-d=2
上面两个式子相减得
((n-1)/2)^2-((n-1)/2-1)^2≡d-c (mod n)
因n为奇数，设n=2k+1，代入上式得
k^2-(k-1)^2≡d-c (mod n)
-2k+1≡d-c (mod n)
-(2k+1)-2≡d-c (mod n)
-2≡d-c (mod n)
c-d≡2 (mod n)
证毕。
我们来证明-般式，设n=2j+1(j>0)
((n-1)/2-k)^2≡d (mod n)
((n-1)/2-k-1)^2≡c (mod n)
上式相减得
((n-1)/2-k)^2-((n-1)/2-k-1)^2≡d-c (mod n)
把n=2j+1代入上式得
(j-k)^2-(j-k-1)^2≡d-c (mod n)
2(j-k)-1≡d-c (mod n)
2j+1-2k-2≡d-c (mod n)
-2(k+1)≡d-c (mod n)
c-d≡2(k+1) (mod n)
证毕。
我们再看一个式子：
a^2≡d (mod n)
两边加2a+1得
a^2+2a+1≡d+2a+1 (mod n)
(a+1)^2≡d+a+a+1 (mod n)
即下个数的平方剩余等于该数的平方剩余加2倍该数再加1