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

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

12 人参与  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://zhangshiyu.com/post/30795.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

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

最新文章

  • 大雁南飞人不归结局+番外(沈砚之姜曼殊)结局_(大雁南飞人不归结局+番外大雁南飞人不归结局+番外全书结局)结局列表_笔趣阁(沈砚之姜曼殊)
  • 夕拾难觅朝阳苏亦葵厉晏行完本_夕拾难觅朝阳(苏亦葵厉晏行)
  • [老婆豪掷五百万给初恋,重生后我拒当提款机]人气小说未删减节选_唐欣顾承泽萧然小说节选推荐
  • 半堂花夜渡空城免费在线(裴砚泽沈诺柠)_半堂花夜渡空城免费在线
  • 大雁南飞人不归结局+番外优质全章(姜曼殊沈砚之)_大雁南飞人不归结局+番外优质全章姜曼殊沈砚之
  • [绿茶室友邀请我参加祭祖仪式,却不知我是老祖]人物羁绊章节精选_李岚老祖宗苏婧节选免费试读
  • (番外)+(全书)兰因絮果,爱恨全如玉碎+后续+结局(长乐肖风行)全书在线_兰因絮果,爱恨全如玉碎+后续+结局免费列表_笔趣阁(长乐肖风行)
  • 完结文被绿茶养女夺走真千金身份后,我杀疯了列表_完结文被绿茶养女夺走真千金身份后,我杀疯了(苏楠苏意安+)
  • 刹那芳华顾,褚墨景迟文月+番外+后续_刹那芳华顾,褚墨景迟文月+番外+后续列表
  • 被瘾症折磨的可怜校花免费结局+后续(张团团仁川)全书免费_(张团团仁川)被瘾症折磨的可怜校花免费结局+后续后续(张团团仁川)
  • [竹马率十万铁骑娶我,只为给心上人做嫁衣]反转剧情试读片段_尚书府限免完整章节合集‌
  • 方沐筱宋安(重生后,我将兼挑两房的老公一锅端+后续+结局)结局_(方沐筱宋安重生后,我将兼挑两房的老公一锅端+后续+结局全书结局)结局列表_笔趣阁(方沐筱宋安)

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

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