扩展欧几里得算法

本文主要是介绍扩展欧几里得算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

Bézout’s定理

∀ a , b ∈ Z \forall a, b \in Z ∀a,b∈Z， ∃ x , y ∈ Z + \exists x,y \in Z^+ ∃x,y∈Z+，使得
a x + b y = g c d ( a , b ) (0) ax + by = gcd(a,b) \tag{0} ax+by=gcd(a,b)(0)

扩展欧几里得算法求该定理的解

已知
g c d ( a , b ) = g c d ( b , a % b ) (1) \begin{aligned} gcd(a, b) = gcd(b, a \% b) \end{aligned} \tag{1} gcd(a,b)=gcd(b,a%b)​(1)
根据 B e ˊ z o u t ′ s Bézout's Beˊzout′s定理， ∃ x ′ , y ′ ∈ Z + \exists x^{'}, y^{'} \in Z^+ ∃x′,y′∈Z+，使得：

b x ′ + ( a % b ) y ′ = g c d ( b , a % b ) (2) \begin{aligned} bx^{'} + (a \% b)y^{'} = gcd(b, a \% b) \end{aligned} \tag{2} bx′+(a%b)y′=gcd(b,a%b)​(2)
又

a % b = a − b ∗ ⌊ a / b ⌋ (3) \begin{aligned} a \% b = a - b * \lfloor a / b \rfloor \end{aligned} \tag{3} a%b=a−b∗⌊a/b⌋​(3)
将 ( 3 ) (3) (3)带入 ( 2 ) (2) (2)，得：

b x ′ + ( a − b ∗ ⌊ a / b ⌋ ) y ′ = g c d ( b , a % b ) a y ′ + b ( x ′ − ⌊ a / b ⌋ y ′ ) = g c d ( b , a % b ) (4) \begin{aligned} bx^{'} + (a - b * \lfloor a / b \rfloor) y^{'} &= gcd(b, a \% b) \\ ay^{'} + b(x^{'} - \lfloor a / b \rfloor y^{'}) &= gcd(b, a \% b) \end{aligned} \tag{4} bx′+(a−b∗⌊a/b⌋)y′ay′+b(x′−⌊a/b⌋y′)​=gcd(b,a%b)=gcd(b,a%b)​(4)
令 x = y ′ x = y^{'} x=y′， y = x ′ − ⌊ a / b ⌋ y ′ y= x^{'} - \lfloor a / b \rfloor y^{'} y=x′−⌊a/b⌋y′，将 ( 1 ) (1) (1)代入 ( 4 ) (4) (4)，整理得：

a x + b y = g c d ( b , a % b ) = g c d ( a , b ) (5) \begin{aligned} ax + by = gcd(b, a \% b) = gcd(a,b) \end{aligned} \tag{5} ax+by=gcd(b,a%b)=gcd(a,b)​(5)
( 5 ) (5) (5)说明，知道 ( 2 ) (2) (2)的解就可以推出定理的解。公式(0)到公式(2)明显是欧几里得算法求解最大公约数的过程。公式(3)，(4)，(5)是说明：公式(0)的解与公式(2)的解的关系。将上述过程归纳成代码形式：

void exgcd(int a, int b, int& x, int& y) {	//公式(0)
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    exgcd(b, a % b, x, y);	//公式(2)
    int tp = x;
    x = y;
    y = tp - a / b * y;
}

参考

• https://www.cnblogs.com/fusiwei/p/11775503.html

这篇关于扩展欧几里得算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！