整除与同余

整除

定义

$\exists q \in \mathbb{Z}$ 使得 $b = a \cdot q$ 则$a \mid b$，其中$a$是$b$的因数，$b$是$a$的倍数

性质

  1. $a\mid b$ 且 $a\mid c$，则$a\mid (b\pm c)$
  2. $a\mid b$，若$c\neq 0$，则$a\mid b\cdot c$
  3. 若$ a\mid b $ 且 $b\mid c$，则$a\mid c$
  4. 若 $a\mid b$ 且 $a\mid c$，$\forall x,y \in \mathbb{Z}\setminus{0}$，存在$a\mid (b\cdot x+c\cdot y)$
  5. 若 $a\mid b$，$\forall m\neq 0$，有$(m\cdot a)\mid (m\cdot b)$
  6. 若 $a\mid n$ 且 $b\mid n$ ，$ \exists x,y \in \mathbb{Z}$ ，满足 $a\cdot x+b\cdot y=1$ 时，有 $(a\cdot b)\mid n$

证明

  1. $a\mid b$ 且 $a\mid c$，则$a\mid (b\pm c)$

    设$b = qa$ 且 $c=pa$
    $\therefore b\pm c = qa\pm pa = (p+q)\cdot a$
    $\therefore a\mid b\pm c$

  2. $a\mid b$，若$c\neq 0$，则$a\mid b\cdot c$

    设$b = qa$
    $\therefore b\cdot c = q\cdot a\cdot c$
    $\therefore a\mid b\cdot c$

  3. 若$ a\mid b $ 且 $b\mid c$，则$a\mid c$

    设$b = qa$ 且 $c=pb$
    则$c=pb=p\cdot q\cdot a$
    $\therefore a\mid c$

  4. 若 $a\mid b$ 且 $a\mid c$，$\forall x,y \in \mathbb{Z}\setminus{0}$，存在$a\mid (b\cdot x+c\cdot y)$

    参考1与2的证明

  5. 若 $a\mid b$，$\forall m\neq 0$，有$(m\cdot a)\mid (m\cdot b)$

    设$b = qa$
    则$mb=m\cdot a\cdot q$
    $\therefore (m\cdot a)\mid (m\cdot b)$

  6. 若 $a\mid n$ 且 $b\mid n$ ，$ \exists x,y \in \mathbb{Z}$ ，满足 $a\cdot x+b\cdot y=1$ 时，有 $(a\cdot b)\mid n$

    由题意得：$ab\mid bn$，$ab\mid an$
    $\therefore ab\mid an\cdot x+bn\cdot y$（由4得）
    $\therefore ab\mid (ax+by)\cdot n$
    $\because ax+by=0$
    $\therefore ab\mid n$

同余

待更新。。。

参考文献