【数论】整除

整除

整除的定义

若

a,b \in \mathbb{Z}

，如果存在

q \in \mathbb{Z}

，且

a=qb

，则称

b

整除

a

，记作

b \mid a

；反之，若不存在

q

，则称

b

不整除

a

，记作

b \nmid a

。

整除的性质

若 $a \mid b$ ， $b \mid c$ ，则 $a \mid c$ ；
若 $a \mid b$ 且 $a \mid c$ ，则 $a \mid bx+cy$ ；
若 $2 \mid a$ ，则 $a$ 为偶数；反之则 $a$ 为奇数;
若 $(a,b)=1$ 且 $a \mid bc$ ，则 $a \mid c$ ；
若 $(a,b)=1$ 且 $a \mid c,b \mid c$ ，则 $ab \mid c$ ；

带余除法定理

若存在

a,b \in \mathbb{Z}

且

b>0

，则存在唯一的

q,r \in \mathbb{Z}

，使得

a=qb+r

。

其中，

a

为被除数，

b

为除数，

q

为商，

r

为余数，且

0 \le r < b

。

等式两边同时除以

b

可得

\dfrac{a}{b}=q+\dfrac{r}{b}

，可得

q=\dfrac{a-r}{b}=\lfloor\dfrac{a}{b}\rfloor

。

由此，不难发现

\dfrac{a-(b-1)}{b}\le q \le \dfrac{a}{b}

。

EG1.若 $n$ 为正整数,令 $\text{r(n)}$ 表示 $n$ 除以 $1,2,\cdots,n$ 的余数和，试证明有无穷多正整数 $n$ 使得 $\text{r(n)}=\text{r(n-1)}$ 。

证明：对每个

k=1,2,\cdots,n

，利用带余除法定理，可得：

\begin{align*} n=q_k \cdot k+r_k \space (0 \le r_k < k) \end{align*}

因此，

q_k=\lfloor \dfrac{n}{k} \rfloor

，就有

r_k=n-\lfloor \dfrac{n}{k} \rfloor \cdot k

。

所以有：

\begin{equation*} \begin{align*} r(n)&=r_1+r_2+\cdots+r_n\\ &=\sum\limits_{k=1}^{n}r_k\\ &=\sum\limits_{k=1}^{n}(n-\lfloor \dfrac{n}{k}\rfloor\cdot k) \end{align*} \end{equation*}

想证有无穷多正整数

n

，使得

r(n)=r(n-1)

，可以考虑：

\begin{equation*} \begin{align*} r(n)-r(n-1)&=\sum\limits_{k=1}^{n}(n-\lfloor\dfrac{n}{k}\rfloor\cdot k)-\sum\limits_{k=1}^{n-1}(n-1-\lfloor\dfrac{n-1}{k}\rfloor\cdot k)\\ &=2n-1-\sum\limits_{k=1}^{n}(\lfloor\dfrac{n}{k}\rfloor-\lfloor\dfrac{n-1}{k}\rfloor)\cdot k \end{align*} \end{equation*}

不难发现，当

k \mid n

时，

\lfloor \dfrac{n}{k}\rfloor-\lfloor\dfrac{n-1}{k}\rfloor=1

；当

k \nmid n

时，上式值为

0

。

因此，

r(n)-r(n-1)=2n-1-\sum\limits_{1 \le k \le n 且 k \mid n}1\cdot k

，也就是要证存在无穷多正整数

n

使得

2n-1=\sum\limits_{1 \le k \le n 且 k \mid n}k

。当

n

取

2^p

，其中

p \in \mathbb{N}

时，上式成立。#

公因子与最大公因子

若 $b \mid a$ ，则称 $a$ 是 $b$ 的倍数， $b$ 是 $a$ 的因子。特别地，若 $b \mid a$ ，则 $\pm b \mid \pm a$ ，并且 $|b|\mid |a|$ 。
若 $a,b \in \mathbb{N^+}$ 且 $b \mid a$ ，则有 $1 \le b \le a$ 。
若 $a,b \in \mathbb{Z}$ 且 $d \mid a$ 且 $d \mid b$ ，则 $d$ 是 $a,b$ 的一个公因子。特别地， $-d$ 也是 $a,b$ 的一个公因子。
若 $a,b \in \mathbb{Z}$ 且 $a,b \neq 0$ ,如果 $d$ 是 $a,b$ 的一个公因子且是最大的，则 $d$ 是 $a,b$ 的最大公因子，记为 $d=(a,b)$ 。

最大公因数的性质

当

a,b \in \mathbb{Z}

时：

$(a,b)=(b,a)=(\pm a,\pm b)=(|a|,|b|)$ 。
$(a,0)=|a|$ ， $(a,1)=1$ 。
$(a,b)=(a-qb,b)$ ，其中 $q \in \mathbb{Z}$ （辗转相除法）。
若 $a,b \neq 0$ 且 $d \mid a$ 且 $d \mid b$ ，则 $d \mid (a,b)$ 。
$(\dfrac{a}{(a,b)},\dfrac{b}{(a,b)})=1$ 。
当 $(a,b)=1$ 时， $a,b$ 互素。
若 $(a,b)=1$ ，则 $(a,bc)=(a,c)$ 。
若 $(a,b)=1$ ，则 $(ab,c)=(a,c)(b,c)$ 。

裴蜀定理

若

a,b \in \mathbb{Z}

且

a,b \neq 0

，那么一定存在

s,t \in \mathbb{Z}

，使得：

\begin{align*} as+bt=(a,b) \end{align*}

Euler定理的简化版本

结论：设 $m$ 为大于 $1$ 的正整数，令 $a \in \mathbb{Z}$ ，且 $(a,m)=1$ ，那么存在 $t \in \mathbb{N^+}$ ，使得 $m \mid a^t-1$ ,其中 $1 \le t < m$ 。

证明：令集合

P=\{a^1,a^2,\cdots,a^m\}

。

因为

(a,m)=1

，所以

(a^i,m)=1

，其中

i=1,2,\cdots,m

。

又因为

a^i

与

m

互素，所以

a^i

除以

m

的余数在

1,2,\cdots,m-1

中。利用抽屉原理，可得存在

1 \le i < j \le m

，使得

a^i

与

a^j

除以

m

的余数相同。因此，有：

\begin{align*} m \mid a^j-a^i=a^i(a^{j-i}-1) \end{align*}

由于

(a^i,m)=1

，有

m \mid a^{j-i}-1

。令

t=j-i

，可得

m \mid a^t-1

。因为

1 \le i < j \le m

，所以

1 \le t \le m-1

。 #

素数与合数

素数与合数的定义

令

\tau (n)

为

n

的所有不同的正因子的个数：

当 $\tau (n)=2$ 时，称 $n$ 为素数；
当 $\tau (n) \ge 3$ 时，称 $n$ 为合数；
当 $\tau (n)=1$ 时，则 $n=1$ 。

Euclid 定理

Euclid

定理：素数有无限多个。

素数的性质

若 $n$ 是大于 $2$ 的正整数，则 $n$ 一定有一个正因子是素数；
若 $p$ 为素数， $n \in \mathbb{Z}$ ，则 $p \mid n$ 或 $(p,n)=1$ ；
若 $p$ 为素数且 $p \mid ab$ ，则 $p \mid a$ 或 $p \mid b$ 。

算数基本定理

如果

n

是一个大于

1

的正整数，那么

n

一定可以拆分为有限个素数之积。

如果不考虑这种拆分的顺序，那么这种拆分方案就是唯一的。因此，我们令：

\begin{align*} n=p_1^{a_1} \cdot p_2^{a_2} \cdots p_t^{a_t} \end{align*}

上式为

n

的标准分解式。

其中，

p_1 < p_2 < \cdots < p_t

为素数，

a_i

为大于

1

的正整数，

i=1,2,\cdots,t

。

注：

$p_1$ 为 $n$ 的最小素因子， $p_t$ 为 $n$ 的最大素因子；
引理：若 $n \in \mathbb{N^+}$ ，则 $n=2^a \cdot b$ ，其中 $2 \nmid b,b \ge 1,a \ge 0$ ；
引理：若 $n \in \mathbb{N^+}$ ，则 $n=a^2\cdot b$ ，其中 $a,b \in \mathbb{N^+}$ 且 $b$ 不能被任意一个大于 $1$ 的数的平方整除（无平方因子）。

文章操作

整除