当前位置:首页 > 嵌入式培训 > 嵌入式学习 > 讲师博文 >
最大公约数 相关数论知识
时间: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。

最大公约数


发表评论

全国咨询电话:400-611-6270,双休日及节假日请致电值班手机:15010390966

在线咨询: 曹老师QQ(3337544669), 徐老师QQ(1462495461), 刘老师 QQ(3108687497)

企业培训洽谈专线:010-82600901,院校合作洽谈专线:010-82600350,在线咨询:QQ(248856300)

Copyright 2004-2018 华清远见教育集团 版权所有 ,京ICP备16055225号,京公海网安备11010802025203号