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}$。

Last modification:March 16, 2021
兴趣使然