歐幾里得定理

$gcd(a,b)=gcd(a\%b,b)$(a>=b)
給出簡(jiǎn)單證明:
可以知道$gcd(a,b)<=b且為b的因子$
$a=mb+r$容易得到左邊的mb部分一定可以被b的所有因子整除,所以不會(huì)對(duì)結(jié)果造成影響，所以得證對(duì)于a>=b,$gcd(a,b)=gcd(a\%b,b)$。
遞歸求解,當(dāng)b=0時(shí)返回a即可。

拓展性質(zhì):對(duì)于a>=b,$gcd(a,b)=gcd(a?b,b)$=$gcd(a+b,b)$
即$gcd(a+k?b,b)=gcd(a,b)$,k為整數(shù)

裴蜀定理(貝祖定理)

$ax+by=gcd(a,b)$
對(duì)于$a$,$b$的$gcd(a,b)$,一定存在系數(shù)x和y，使得:
$ax+by=gcd(a,b)$

拓展歐幾里得定理

對(duì)貝祖定理系數(shù)的求解過程稱為拓展歐幾里得定理

ll exgcd(ll a,ll b,ll &x,ll &y) {if(b==0){x=1;y=0;return a;}else {ll g=exgcd( b, a % b, y, x);y -= a / b * x;return g;} }

證明:
$a{x}_1+b{y}_1=gcd(a,b)$
$b{x}_2+(a\%b)y_2=gcd(a,b)$
聯(lián)立兩個(gè)等式可得：
$a?x_1+b?y_1$
$=b?x_2+(a\%b)y_2$
$=b?x_2+(a?a/b?b)y_2$
$=a?y_2+b?(x_2?a/b?y_2)$
可以得到:
$x_1=y_2$
$y_1=x_2?a/b?y_2$

定理的一些基本應(yīng)用
1.求$x$模$p$的逆元
2.關(guān)于系數(shù)的變化
對(duì)于 $ax+by=gcd(a,b)$
兩邊同除以$gcd(a,b)$,
則a與b變成了素?cái)?shù)p和q,
$px+qy=1$
系數(shù)x,y可以隨意變動(dòng),
$x$每增大$q$,$y$就減少$p$,反之亦然。

算數(shù)基本定理：

一個(gè)數(shù)可被唯一地表示成若干個(gè)素?cái)?shù)的乘積。
$x=p_1^{cn{t}_1}?p_2^{cn{t}_2}?p_3^{cn{t}_3}???p_n^{cn{t}_n}$
$cn{t}_i$表示x分解后的乘積表達(dá)式中有$cn{t}_i$個(gè)$p_i$.
定理的一些基本應(yīng)用
1.求出x的因子個(gè)數(shù)
$factorCnt=(cn{t}_1+1)?(cn{t}_2+1)???(cn{t}_n+1)$
2.更好地理解$gcd(最大公因數(shù))$
$gcd(a,b)=p_1^{min(cnt{a}_1,cnt{b}_1)}?p_2^{min(cnt{a}_2,cnt{b}_2)}???p_n^{min(cnt{a}_n,cnt{b}_n)}$
3.更好地理解$lcm(最小公倍數(shù))$
$lcm(a,b)=p_1^{max(cnt{a}_1,cnt{b}_1)}?p_2^{max(cnt{a}_2,cnt{b}_2)}???p_n^{max(cnt{a}_n,cnt{b}_n)}$

費(fèi)馬小定理

如果p是一個(gè)質(zhì)數(shù)，而整數(shù)a不是p的倍數(shù)，那么$1.$$a^{p}modp=$$amodp$.
$2.$$a^{p?1}modp$$=1modp$.
應(yīng)用:
1.求一個(gè)數(shù)x模p的逆元y
$y=x^{p?2}$
證明:
$$\begin{gathered} x?y \\ =x?x^{p?2} \\ =x^{p?1}modp \\ =1(此處由費(fèi)馬小定理得出) \end{gathered}$$
因?yàn)槿∧＿\(yùn)算后的結(jié)果已經(jīng)不能簡(jiǎn)單地用除法，所以我們引入了乘法逆元的概念,即你如果在模p條件下想除以一個(gè)數(shù),只能用乘以它的逆元代替。
證明可以看下文的完全剩余系

互質(zhì)的判斷

若$gcd(x,y)=1，表明x,y互質(zhì)$
拓展性質(zhì):
若$x和y互質(zhì)，$
1.$gcd(x+y,x?y)=1$
證明：x和y互質(zhì)表明它們沒有共同的質(zhì)因子,另$z=x?y$，顯然z具有x,y所有的質(zhì)因子。
而$x+y$要存在至少一個(gè)x或y的因子的條件是:$x+y$能夠整除這些質(zhì)因子,但因?yàn)?span id="ze8trgl8bvbq" class="katex--inline">$x+y$合并時(shí),x和y沒有一個(gè)共同的質(zhì)因數(shù),所以相加后這些質(zhì)數(shù)并未能保留，全部變成了別的質(zhì)因數(shù)。所以,$gcd(x+y,x?y)=1$.

歐拉函數(shù)

定義：對(duì)于正整數(shù)n,歐拉函數(shù)φ(n)是小于n的正整數(shù)中與n互質(zhì)的數(shù)的數(shù)目.
1.對(duì)于素?cái)?shù)p,$\phi (p)=p?1$
2.對(duì)于素?cái)?shù)p,$\phi (p^k)=p^k?p^{k?1}$
3.若$p_1$與$p_2$互質(zhì), 那么$\phi (p_1{p}_2)=\phi (p_1)\phi (p_2)$
證明：如果a與p1互質(zhì)(a<p1)，b與p2互質(zhì)(b<p2)，c與p1p2互質(zhì)(c<p1p2)，則c與數(shù)對(duì) (a,b) 是一一對(duì)應(yīng)關(guān)系。由于a的值有φ(p1)種可能，b的值有φ(p2)種可能，則數(shù)對(duì) (a,b) 有$\phi (p1)\phi (p2)$種可能，而c的值有$\phi (p1p2)$種可能，所以$\phi (p1p2)$就等于$\phi (p1)\phi (p2)$。
4.對(duì)于一個(gè)有多個(gè)質(zhì)因子的數(shù)x,
$x(x=p_1^{k_1}{p}_2^{k_2}?p_n^{k_n})$,
由第三個(gè)性質(zhì)可得：
$\phi (x)=\phi (p_1^{k_1})\phi (p_2^{k_2})?\phi (p_n^{k_n})$
由第四個(gè)性質(zhì)可得(n為x不同質(zhì)因數(shù)的個(gè)數(shù))：
$\phi (p_1^{k_1})\phi (p_2^{k_2})?\phi (p_n^{k_n})$$$\begin{gathered} =p_1^{k_1}(1?\frac{1}{p_1})p_2^{k_2}(1?\frac{1}{p_2})?p_n^{k_n}(1?\frac{1}{p_n}) \\ =p_1^{k_1}{p}_2^{k2}?p_n^{k_n}(1?\frac{1}{p_1})(1?\frac{1}{p_2})?(1?\frac{1}{p_n}) \\ =x(1?\frac{1}{p_1})(1?\frac{1}{p_2})?(1?\frac{1}{p_n}) \\ =x{\prod }_{i=1}^n(1?\frac{1}{p_i}) \end{gathered}$$

同余關(guān)系

$加法$
1.如果$a\equiv b且c\equiv d$，那么$a+c\equiv b+d(modm)$
$減法$
2.如果$a\equiv b且c\equiv d$，那么$a?c\equiv b?d(modm)$
$乘法$
3.如果$a\equiv b且c\equiv d$，那么$ac\equiv bd(modm)$
4…如果$a\equiv b且c\equiv d$，那么$a^n\equiv b^n(modm)$
$除法$
只有在滿足d與m互質(zhì)的情況下
$ad\equiv bd(modm)$等價(jià)于$a\equiv b(modm)$,$d=0$
證明:
尋找系數(shù)$d^{\prime }和m^{\prime }$,使得$d{d}^{\prime }+m^{\prime }m=1(d和m互質(zhì),gcd(d,m)=1)$,
那么$ad\equiv bd?ad{d}^{\prime }\equiv bd{d}^{\prime }$
因?yàn)?span id="ze8trgl8bvbq" class="katex--inline">$d{d}^{\prime }=1?m{m}^{\prime }$
所以$a\equiv b$

模數(shù)變化

$ad\equiv bd(modmd)$等價(jià)于$a\equiv b(modm)$
$ad\equiv bd(modm)$等價(jià)于$a\equiv b(mod\frac{m}{gcd(d,m)})$
證明：$d{d}^{\prime }+m{m}^{\prime }=gcd(d,m)$,
這就給出同余式
$a?gcd(d,m)\equiv b?gcd(d,m)(modm)$
$\to a\equiv b(mod\frac{m}{gcd(d,m)})$

$a\equiv b(modmd)$等價(jià)于$a\equiv b(modm)$,$d為整數(shù)$

如果$m\perp n(互質(zhì))$,
$a\equiv b(modmn)$$?a\equiv b(modm)并且a\equiv b(modn)$

中國(guó)剩余定理

找到一個(gè)滿足以下條件并最小的$X$
對(duì)于任意i都滿足,$Xmod{m}_i$=$a_i$$(1<=i<=n)$
要求$m_i$之間互質(zhì)
首先考慮一個(gè)周期性,即找到一個(gè)可行解,該如何處理使得解更小呢?不斷減去周期T即可。
$T={\prod }_{i=1}^n{m}_i$
對(duì)于X，我們不妨考慮找到一個(gè)組合使得X=$\sum x_i$
$x_i$滿足條件$xi\%m_i$=$a_i并且(T/m_i)|x_i$，則這個(gè)$x_i$不會(huì)對(duì)其他$x$造成影響。
怎么找到這個(gè)$x_i$呢？
1.求出$T/m_i$模$m_i$下的逆元$p$
2.令$x_i$=$T/m_i$*p,則乘積模$m_i$為1
3.再把$x_i$乘以$a_i$即可
思考：為什么要求$m_i$之間互質(zhì)呢？
如果$m_i$之間不互質(zhì),那么周期T就不為這個(gè)。
思考：那么如果$m_i$之間不互質(zhì)該怎么辦呢？
把非互質(zhì)的方程組消去,合并成一個(gè)。
用拓展歐幾里得消去其他m非互質(zhì)的方程,合并后的$mod$為$lcm(m_i,m_j)$

大佬博客

歐拉定理

若$gcd(a,m)=1,則a^{\phi (m)}\equiv 1(modm)$

拓展歐拉定理（歐拉降冪公式）

$若gcd(a,p)=1,那么a^b=a^{bmod\phi (p)}$
$否則,若b>=\phi (p),a^b=a^{bmod\phi (p)+\phi (p)}$
$若b<\phi (p),a^b=a^b$

乘法逆元的幾種求法

限制條件
1.拓展歐幾里得(要求a與m互質(zhì))
2.費(fèi)馬小定理(要求a與p互質(zhì),并且p為質(zhì)數(shù))

一些數(shù)學(xué)術(shù)語(摘自百度百科)

剩余類
設(shè)模為n，則根據(jù)余數(shù)可將所有的整數(shù)分為n類，把所有與整數(shù)a模n同余的整數(shù)構(gòu)成的集合叫做模n的一個(gè)剩余類，記作[a]。并把a(bǔ)叫作剩余類[a]的一個(gè)代表元。

完全剩余系
在模n的剩余類中各取一個(gè)元素，則這n個(gè)數(shù)就構(gòu)成了模n的一個(gè)完全剩余系。
簡(jiǎn)化剩余系
簡(jiǎn)化剩余系(reduced residue system)也稱既約剩余系或縮系，是m的完全剩余系中與m互素的數(shù)構(gòu)成的子集，如果模m的一個(gè)剩余類里所有數(shù)都與m互素，就把它叫做與模m互素的剩余類。
在與模m互素的全體剩余類中，從每一個(gè)類中各任取一個(gè)數(shù)作為代表組成的集合，叫做模m的一個(gè)簡(jiǎn)化剩余系。
例如:
模5的一個(gè)簡(jiǎn)化剩余系是1,2,3,4,模10的一個(gè)簡(jiǎn)化剩余系是1,3,7,9,模18的一個(gè)簡(jiǎn)化剩余系是1,5,7,11,13,17

一些引理
1.若a,b,c為任意三個(gè)整數(shù),m為正整數(shù),且$(m,c)=1$,則當(dāng)$ac\equiv bc(modm)$時(shí),有
$a\equiv b(modm)$
證明：
上式等價(jià)于:
$c(a?b)\equiv 0(modm)$
$\because (m,c)=1$
$\therefore a?b\equiv 0(modm)$
$\therefore a\equiv b(modm)$
2.設(shè)$m$是一個(gè)整數(shù)且$m>1$，$b$是一個(gè)整數(shù)且$(m,b)=1$。
如果$a[1],a[2],a[3],a[4],\dots a[m]$是模m的一個(gè)完全剩余系，
則$b?a[1],b?a[2],b?a[3],b?a[4],\dots b?a[m]$也構(gòu)成模m的一個(gè)完全剩余系。
證明采用反證法:
如若存在$b?a[i]\equiv b?a[j]$,那么$b(a[i]?a[j])\equiv 0(modm)$
$又因為(b,m)=1$,則$a[i]\equiv a[j](modm)$,與條件矛盾。
作用
證明費(fèi)馬小定理:如果$(a,p)=1$($p$為素?cái)?shù)),則$a^{p?1}=1$
過程：構(gòu)造素?cái)?shù)p的完全剩余系
$P=\{1,2,3,\dots ,p?1\}$
又$(a,p)=1$,那么根據(jù)引理2,
$Q=\{a,2a,3a,\dots ,(p?1)a\}$也為p的完全剩余系
根據(jù)完全剩余系的性質(zhì)：
$1?2?3???(p?1)\equiv a?2a?3a?\dots ?(p?1)a(modp)$
$(p?1)!\equiv (p?1)!?a^{p?1}(modp)$
消去$(p?1)!$,得到$a^{p?1}\equiv 1(modp)$

盧卡斯定理

Lucas定理是用來求 $c(n,m)modp$
C(n,m)%p=C(n/p,m/p)*C(n%p,m%p)%p

ll lucas(ll n,ll m,ll mod) {if(!m)return 1;return C(n%mod,m%mod,mod)*lucas(n/mod,m/mod,mod)%mod; }

總結(jié)

以上是生活随笔為你收集整理的数论入门篇的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。