当前位置:首页 > 嵌入式培训 > 嵌入式学习 > 讲师博文 > 最大公约数 相关数论知识

最大公约数 相关数论知识 时间:2018-12-27      来源:华清远见

整除性

一个整数能被另一个整数整除,记为 d|ad|a,意味着对某个整数 k,有a=kda=kd。

余数以及模运算

除法定理: 

对任意整数a和任意正整数n,存在唯一的整数q和r,满足0<=r<n,并且a=qn+r。对任意整数a和任意正整数n,存在唯一的整数q和r,满足0<=r<n,并且a=qn+r。 

取模运算:a % p(或a mod p),表示a除以p的余数。

比如给定一个正整数p,任意一个整数n,一定存在等式 :n = kp + r ;其中 k、r 是整数,且 0 ≤ r < p,则称 k 为 n 除以 p 的商,r 为 n 除以 p 的余数。

取模运算的规则如下:

最大公约数

公约数性质

对任意整数 x 和 y,有: 

d|a并且d|b,则d|(ax+by)d|a并且d|b,则d|(ax+by) 

定义两个不同时为 0 的整数 a 与 b 的最大公约数表示为 gcd(a,b)gcd(a,b),如果 a 和 b 都不为 0,则 gcd(a,b)gcd(a,b) 为一个在 1 和 min(|a|,|b|)min(|a|,|b|) 之间的整数。定义 gcd(0,0)=0gcd(0,0)=0。其基本性质有如下几条:

最大公约数

给出如下定理: 

如果a和b是不都为0的任意整数,则gcd(a,b)是a与b的线性组合{ax+by:x,y均属于整数}中的最小元素。如果a和b是不都为0的任意整数,则gcd(a,b)是a与b的线性组合{ax+by:x,y均属于整数}中的最小元素。 

欧几里得算法

GCD递归定理

对于任意非负整数 a 和任意正整数 b,有 

最大公约数

C语言实现欧几里得算法:

最大公约数

欧几里得算法的扩展形式

最大公约数

推广欧几里得算法以使其可以计算出相应的整系数 x,y。

最大公约数

上一篇:C语言编程软件

下一篇:什么是字符串数组

热点文章推荐
华清学员就业榜单
高薪学员经验分享
热点新闻推荐
前台专线:010-82525158 企业培训洽谈专线:010-82525379 院校合作洽谈专线:010-82525379 Copyright © 2004-2018 北京华清远见科技发展有限公司 版权所有 ,京ICP备16055225号,京公海网安备11010802025203号