第一章 整除
素数(质数,不可约数) 除了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的公约数 辗转相除法:将求两个较大数的公因数转化为求两个较小数的公因数

