整除性

一个整数能被另一个整数整除，记为 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。