• 第一章 整数的整除性
  • 整除
  • 素数与合数
  • 带余除法
  • 辗转相除法与最大公约数
  • 最小公倍数
  • 算术基本定理
  • 二元一次不定方程
  • 阅读与欣赏
    • 秦九韶
• 第二章 同余
  • 同余及其基本性质
  • 特殊数的整除特征
  • 剩余类及其运算
  • 剩余系和欧拉函数
  • 欧拉定理
  • 不定方程与同余
• 第三章 同余方程
  • 同余方程的概念
  • 一次同余方程
  • 孙子定理
  • 拉格朗日插值公式
  • 公开密钥码
  • 阅读与欣赏
    • 陈景润

整数

整除的定义

设 $a$ 和 $b$ 是整数， $b \neq 0$，如果存在整数 $c$ 满足 $a=bc$，则称 $b$ 整除 $a$，记为 $b|a$，并称 $b$ 是 $a$的因子或称 $b$ 是 $a$的约数，而称称 $a$ 是 $b$的倍数。如果不存在上述的整数 $c$，则称 $b$ 不整除 $a$，记为 $b \nmid a$。

整除的基本性质

1. $b \mid b$
2. 若 $b \mid a$， $a \mid c$，则 $b\mid c$
3. 若 $b \mid a$，$b \mid c$，则对于任意整数 $x$和 $y$，有 $b \mid (ax+cy)$
4. 若 $b \mid a$， $a \mid b$，则 $b = \pm a$
5. 若$cb \mid ca$，则 $b \mid a$

定理：带余除法

设 $a$ 和 $b$ 是整数， $b \neq 0$，如果存在整数 $q$ 和 $r$ 使得

$$ a=bq+r , 0 \leq r \lt |b| $$

上述 $q$ 和 $r$ 是唯一确定的。整数 $q$ 称为 $a$ 被 $b$ 除的商， $r$ 称为 $a$ 被 $b$ 除所得的余数。

最大公约数的定义

设 $a_1, a_2,a_3,\cdots, a_n$是有限个不全为零的整数，如果存在一个整数 $d$满足下列条件，则称 $d$ 为$a_1, a_2,a_3,\cdots, a_n$的最大公约数

1. d是$a_1, a_2,a_3,\cdots, a_n$的公约数
2. d是$a_1, a_2,a_3,\cdots, a_n$所有公约数中最大者，即如果整数 $d_1$也是$a_1, a_2,a_3,\cdots, a_n$的公约数，则 $d_1 \leq d$