博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
回档|欧几里得算法和扩展欧几里得算法
阅读量:5878 次
发布时间:2019-06-19

本文共 672 字,大约阅读时间需要 2 分钟。

欧几里得算法:用于求两个非负整数a、b的最大公因数(用gcd(a,b)表示)。这里用d表示,假设d一定存在。

证明:由题设知d|a,d|b(d|a代表d能整除a,即a mod d=0)
 

      设a=kb+r,这里k和r都是整数。则r=a mod b。
       我们可以让a=n1d,b=n2d。则r=(n1-k*n2)d
       ∴d|r  ∴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。
  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,所以递归可以结束。

转载于:https://www.cnblogs.com/Shymuel/p/4393570.html

你可能感兴趣的文章
Java I/O系统基础知识
查看>>
Java多线程设计模式(2)生产者与消费者模式
查看>>
基于whoosh的flask全文搜索插件flask-msearch
查看>>
对象并不一定都是在堆上分配内存的
查看>>
刘宇凡:罗永浩的锤子情怀只能拿去喂狗
查看>>
PHP学习笔记 第十讲 MYSQL在PHP5中的应用
查看>>
php晚了8小时 PHP5中的时间相差8小时的解决办法
查看>>
JS(JavaScript)的初了解7(更新中···)
查看>>
svn文件管理器的使用
查看>>
Ansible playbook 使用
查看>>
for/foreach/linq执行效率测试
查看>>
js /jquery停止事件冒泡和阻止浏览器默认事件
查看>>
杭电1698--Just a Hook(线段树, 区间更新)
查看>>
长春理工大学第十四届程序设计竞赛(重现赛)I.Fate Grand Order
查看>>
好作品地址
查看>>
[翻译]Protocol Buffer 基础: C++
查看>>
runloop与线程的关系
查看>>
[Bzoj2246]迷宫探险(概率+DP)
查看>>
[译] 感受 4px 基线网格带来的便利
查看>>
oracle常用函数
查看>>