質數第5回
Topic: 9亂證 Crazy Proof

質數第4回
Topic: 9亂證 Crazy Proof
請先看<提示>.

事情:質數或合成數.

問題1:測試質數,如何減低錯誤?
問題2:測試質數,如何排除困難?

解題:
-----------
上回講到測試非常大的質數,要用電腦及2進制數學.

2進制中,除數比較大機會有誤差,+-x比較穩陣.

但除2及除3還是比較易.
除2只需退後1個位,如 11001010/2=1100101
而除3更可以用速算法,如 325973/3=?
先將每數字加起再除3: 3+2+5+9+7+3=29/3=9餘2,所以先將325973減2,再化成2進制再除3即可.

再看回之前的其中一些數據:
91=1x3+44x2=29x3+2x2
44/3=14餘2
14x2+1=29

221=1x3+109x2=73x3+1x2
109/3=36餘1
36x2+1=73

所以 P=3+Y2=X3+r2, X=2int(Y/3)+1, r=Y/3的餘數    ----------(10)

再看真些,
91=......=7x3+35x2=......=21x3+14x2=......

7+7x2=21
14+7x3=35

221=......=13x3+91x2=......=39x3+52x2=......=65x3+13x2=......

13+13x2=39
13+13x3=52

13+13x4=65
13+13x6=91

可見如果 x=1+2n是因子,該組 (1+2n)3+(Y-3n)2在相距1+2n的一個倍數後,必然與 y=(1+2n)倍數的一組 (X-2m)3+(r+3m)2重疊.

(x+2kx,y-3kx)=(X-2m,r+3m),    k=int, r+3m=dx, d=int    ----------(11)

所以,僅用2進制除數除2或3,可以測試
Nmax=int(Y/3)    ----------(12)
K=Nmax-n-m        ----------(13)
如果 K=kx, x+2K=X-2m, y-3K=r+3m=d(1+2n), d=1or2    ----------(14)
x=1+2n 就是因子.

最後,
3x+2y=3X+2dx,    y=Ymax-3n, X=Xmax-2m
(3-2d)x=3X-2y
X=[(3-2d)x+2y]/3=(2y+/-x)/3,    d=1or2
X=(2j+/-1)(1+2n)/3,    +1 when d=1,-1 when d=2    ----------(15)

y-X=y-(2y+/-x)/3=(y+/-x)/3        
y-X=(j+/-1)(1+2n)/3,    +1 when d=1,-1 when d=2    ----------(16)    

而 (j+/-1)/3 < j

所以,可以用 (y-X)/(1+2n) 去找出 j.
-----------

答案1:少用2進制除數,多用+-x.
答案2:x+2kx=X-2m, y-3kx=r+3m,測試有否重疊.

以證:尋找質數,細心研究,得出自己的結論,好過只識跟人尾.

結論:質數再大,都有方法.

得分:(x+2kx,y-3kx)/10

質數第3回
Topic: 9亂證 Crazy Proof
請先看<提示>.

事情:質數測試.

問題1:質數數式,有何意義?
問題2:測試質數數式,有何方法?

解題:
-----------
質數數式 P=(1+2n)3+(Y-3n)2=(X-2m)3+(r+3m)2
如非質數,有 j(1+2n)=Y-3n,i(X-2m)=(r+3m)

上回講到,j較大機會是整數,所以先分析 j.
j=(Y-3n)/(1+2n)    ----------(7)

這明顯是直角雙曲線,y=(C-3x)/(1+2x),曲線位於(+x,+y),(-x,-y)之內.

再看清楚,
(1+2n)3+(Y-3n)2=(1+2n)3+j(1+2n)2=(1+2n)(3+2j)=(1+2n)(1+2m)=(3+2i)(3+2j)

明顯 j就是另一個合成數 3+2j組成部分,所以找到一組n,j等於找到兩個 P的合成數.
m=1+j
n=1+i
注意,這裡 i,m並非i(X-2m)=(r+3m)中的 i,m.

(m-1)(1+2n)=Y-3n
2mn+m+n-1-Y=0    ----------(8)
或
j[1+2(1+i)]=Y-3(1+i)
2ij+3(i+j)+3-Y=0    ----------(9)

(7)(8)(9)都是直角雙曲線,如何找出其中的正整數解?
請恕材疏學淺,除了電腦繪圖,不知其他方法.

另外
P=(1+2n)3+(Y-3n)2=(1+2n)(1+2m)=(1+2n)1+(1+2n)2m
所以其實測試亦可以變成: (P-x)/2x=m, x=3,5,7,9.....

(P-x)當然比(Y-3n)大,所以還是用 (1+2n)3+(Y-3n)2測試較易.

測試時自然不用試 3及5 的倍數,因為一開始先要確定 Y not= 3n,而 5的倍數只有 5與0字尾,一望便知.
同理,7,11,13...等的倍數亦不用測試.

需然直接用 P測試亦可,但 Y-3n比 P細,而且 Y-3n會越來越細,所以越來越易計.

倘若 P是非常大的單數,可先減去 1+2n的大倍數,
如 Y-3n是有100位的數,
先減去 (1+2n)x(10的98,99次方),
再減去 (1+2n)x(10的97,96....次方),
使之變成可計算範圍,如一百萬或6個0之內,最後才去除以(1+2n).

要測試非常大的質數,當然最好要用電腦及2進制數學.
-----------

答案1:j=(Y-3n)/(1+2n),是直角雙曲線.
答案2:不用試 3,5,7,11,13...等的倍數.測試非常大的質數,用電腦繪圖,2進制數學.

以證:質數的確難找.

結論:至於如何再進一步排除困難與錯誤,欲知後事如何,且看下回分解.

得分:2mn+m+n-1-Y/10

質數第2回
Topic: 9亂證 Crazy Proof
請先看<提示>.

事情:分析質數,尋找(xi,yi).

問題1:質數數式有何特徵?
問題2:(xi,yi)有何特徵?

解題:
-----------
質數數式 P=x3+y2

根據 A) x not= 2m,所以x一定是單數.
x=1,3,5,.....

根據 B) y not= 3n,所以y一定是:
y=1,4,7,10....=1+3n, 或
y=2,5,8,11....=2+3n,

因為x每次加2,x3會加6,y2自然要減6,所以
P=(1+2n)3+(Y-3n)2,    Y=y max, n=1,2,3,....N=n max    ----------(3)
P=(X-2m)3+(r+3m)2,    X=x max, r=1or2, m=1,2,3...M=m max    ----------(4)

例如:
19=1x3+8x2=3x3+5x2=5x3+2x2,    X=5, Y=8, r=2, N=M=2

根據 C)x/y or y/x not= i, i=正整數;

所以如果不是質數,x或y會是對方的倍數.

1+2n=j(Y-3n) or j(1+2n)=Y-3n
(X-2m)=i(r+3m) or  i(X-2m)=(r+3m)

再分析多些單數,何時出現以上情況,

7x7=49=1x3+23x2=3x3+20x2=5x3+17x2=7x3+14x2
=9x3+11x2=11x3+8x2=13x3+5x2=15x3+2x2    第4組

7x13=91=1x3+44x2=3x3+41x2=5x3+38x2=7x3+35x2=9x3+32x2
=11x3+29x2=13x3+26x2=15x3+23x2=17x3+20x2=19x3+17x2
=21x3+14x2=23x3+11x2=25x3+8x2=27x3+5x2=29x3+2x2        第4,7,11組

3x5x7=105=1x3+51x2=3x3+48x2=5x3+45x2=7x3+42x2=9x3+39x2
=11x3+36x2=13x3+33x2=15x3+30x2=17x3+27x2=19x3+24x2
=21x3+21x2=23x3+18x2=25x3+15x2=27x3+12x2=29x3+9x2
=31x3+6x2=33x3+3x2=35x3+0x2              第2,3,4,8,11,13,17組

107=1x3+52x2=3x3+49x2=5x3+46x2=7x3+43x2=9x3+40x2
=11x3+37x2=13x3+34x2=15x3+31x2=17x3+28x2=19x3+25x2
=21x3+22x2=23x3+19x2=25x3+16x2=27x3+13x2=29x3+10x2
=31x3+7x2=33x3+4x2=35x3+1x2        無

13x17=221=1x3+109x2=3x3+106x2=5x3+103x2=7x3+100x2=9x3+97x2=
11x3+94x2=13x3+91x2=15x3+88x2=17x3+85x2=19x3+82x2=  
21x3+79x2=23x3+76x2=25x3+73x2=27x3+70x2=29x3+67x2=
31x3+64x2=33x3+61x2=35x3+58x2=37x3+55x2=39x3+52x2=
41x3+49x2=43x3+46x2=45x3+43x2=47x3+40x2=49x3+37x2=
51x3+34x2=53x3+31x2=55x3+28x2=57x3+25x2=59x3+22x2=
61x3+19x2=63x3+16x2=65x3+13x2=67x3+10x2=69x3+7x2=
71x3+4x2=73x3+1x2            第7,9,26,33組

可以發現:
1)如果不是質數,最少有一組(xi,yi)是倍數,不是自成數則最少有兩組(xi,yi)是倍數.
2)因為x必定是單數,兼且是由1開始的每個單數,而(y/x)會是倍數,但y則不一定是單數,而(x/y)亦不一定是倍數,或只有公因數,所以(xi,yi)必定會出現在前半數(xi,yi)組合,即yi>xi.
3)實際上(xi,yi)只需尋找至(x=P開方)那一組,必會出現,否則就是質數.

所以只需考慮:
j(1+2n)=Y-3n    j=正整數, 而1+2n<=sqrtP    ----------(5)
i(X-2m)=(r+3m)    i=正整數, 而X-2m<=sqrtP    ----------(6)

因此,尋找質數的問題又變成:
給出一單數P>3,如何確定P=(xi)3+(yi)2會否有至少一組(xi,yi)符合(5)或(6)式?
-----------

答案1:P=(1+2n)3+(Y-3n)2=(X-2m)3+(r+3m)2
答案2:合成數會出現 j(1+2n)=Y-3n,i(X-2m)=(r+3m)

以證:質數數式有助找尋質數.

結論:至於怎樣尋找那一組(xi,yi),欲知後事如何,且看下回分解.

得分:yi>xi/10

質數第1回
Topic: 9亂證 Crazy Proof
請先看<提示>.

事情:質數就係合成數之源.

問題1:如何尋找質數?
問題2:有無質數公式?

解題:
-----------
質數基本定義:質數只可被自己及1除盡.
除1,2,之外,3以上質數都係單數.

根據<<輾轉相除法>>:
被除數=商x除數+餘數
a=a0b+r,    0=<r<b;        如果r唔等於0,再除b,
b=a1r+r1,    0=<r1<r;    如果r1唔等於0,再除r,
r=a2r1+r2,    0=<r2<r1;    如果r2唔等於0,再除r1,
.
.
.
r(i-1)=a(i+1)ri+r(i+1),        0=<r(i+1)<ri,    直至r(i+1)等於0.        

於是,所有整數可以此形式寫成:
1=1+0
2=2+0
3=2+1
5=3+2
7=4+3=2x2+3
9=5+4=5+2x2=(3+2)+2x2=3+3x2=3x3

如此類推,於是,所有單數可以寫成:
k=(k+1)/2+(k-1)/2, k=單數1,3,5....    ----------(1)

繼續寫,睇下有乜發現?
11=6+5=2x3+3+2=4x2+3=3x3+2
13=7+6=2x2+3+3x2=5x2+3=2x2+3x3
15=8+7=2x4+2x2+3=2x6+3=2x2x3+3=5x3
17=9+8=3x3+4x2=3+7x2=5x3+2
19=10+9=5x2+3x3=(3+2)x2+3x3=5x3+2x2=3+8x2
21=11+10=3x3+2+5x2=3x3+6x2=3x3+3x2x2=7x3=3+9x2
23=12+11=2x6+3x3+2=7x2+3x3=4x2+5x3=3+10x2=7x3+2
25=13+12=5x2+3+3x4=5x2+3x5=5x5=7x3+2x2=3+11x2
27=14+13=7x2+2x2+3x3=9x2+3x3=3x6+3x3=9x3=3+12x2
.
.
49=25+24=7x3+2x2+3x4x2=7x3+14x2=7x3+7x2x2=7x7
51=26+25=13x2+5x2+5x3=18x2+5x3=3x3x2x2+5x3=17x3
53=27+26=9x3+13x2=9x3+(2x2+3x3)x2=15x3+4x2

可以發現,越大既單數,可以用越多既3同2既倍數組合寫成,即
k=x3+y2,    x,y=1,2,3.....        

而如果是合成數,則必定有最少一組(x3,y2)組合可找到公因數.

所以質數必須符合以下條件:
**********************
所有 P=質數>3
P=x3+y2,    x,y=1,2,3.....        ----------(2)

而且
A) x not= 2m, 證明與C)相同
B) y not= 3n, 證明與C)相同
C) x/y or y/x not= i, i=正整數; 證明: 當 x,y>1, if x/y=i,x3+2y=iy3+2y=(i3+2)y
D) P的每一組(xi,yi)組合, P=(x1)3+(y1)2=(x2)3+(y2)2=......=(xi)3+(yi)2 均符合 A),B),C)三點.
**********************

因此,尋找質數的問題變成:
給出一單數P>3,如何確定P=(xi)3+(yi)2的每一組(xi,yi)組合均符合 A,B,C三點要求?
-----------

答案1:質數有方式尋找.
答案2:質數有數式,未知有無公式.

以證:質數除了基本定義,還可以有數式定義.

結論:至於怎樣尋找有否(xi,yi),欲知後事如何,且看下回分解.

得分:x3+y2/10