欧几里得算法是一种求解两非负数最大公约数的过程,它本质上就是执行辗转相除法。

    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\)的最小非负整数解。

求解:

  1. 令\(M=\prod_{i=1}^{k} m_{i}\),即\(M\)是所有\(m_i\)的最小公倍数;
  2. 由于\(m_i\)两两互素,所以\(\frac{M}{m_{i}}\)与\(m_i\)亦互素,根据上述贝祖定理推论,可有\(\frac{M}{m_{i}} t_{i} \equiv 1\left(\bmod m_{i}\right)\);
  3. 则有一个解为\(x=\sum_{i=1}^{k} a_{i} \frac{M}{m_{i}} t_{i}\),通解为\(x+i * M(i \in Z)\),特别的,最小非负整数解为\((x \% M+M) \% M\)。

证明:

  1. 由\(\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)\);
  2. 又\(\forall k \downarrow=i, a_{i} \frac{M}{m_{i}} t_{i} \equiv 0\left(\bmod m_{k}\right)\);
  3. 将两式代入原方程,易得[其中一解]\(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

01-05 08:13