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

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

23 人参与  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