一、约数和倍数：如果一个整数 $a$ 能被正整数 $b$ 整除，也就是说存在另一个整数 $p$ 使得 $\text{a=bp}$，那么我们就称 $a$ 是 $b$ 的倍数，$b$ 是 $a$ 的约数。

tips:

• 约数和倍数是定义在整数域上的概念。
• 正整数 $a$ 的两个倍数的和或差还是 $a$ 倍数。
• 约数一定是正整数，倍数可以负整数或零。（负整数的约数等价于它的相反数的约数）
• $0$ 的约数为全体正整数。$0$ 没有倍数的定义。

二、公约数和最大公约数：如果正整数 $p$ 同时是两个整数 $a,b$ 的约数，我们就称 $p$ 为 $a$ 和 $b$ 的公约数。$a$ 和 $b$ 的所有公约数中最大的那个数被称为 $a$ 和 $b$ 的最大公约数。

tips:

• $a$ 和 $b$ 的最大公约数记作 $\text{(a,b)}$。
• $\text{(0,0)}$ 不存在。
• $\text{(0,a)=a}$。

三、带余除法：给定一个整数 $a$ 和一个正整数 $q$，总能找到一个整数 $b$ 使得 $\text{a=bq+r}(0≤r＜q)$。我们称 $r$ 为 $a$ 被 $q$ 除的余数。

四、质数：对于一个正整数 $a(1＜a)$，如果 $a$ 只有 $1$ 和 $a$ 两个约数，就称它为质数。两个整数的最大公约数如果为 $1$，就称这两个数是互质的：$\text{(a,b)=1}$。

裴蜀定理：

• 给定两个整数 $a$ 和 $b$，假设他们的最大公约数是 $p$，那么下列方程有整数解当且仅当 $n$ 是 $p$ 的倍数：
  $$\text{ax+by=n}$$

推论一、两个整数 $a$ 和 $b$ 互质当且仅当下列方程有解整数解：
$$\text{ax+by=1}$$

推论二、如果质数 $p$ 整除两个整数 $a$ 和 $b$ 的乘积 $ab$，则 $p$ 必然会整除 $a$ 或 $b$。

证明：

$\text{1.}$ $a$ 的两个倍数相加还是 $a$ 的倍数。

设 $a$ 的两个倍数分别为 $na$ 和 $ma$（$n,m∈Z$）

$\because na+ma=(n+m)a$

$\therefore a$ 的两个倍数相加还是 $a$ 的倍数

$\text{2.}$ 简单论述带余除法的合理性。

把 $q$ 的所有倍数都在数轴上表示出来，
此时，数轴上 $a$ 的位置，必然可以通过 $q$ 的某一个倍数 $bq$ 加上一个正整数 $r$ 且 $0≤r<q$ 得到。

$\text{3.}$ 裴蜀定理的证明。

设 $S= z|z=ax+by,a,b,x,y \in Z$

设 $ca+db \in S$，且 $\forall z \in S,|z|≥ca+db$

设 $\exists$ $z \in S,z\nmid ca+db$

则 $\exists$ $ea+fb=(ca+db)k+t(0≤t<ca+db)$

$\Rightarrow t=(e-ck)a+(f-kd)b$

$\therefore t \in S$，与 $\forall z \in S,|z|≥ca+db$ 矛盾。

$\therefore$ 假设不成立，即：$\forall z \in S,z\mid ca+db$

$\because a,b \in S$

$\therefore a,b \mid ca+db$

即：$ca+db$ 为 $a,b$ 的公约数

$\because (a,b) \mid ax,(a,b) \mid by$

$\therefore (a,b) \mid ax+by,(a,b) \mid ca+db$

$\because$ 最大公约数是公约数的倍数

$\therefore ca+db=(a,b)$

$\text{4.}$ 裴蜀定理推论一证明。

$\text{ax+by=1}$ 有解，$(a,b) \mid 1$。

$\therefore (a,b)=1$，即：方程有解时，$a,b$ 互质。

$\text{5.}$ 裴蜀定理推论二证明。

设 $p \nmid a$ 且 $p \nmid b$

又 $\because p$ 为质数

$\therefore (a,p)=1,(b,p)=1$

$\therefore ax+py=1,bx’+py’=1$ 有解。

$\Rightarrow (ax+py)(bx’+py’)=1$ 有解。

展开得 $p(xx’+xby’+ayx’)+abyy’=1$ 有解。

即：$\text{pX+abY=1}$ 有解。

$\therefore (p,ab)=1$ 与已知矛盾，假设不成立。

$\therefore p \mid a$ 或 $p \mid b$