最大公约数GCD学习笔记
2024-09-01 02:55:54
引理
已知:k|a,k|b
求证:k|(m*a+n*b)
证明:∵ k|a
∴ 有p*k=a
同理可得q*k=b
∴ p*k*m=m*a,q*k*n=n*b
∴ k(p*m+q*n)=m*a+n*b
∴ k|(m*a+n*b)
条件:a,b均为正整数
求证:gcd(a,b)=gcd(b,a%b)
证明:设m=gcd(a,b),n=gcd(b,a%b).
则必有p能使p*b+a%b=a;
∵ n=gcd(b,a%b)
∴ n|(p*b+1*a%b)且n|b
∴ n|a 即 n为a,b公约数
∵ m=gcd(a,b)
∴ m>=n
设q,使a-q*b=a%b
∵ m=gcd(a,b)
∴ m|(a-q*b)且m|b
∴ m|(a%b)
∴ m为b,a%b公约数
∵ n=gcd(b,a%b)
∴ n>=m
∴ n=m 命题得证
最后,gcd->伟大光荣正确的党!
最新文章
- python中文字符乱码(GB2312,GBK,GB18030相关的问题)
- Erlang中如何在同一台机器上运行多个erlang节点?
- Python引用模块和查找模块路径
- dede使用方法----实现英文版的搜索功能
- Ubuntu14.04安装intel集显驱动
- html5,进度条
- Delphi word 颜色
- MVC中提示错误:从客户端中检测到有潜在危险的 Request.Form 值的详细解决方法
- 设计模式之:组合模式(Composite)
- Objective-C 获取当前执行函数的名称
- mvc4 membership, [Win32Exception (0x80004005): The system cannot find the file specified]
- vue路由组件群
- python函数式编程之装饰器(二)
- 错误: Error creating bean with name 'studentController': Unsatisfied dependency expressed through field 'studentServiceImpl';
- Go 初体验 - 并发与锁.1 - sync.Mutex 与 sync.RWMutex
- csu1804
- CentOS 7.x默认没有ifconfig?!
- Generative Adversarial Nets[AAE]
- Redis管道
- 软工个人博客作业Week 1
热门文章
- 核心思想:许多公司都没有认识到云储存的革命性(类似QQ把它搞成了用户的家、再也离不开了)
- Delphi在系统菜单中添加菜单项
- 论文阅读计划2(Deep Joint Rain Detection and Removal from a Single Image)
- 程序员该如何过好他的整个职业生涯?(最重要的是你得一直往前走。拐点不是你的工资。想起很久前有个人说我“逻辑性”比较强)good
- C++迭代器 iterator
- WCF研究-中篇
- 通过OSG实现对模型的日照模拟
- 一、Linux常用命令
- 阿里云主机CentOS7设置远程连接MySQL数据库
- sails连接monogodb数据库