数论定理总结
0.威爾遜定理、判斷一個數(shù)是不是素數(shù)得充分必要條件:
? p為素數(shù),必有: (p-1)! ≡ -1 mod p
? ? ? ? ?即:(p-1) !+ 1 ≡ 0 mod p
? 引證: 令 p=7 則有(7-1)!= 6! = 1 * 2 * 3 * 5 * 6
? ? ? ? ?重排乘積中的因子并把乘積是模7的逆的分成一組 即:2*4 ≡ 1 mod 7 、3*5 ≡ 1 mod 7
? ? ? ? ?得: 6!≡(2*4)*(3*5)*6
? ? ? ? ? ? ? ≡ 6 mod 7
? ? ? ? ? ? ? ≡-1 mod 7
? ? 看看引證就行,實證太玄學(xué)(初等數(shù)論及應(yīng)用中可以找到)
實現(xiàn)的時間復(fù)雜度為 n(log2 n)^2
1. 費馬小定理推出的一個[線性同余方程]的推論：
? ?費馬小定理:ax ≡ 1 mod p
? ? ? ? 因為a^(p-2)是 a mod p 的逆 [a^(p-1)≡ 1 mod p],也就是說解: x=a^(p-2)
? ?現(xiàn)在有: ax ≡ b mod p
? ? ? ? 把同余方程左右兩邊 *a^(p-2) 得出: a^(p-2)*ax ≡ b*a^(p-2) mod p
? ? ?則得出推論:x ≡ a^(p-2)*b mod p,
? ? 歐拉定理：模板
? ? ? ? ??假若與互質(zhì)，那么可被整除。亦即，??其中即為歐拉總計函數(shù)。如果為 ? ? ? ? ?質(zhì)數(shù)，那么?
? ? ?歐拉函數(shù)的值:?（小于等于1的正整數(shù)中唯一和1互質(zhì)的數(shù)就是1本身）
?? ? ? ? ?若n是質(zhì)數(shù)p的k次冪，，因為除了p的倍數(shù)外，其他數(shù)都跟n互質(zhì)。
? ? ? ? ? ? 若
? ? ? ??。如 ? ? ?
歐拉函數(shù)是積性函數(shù)，即是說若m?,?n互質(zhì)，
?2.同余式的消去律：
? ? 有一個c 使得 gcd(c,p)=1? ? ?則 ac ≡ bc mod p? =>? a ≡ b mod p ?(在a != b 的時候成立)
證：? ?ac = pk + bc => c (a-b) = kp ?=> (a-b)= kp /c ?則c 整除 k (c|k) => k=k`c
? ? ? ? ? c (a - b) = k`cp => (a -b) =k`p ?=> ?a ?≡ ?b mod p
附變形: 若a^2≡1(mod p),則a≡±1(mod p) 也就是說:(a+1)%p==0或(a-1)%p==0
3.盧卡斯定理:
? ? ? ? ? ? ?? ??? ? ??? ?
? ? ? ?A、B是非負整數(shù)，p是質(zhì)數(shù)。AB寫成p進制：A=a[n]a[n-1]...a[0]，B=b[n]b[n-1]...b[0]。
? ? ? ? 則組合數(shù)C(A,B)與C(a[n],b[n])*C(a[n-1],b[n-1])*...*C(a[0],b[0])??modp同余
? ? ? ? 即：Lucas(n,m,p)=c(n%p,m%p)*Lucas(n/p,m/p,p)?因為要用到相除、取模、所以p要求是素數(shù)
4.所有的偶數(shù)（2除外）都可以用兩個素數(shù)的和來表示
5. 求兩個分?jǐn)?shù)的最大公約數(shù) b/a,d/c
? ? ?首先把b/a，和d/c分別化簡為最簡公約數(shù)（b、a，d、c.分別除以(a,b)和（d，c）就好啦）
? ? ? 假設(shè)b/a,d/c已經(jīng)是最簡的 那么有 （b/a,d/c)=(b,d)/lcm(a,c)
? 求兩個分?jǐn)?shù)的最小公倍數(shù)（假設(shè)同上）
?? ? ?lcm(b/a,d/c)=lcm(a,c)/(b,d)?
6. ??(a,b)=c,若 i = a/c，j = b/c，則(i+j)與(i*j)互質(zhì)。 ?a和b兩個數(shù)，使得x+y=a,lcm(x,y)=b, 那么有g(shù)cd(a,b)=gcd(x,y);
總結(jié)
