gcd && egcd

欧几里德算法（gcd）又称辗转相除法，可用于计算两个整数a,b的最大公约数。

基本思路：设a=qb+r，其中a，b，q，r都是整数，则gcd(a,b)=gcd(b,r),即gcd(a,b)=gcd(b,a%b)。

代码

def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)

扩展欧几里德算法（egcd）

基本思路：对于不全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然存在整数对 x，y ，使得 gcd(a,b)=ax+by。

证明：设 a>b。
　　1，显然当 b=0，gcd（a，b）=a。此时 x=1，y=0；
　　2，ab!=0 时
　　设 ax1+by1=gcd(a,b);
　　bx2+(a mod b)y2=gcd(b,a mod b);
　　根据朴素的欧几里德原理有 gcd(a,b)=gcd(b,a mod b);
　　则:ax1+by1=bx2+(a mod b)y2;
　　即:ax1+by1=bx2+(a-(a/b)*b)y2=ay2+bx2-(a/b)*by2;
　　根据恒等定理得：x1=y2; y1=x2-(a/b)*y2;

     这样我们就得到了求解 x1,y1 的方法：x1，y1 的值基于 x2，y2
　  上面的思想是以递归定义的，因为 gcd 不断的递归求解一定会有个时候 b=0，所以递归可以结束。

代码

def egcd(a,b):
    if b==0:
        return 1,0
    else:
        x,y=egcd(b,a%b)
        return y,x-a/b*y

中国剩余定理CRT

中国剩余定理 (Chinese Remainder Theorem, CRT) 可求解如下形式的一元线性同余方程组（其中$n_1,n_2,...,n_k$两两互质）：
$$
\begin{equation}
\left\{
\begin{array}{lr}
x \equiv a_1 \pmod {n_1} & \\
x \equiv a_2 \pmod {n_2} & \\
......\\
x \equiv a_k \mod {n_k}
\end{array}
\right.
\end{equation}
$$
上面的「物不知数」问题就是一元线性同余方程组的一个实例。

算法步骤：

1.计算所有的模数$n$;
2.对于第$i$个方案:

• 计算$m_i = \frac{n}{n_i}$;
• 计算$m_i$在模$n_i$意义下的逆元$m_i^-1$;
• 计算$c_i = m_i * m_i^-1$ (不要对$n_i$取模);

3.方程组的唯一解为$a = \begin{matrix} \sum_{i=1}^k a_ic_i \end{matrix} \pmod {n}$

代码

from functools import reduce
def egcd(a, b):
    """扩展欧几里得"""
    if 0 == b:
        return 1, 0, a
    x, y, q = egcd(b, a % b)
    x, y = y, (x - a // b * y)
    return x, y, q
def chinese_remainder(pairs):
    """中国剩余定理"""
    mod_list, remainder_list = [p[0] for p in pairs], [p[1] for p in pairs]
    mod_product = reduce(lambda x, y: x * y, mod_list)
    mi_list = [mod_product//x for x in mod_list]
    mi_inverse = [egcd(mi_list[i], mod_list[i])[0] for i in range(len(mi_list))]
    x = 0
    for i in range(len(remainder_list)):
        x += mi_list[i] * mi_inverse[i] * remainder_list[i]
        x %= mod_product
    return x
if __name__=='__main__':
    print(chinese_remainder([(3, 2), (5, 3), (7, 2)]))

费马定理和欧拉定理

费马定理

若$p$是素数，$a$是正整数且不能被$p$整除，则$a^{p-1} \equiv 1 \pmod {p}$。（该形式需要$a$与$p$互素）
另一种有用形式，$p$为素数，$a$为任意正整数，则有$a^p \equiv a \pmod {p}$。

欧拉定理

欧拉函数：指小于$n$且与$n$互素的正整数个数。
对于素数$p$，有$\phi(p) = p-1$
对于两个素数$p$和$q$，有$n=pq$,有
$\phi(n)=\phi(pq)=\phi(p)*\phi(q)=(p-q)*(q-1)$

欧拉定理：对任意互素的$a$和$n$，有$a^{\phi(n)} \equiv 1 \pmod {n}$。
同费马定理一样，有另一种形式$a^{\phi(n)+1} \equiv a \pmod {n}$。