歐幾里得與擴(kuò)展歐幾里得

先解釋一下符號(hào)：

$$A\equiv B（modC）符號(hào)代表A模C與B模C相等，即A/C與B/C同余。$$

$inv（a）代表a的逆元$

定義：
$b?b^{?1}\equiv 1(modc)，那么稱b^{?}{1}^{為}b模c的乘法逆元。$
$則Inv（b）=b^{?1}$

定理：

$\frac{a}{b}(\mathrm{m}\mathrm{o}\mathrm{d}c)=a?inv(b)(\mathrm{m}\mathrm{o}\mathrm{d}c)成立的條件是inv(b)存，在即b與c互質(zhì)。$

用途：

乘法逆元可以用來求解部分除法的取模問題（分母是一個(gè)整數(shù)，并且與被取模數(shù)互質(zhì)）
$$b?b^{?1}\equiv 1(modc)$$$$可以轉(zhuǎn)化為使用拓展歐幾里得求解bx+cy=1的解，求解x即為b的逆元$$
證明:
學(xué)數(shù)論不證明，是不能鍛煉邏輯思維能力的。

$$\begin{gathered} 因為a?inv(a)\equiv 1(modc) \\ 所以設(shè)a?inv(a)=k?c+1 \\ 移項(xiàng)得a?inv(a)?k?c=1 \\ 取K=?k得a?inv(a)+K?c=1 \end{gathered}$$
原結(jié)論得證

小技巧：
但是這里的inv(a)可能解除負(fù)值，我們可以再加上c來保證他是正整數(shù)

總結(jié)

以上是生活随笔為你收集整理的数学--数论--（逆元）扩展欧几里求解+证明的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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