歐幾里得演算法是一種求解兩非負數最大公約數的程序，它本質上就是執行輾轉相除法，
int gcd(int a,int b) { return b==0?a:gcd(b,a%b); }
可證明最終得到的結果（設為\(r_n\)）就是所求最大公約數：第一步證明\(r_n\)是兩數約束，第二步證明\(r_n\)可被兩數任意約數整除，
貝祖定理：對于不全為 0 的自然數\(a,b\)，必然存在整數\(x,y\)（不唯一）滿足等式\(ax+by=gcd(a, b)\)，使用擴展歐幾里得演算法能夠證明，進而可知，若\(a,b\)互素，那么存在整數\(x,y\)滿足等式\(ax+by=1\)，更進一步，若\(a,b\)互素，總可以找到一個比\(b\)小的非負數\(x\)，使得\(ax=1(\bmod b)\)成立，
中國剩余定理是從一個方程求解程序總結出的定理，
有同余方程組：\(\left\{\begin{array}{l}{x \equiv a_{1}\left(\bmod m_{1}\right)} \\ {x \equiv a_{2}\left(\bmod m_{2}\right)} \\ {\cdots} \\ {x \equiv a_{k}\left(\bmod m_{k}\right)}\end{array}\right.\)，其中\(m_1, m_2, \cdots, m_k\)為兩兩互素整數，求\(x\)的最小非負整數解，
求解：
- 令\(M=\prod_{i=1}^{k} m_{i}\)，即\(M\)是所有\(m_i\)的最小公倍數；
- 由于\(m_i\)兩兩互素，所以\(\frac{M}{m_{i}}\)與\(m_i\)亦互素，根據上述貝祖定理推論，可有\(\frac{M}{m_{i}} t_{i} \equiv 1\left(\bmod m_{i}\right)\)；
- 則有一個解為\(x=\sum_{i=1}^{k} a_{i} \frac{M}{m_{i}} t_{i}\)，通解為\(x+i * M(i \in Z)\)，特別的，最小非負整數解為\((x \% M+M) \% M\)，
證明：
- 由\(\frac{M}{m_{i}} t_{i} \equiv 1\left(\bmod m_{i}\right)\)兩邊同乘\(a_i\)得：\(a_i\frac{M}{m_{i}} t_{i} \equiv a_i\left(\bmod m_{i}\right)\)；
- 又\(\forall k \downarrow=i, a_{i} \frac{M}{m_{i}} t_{i} \equiv 0\left(\bmod m_{k}\right)\)；
- 將兩式代入原方程，易得[其中一解]\(x=\sum_{i=1}^{k} a_{i} \frac{M}{m_{i}} t_{i}\)，
推論：基于上述同余方程組，對于不同的\(\left(a_{1}, a_{2} \dots, a_{k}\right)\)集合，\(0 \leqslant x_{最小非負值} \leqslant M\)取值亦各不相同，此一一對應關系可用于推導歐拉函式，
參考資料：
輾轉相除法的原理
POJ1006: 中國剩余定理的完美演繹
中國剩余定理 && 擴展中國剩余定理
轉載請注明本文出處：https://www.cnblogs.com/newton/p/11720097.html
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/5145.html
標籤：其他
上一篇：數論之歐拉定理
下一篇：<學會提問-批判性思維指南>運用