• 扩展欧几里德算法的推导

    让欧几里德算法应用更广
    服务器君一共花费 8.893 ms 进行了 4 次数据库查询,努力地为您提供了这个页面。
    广告很萌的
    1. Chapter:

    我们再重复一次欧几里得算法:

    gcd(a, b) = gcd(b, a mod b)
    

    由朴素欧几里得算法我们可以得出扩展欧几里德算法:对于不全为 0 的非负整数 a、b,gcd(a,b)表示 a,b 的最大公约数,必然存在整数对 x,y ,使得 gcd(a,b)=ax+by。

    就是给两个整数 a,b 必然存在一对整数 x,y 使得 ax + by = gcd(a,b),这个定理又叫贝祖定理。

    下面我们证明一下:

    假如 a > b, 且 b = 0,那么很明显, ax + by = ax + 0 = gcd(0, a mod 0) = a,也就是 x = 1。扩展欧几里德算法是成立的。

    那么a 和 b 都不为 0 的情况下呢?

    假设

    gcd(a,b) = a * x1 + b * y1;
    // 将 gcd(b, a mod b) 套入上面公式,得 
    gcd(b, a mod b) = b * x2 + (a mod b) * y2;
    

    因为 gcd(a,b) 是和 gcd(b, a mod b) 相等的,所以就有:

    a * x1 + b * y1 = b * x2 + (a mod b) * y2;
    

    (a mod b) 不好参与运算,那么如何将它转化为代数式呢?由模运算法则,我们可以知道 a % b = a - (int)(a/b) * b,举个例子吧,假如 a = 8, b = 5,那么 a % b = 3,就是 a % b = 8 - (int)(8/5) * b = 8 - 1 * 5 = 3。这点模运算知识还是不难的。

    所以等式 a * x1 + b * y1 = b * x2 + (a mod b) * y2 可以进一步表示为:

    a * x1 + b * y1 = b * x2 + (a - (int)(a/b) * b) * y2
    // 也就是
    a * x1 + b * y1 = b * x2 + a * y2 - (int)(a/b) * b * y2 
    // 继续合并同类项
    a * x1 + b * y1 = a * y2 + b ( x2 - (int)(a/b) * y2 )
    

    通过上面最后一个等式,很明显了(根据恒等定理):

    x1 = y2
    y1 = x2 - (int)(a/b) * y2
    

    这两个等式就是我们最后的结论。

    那么这个结论有什么用呢?具体用处我们将在后面讨论,这里就简单提一下。比如你有个上小学的孩子,有天他数学课有道题不懂,要问你:已知等式 47x + 30y = 1; 求x,y的整数解。算了,下一小节再具体讲吧。

    还是那个例子:10 x + 15 y = gcd(10,15) = 5

    怎么写程序求x,y?根据扩展欧几里得算法就可以很容易得出,也就是求解二元一次方程了。

更多 推荐条目

Welcome to NowaMagic Academy!

现代魔法 推荐于 2013-02-27 10:23   

本章最新发布
随机专题
  1. [软件工程与项目管理] 浏览器的HTML解析器 8 个条目
  2. [Linux操作系统] 基本 Linux Shell 命令 2 个条目
  3. [Linux操作系统] CentOS上使用EPEL Repository 2 个条目
  4. [PHP程序设计] PHP里的引用 5 个条目
  5. [数据库技术] 数据库范式篇 5 个条目
  6. [移动开发] Android 网络通信框架Volley 1 个条目
  7. [智力开发与知识管理] 整体性学习步骤 9 个条目
  8. [Python程序设计] urls.py设置技巧 8 个条目
  9. [移动开发] 从代码角度去认识HttpClient 2 个条目
  10. [PHP程序设计] PHP中的Hash算法 3 个条目
  11. [移动开发] Android Studio里的Gradle 3 个条目
  12. [移动开发] 简单了解Android Fragment 3 个条目
窗口