素数(质数,不可约数)
除了1和本身没有其他因数是素数,否则是合数.通常素数指正整数.

Euclid算法

Euclid除法,设a,b是两个整数,其中b>0,则存在唯一的整数q,r使得
    a = qb + r ,0 =< r < b
q 叫做a被b除所得的不完全商,r叫做a被b所除的余数.
d=(a,b)=(b,r)

Euclid除法可以理解为用长度为b的尺子去度量长度a,度量最后剩下的一段r不会大于尺子的长度b.

Euclid除法的用途是可以将两个数之间的整除问题转化为计算问题.
判断a是否能够被非零整数b整除的充要条件是a被b所除的余数r=0.

0 =< r < b,r为最小非负余数.
|r| =< b/2,r为绝对值最小余数,在Euclid算法中有加速作用.

若d被能被a,b整除.那么d叫做a,b的公约数

辗转相除法:将求两个较大数的公因数转化为求两个较小数的公因数