当前位置:首页 » 《随便一记》 » 正文

辗转相除法证明_花嵩的博客

5 人参与  2021年11月11日 16:23  分类 : 《随便一记》  评论

点击全文阅读


文章目录

  • 前言
  • 补充:
  • 辗转法证明
  • 总结:

前言

  • 博主实力有限,博文有什么错误,望各位大佬,不吝赐教,非常感谢!
  • 本文证明 求2数的最大公约数的辗转相除法。

补充:

2数互质:公因数只有1的2个非0自然数,称为互质。

如果 2个数a,b存在最大公约数 c即c=gcd(a,b),(gcd是最大公约数的意思)

设 a = mc;b =nc;那么 m与n必互质

证明 如果 m,n不互质,那么m = pd;n=qd;可以知道 a= pdc; b= qdc; 因此 cd将会是 a,b的最大公约数,这与c是a,b的最大公约数相矛盾,因此 m,n互质。

辗转法证明

a/b=x…y

a=xb+y;

辗转法就是证明:gcd(a,b)=gcd(b,y);

设 a ,b的最大公约数是 c

a= m c;

y= c(m-nx);

y= c(m-nx);

我们分析 : n与 m-nx 发现其互质。

证明:

n = qd;m-nx = pd;

因此 a= cd(qx+p);b =cdq;即 cd是 a,b的最大公约数,这与c是a,b的最大共约数矛盾。

因此 n,m-nx互质,这也说明 c也是 b,y的最大公约数。

因此 gcd(a,b)=gcd(b,y)成立。另外如果 b/y = q…r;

那么 gcd(a,b)= gcd(b,y)=gcd(y,r)…

这也就是 为什么 辗转法要连续执行,直到 商为0.

总结:

补充部分的 m,n互质很关键。
另外,2个数的最大共约数与最小公倍数 之积与2数的之积相同即 ab=pq;

点击全文阅读


本文链接:http://m.zhangshiyu.com/post/30795.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • 陈春花,池言(重生后,摆脱吸血鬼老公一家)前文+全本完整阅读预售作品抢先看
  • 错认皇太女后,三个皇夫悔疯了后续结局_春桃长青魏昭看点十足_小说后续在线阅读_无删减免费完结_
  • (重生后,恶毒女配拿稳白月光剧本)江朝华燕景最终篇章(江朝华燕景)全书在线无广告高口碑小说
  • 女儿遇险命悬一线,我却见死不救后续+完结_小姑娘雷达安静读者推荐_小说后续在线阅读_无删减免费完结_
  • 黎夏林意深:结局+番外新上热文新章速递京港缠绵,他独宠娇梅:结局+番外评价五颗星
  • 陈春花,池言小说全文免费阅读(重生后,摆脱吸血鬼老公一家)全文免费阅读无弹窗_陈春花,池言小说全文免费阅读_笔趣阁
  • 女帝采补八百年:出世无敌怎么了?隐藏剧情_苏玄沐禹竹最新阅读_小说后续在线阅读_无删减免费完结_
  • 最新章节(重生后,恶毒女配拿稳白月光剧本)江朝华燕景:结局+番外精品选集附加章节列表
  • 云舒霍骞小说章节目录+章节前文(乡下真千金,带飞全国不装了)TXT清爽版在线
  • 陆晏周岁岁七零:首长娶了全村最懒的婆娘后续(陆晏周岁岁)(七零:首长娶了全村最懒的婆娘)完整章节列表_笔趣阁
  • 毕业告别旅⾏高分言情_姜雪高中毕业白月光每日分享_小说后续在线阅读_无删减免费完结_
  • 甄灵殷温州续集(甄灵殷温州)章节前文+全书阅读(甄灵殷温州)最新连载

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1