另类专区激情视频,AV观看国产

第一章

對(duì)于整數(shù)abc,有 $a=q*b+c$ ，q為整數(shù)，則 $(a,b)=(b,c)$ 可以推出廣義歐幾里得除法
$(0,b)=b$
貝祖等式： $s*a+t*b=(a,b)$
任何一個(gè)整數(shù) $n>1$ 都可以表示為素?cái)?shù)的乘積
如果a是一個(gè)大于1的整數(shù)，則a大于1的最小因數(shù)一定是素?cái)?shù)
如果a是一個(gè)大于1的整數(shù) $\le\sqrt{a}$ 的素?cái)?shù)都除不盡a，則a是素?cái)?shù)
$\pi(x)$ 表示不大于x的素?cái)?shù)的個(gè)數(shù)
最大公因數(shù)：先分解為幾個(gè)素因數(shù)的乘積，然后在公有素因素取出指數(shù)最小的相乘
{a,b},可以分解為素因數(shù)后取指數(shù)最大的相乘
$(a,b)=d$ ,{a,b}=m,則 $ab=dm$ 可求最小公倍數(shù)
標(biāo)準(zhǔn)分解式：
$N = p _1 k_1 … p_ s k_ s , k_ i > 0 N=p_1^{k_1}…p_s^{k_s} , k_i>0 N=p_1k_1??…p_sk_s??,ki?>0且 p_i < p_ j ( i < j ) p_i < p_j (i<j) p_i?<p_j?(i<j) 是素?cái)?shù)$

Q

如何證明一個(gè)數(shù)是素?cái)?shù)：
1.用Eratosthenes篩法（平凡判別P7）具體：對(duì)于一個(gè)數(shù)n，所有 p < n 1 / 2 p< n^{1/2} p<n1/2，均無法整除n，則n是一個(gè)素?cái)?shù)
2.其歐拉函數(shù)即 $φ ( m ) = m ? 1 \varphi(m)=m-1 φ(m)=m?1$ 的時(shí)候，m是一個(gè)素?cái)?shù) P68
3.對(duì)于模m的最小正數(shù)完全剩余系等于其最小正數(shù)簡(jiǎn)化剩余系的時(shí)候，m是一個(gè)素?cái)?shù)
4.利用Wilson定理，如果一個(gè)整數(shù)n， $( n ? 1 ) ! + 1 ≡ 0 m o d n (n-1)!+1\equiv \ 0\ mod\ n (n?1)!+1≡ 0 mod n$ 時(shí)，n是一個(gè)素?cái)?shù) P118

如何計(jì)算兩個(gè)數(shù)的最大公因數(shù)：

1.廣義歐幾里得除法：P22
利用 $（a，b）=（b，c）$ ，一步一步縮小直到0
2.通過貝祖等式： P25
貝祖等式 $s*a + t*b=（a，b）$ 證明在P27

圖片.png

3.如果形式為 $（ 2 a ? 1 ， 2 b ? 1 2^a-1，2^b-1 2a?1，2b?1）$ ，那么其最大公因數(shù)為 2 （ a ， b ） ? 1 2^{（a，b）}-1 2（a，b）?1 P37
4.如果知道這兩個(gè)數(shù)的最小公倍數(shù)，則（a，b）=a*b/[a，b] P39

如何求兩個(gè)數(shù)的最小公倍數(shù)： P39

$[a，b]=a*b/（a，b）$

如何構(gòu)造兩個(gè)互素的數(shù)：

通過（a，b）的性質(zhì)：P33
$（a/（a，b），b/（a，b））$ =1
通過貝祖等式： P33
構(gòu)造一個(gè)ad-bc=1，則（a，b）=1
通過已知的（u，v）=1，構(gòu)造出（a，b）=1 P35

在這里插入圖片描述

只要qrst是單位陣，也就是qt-sr=1，即等式成立
所以對(duì)于 $a=q*u+r*v b=s*u+t*v$
4.通過已知的（a，b）=1，構(gòu)造出 $（ 2 a ? 1 ， 2 b ? 1 2^a-1，2^b-1 2a?1，2b?1）=1$ P37