• 整除与带余除法是数论的基础，贯穿整个数论

整数

性质

被3整除

  • 一个数的各个位数的数字之和如果能被三整除，那么这个数就能被三整除

被11整除

  • 一个数的奇数位的数字之和 与 偶数位的数字之和 的差能被11整除，那么这个数能被11整除

被7、11整除

  • 如果一个数，它某尾三位组成的三位数 与 末尾三位之前的数字所组成的数 之差 能被11或7整除，那么这个数就能被11或7整除

带余除法

  • 带余除法也被称为欧式除法算式

  • 一般地，整数a，b，b≠0，存在唯一一对整数，q、r，使a=bq+r ， 0≤ r <|b|

素数

最大公因数与最小公倍数

最大公因数

  • 最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。a，b的最大公约数记为（a，b），同样的，a，b，c的最大公约数记为（a，b，c），多个整数的最大公约数也有同样的记号。

  • 仅有两个正因数的正整数，简言之因数只有1和它本身那么这个数就是素数，也被称为质数

  • 不是素数的正整数，且这个数不是1，那么这个正整数就是合数

  • 2是唯一一个偶素数，同时也是最小的素数

  • 每一个素数中，除了1以外最小的正因数是一个素数

  • 任何一个整数都可以分解为几个素数的乘积

判别素数

  • 埃拉托斯特尼筛法（简称埃式筛法）

互素

  • 如果两个整数的最大公因数为1，那么就整这两个整数是互素的

寻找最大公因数

短除法

辗转相除法

同余