整数分解随笔(六)
本次文中未注明处,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)
[课程]FART 脱壳王!加量不加价!FART作者讲授!