应用背景

作为一只码农每当学习个新知识尤其是数学知识时。我觉得最好得搞清楚它是为了解决一个什么问题。欧几里得算法是为了求两个数的最大公约数Greatest Common Divisor后文都以gcd简称，而拓展欧几里得算法则可以帮助我们求出倒数的模 如果对这个写法不太熟悉，我们换一种表示就是——已知两个正整数a和n，我们想求一个数e使得a与e的乘积除以n的余数为1。而在大名鼎鼎的RSA算法中就有这样一步需要求倒数的模，并且还多加了一个限制条件即a与n互质。

欧几里得算法

拓展欧几里得(简称EEA) 人如其名是基于欧几里得算法(EA) 的，那么我们来回顾下小学所学怎么求两个数m,n的最小公约数 如果这个公式还没勾起你的回忆，那么我们来一段计算过程吧。这里我们求39和69的最大公约数

实话说，小时候学只是机械式地记得这个操作。但当看到EA的表达式后发现写作能够更好地理解它的本质。

拓展欧几里得

一句话为了概括EEA就是求两个数和使得

在具体讲怎么求,之前我想先介绍为什么它能让我们求得倒数的模。如前面提到的A，B两数互质的情况下我们有而我们要求的是所以对等式两边对A取余

下面我们来讲讲怎么一步一步地来求,。改写前面求39和69公约数的式子并令

归纳总结，为了求我们需要和

所以我们有

其中初始的这点我们可以当时来验证

JS代码实现

/*
    扩展欧几里得算法，其中s为alpha,t为beta
    s_i = s_i-2 - s_i-1 * q_i-1
    t_i = t_i-2 - t_i-1 * q_i-t
    初始值
    s_0 = 1    t_0 = 0
    s_1 = 0    t_1 = 1  
*/
const extendedEA = function(a,b){
    if (a < b){
        console.log('Error! a < b');
        return;
    }
    let r = a%b, q = parseInt(a/b);
    let s0 = 1, s1 = 0, t0 = 0, t1 = 1;
    while(r !== 0){
        let s2 = s0 - q*s1, t2 = t0 - q*t1;
        s0 = s1;s1 = s2;
        t0 = t1;t1 = t2;
        a = b;b = r;
        r = a%b;
        q = parseInt(a/b);
    }
    console.log(`gcd: ${b} s: ${s1} t: ${t1}`);
}