定义 1a,b 为整数,如果 , ,a 必定能整除 b, 记为 (读作 a 整除 b).定理 1假设 ,且 , 则任何 都有 .证明过程:由 可知, 存在 使得 ;两边乘以 c 得到 ,,所以 .定理 2如果 且 ,那么必有 .证明过程: 由 可知,存在 使得 ; 由 可知,存在 使得 ;进而得到 , 又, 所以 .定理 3如果 且 ,则任何 都使得 .证明过程:由可知,存在 使得 ;由可知,存在 使得 ;进而 ,又 ,所以 .定义 2能同时整除非零整数 a,b,且为其中最大的数是这两个数的最大公约数(greatest common divisors),记为 .公理 1两数互质,其最大公约数必为 1.定理 3定理 5能整除两数之差,必定与两数有相同的最大公约数.即 证明过程:由 可知必定存在 :, 使得: 由此可知, 当 r 等于 0 时,当 r 大于0 时,,假设 , 则有定理 5假设 a,b 均为非0整数.以a 为被除数 ,b 为除数相除,求余得 r;用除数作为下一轮的被除数, 用余数作为下一轮的除数求余,以此类推;直到求出最后一个不为0的余数,即为 a,b的最大公约数.