初等数论（第三版）定理合集

2023-11-21 14:43:40

初等数论

第一章整除理论

§1

定理1

设 $P(n)$ 是关于自然数 $n$ 的一种性质或命题，若

当 $n=1$ 时，$P(1)$ 成立
由 $P(n)$ 成立必可推出 $P(n+1)$ 成立

那么 $P(n)$ 对所有自然数 $n$ 成立

定理2

设 $T$ 是 $\mathbb{N}$ 的一个非空子集，那么，必有 $t_0\in T$，使对任意的 $t\in T$ 有 $t \leq t_0$

定理3

设 $M$ 是 $\mathbb{N}$ 的一个非空子集，若 $M$ 有上界，那么，必有 $m_0\in M$，使得对任意的 $m\in M$ 有 $m\leq m_0$

定理四

设 $P(n)$ 是关于自然数 $n$ 的一种性质或命题，若

当 $n=1$ 时，$P(1)$ 成立
对 $n>1$，若对所有的自然数 $m<n$，$P(m)$成立，则必可推出 $P(n+1)$ 成立

那么$ P(n)$ 对所有自然数 $n$ 成立

定理5

设 $n$ 是一个自然数，现有 $n$ 个盒子和 $n+1$ 个物体，无论怎样把这 $n+1$ 个物体放入这 $n$ 个盒子里，一定有一个盒子被放了两个或两个以上的物体。

§2

定理1

$a\mid b \Leftrightarrow -a\mid b \Leftrightarrow a\mid -b \Leftrightarrow \left\vert a \right\vert\mid\left\vert b \right\vert$
$a\mid b$ 且 $b\mid c \Rightarrow a\mid c$
$a\mid b_1,\cdots,a\mid b_k \Leftrightarrow$ 对任意 $x,y\in \mathbb{Z}$，有 $a\mid b_1x_1+\cdots+b_kx_k$
设 $m\neq 0$,$a\mid b \Leftrightarrow ma\mid mb$
$a\mid b$ 且 $b\mid a \Rightarrow b=\pm a$
设 $b\neq 0$，$a\mid b \Rightarrow \left\vert a \right\vert \leq \left\vert b \right\vert$
设 $a\neq 0$,$b=qa+c$.$a\mid b \Leftrightarrow a\mid c$

定理2

设整数 $b\neq 0$，$d_1,\cdots,d_k$ 是它的全体约数，那么 $b/d_1,\cdots,b/d_k$ 也是它的全体约数

定理3

$a > 1$ 是合数的充分必要条件是

\[a=de,1<d<a,1<e<a \]
若 $d>1$，$q$ 是素数且 $d|q$，则 $d=q$.

定理4

若 $a$ 是合数，则必有素数 $p\mid a$

定理5

设整数 $a\geq 2$,那么 $a$ 一定可表示为素数的乘积，即

\[a=p_1p_2\cdots p_s \]

其中 $p_j(1\leq j\leq s)$ 是素数

推论 6

设整数 $a \geq 2$

若$ a$ 是合数，则必有素数 $p\mid a$,$p\leq a^{\frac{1}{2}}$
若 $a$ 有定理五中的表示式，则必有素数 $p\mid a$,$p\leq a^{\frac{1}{s}}$

定理 7

素数有无穷多个

定理 8

\[(a_1,a_2,\cdots,a_i,\cdots,a_k)=(a_i,a_2,\cdots,a_1,\cdots,a_k)=(-a_1,a_2,\cdots,a_i,\cdots,a_k)=(\left\vert a_1 \right\vert,\left\vert a_2 \right\vert\cdots,\left\vert a_i \right\vert,\cdots,\left\vert a_k \right\vert) \]
若 $a_1\mid a_j,j=2,\cdots,k$,则

\[(a_1,a_2)=(a_1,a_2,\cdots,a_k)=(a_1)=\left\vert a_1 \right\vert \]
对任意整数 $x$

\[(a_1,\cdots,a_k)=(a_1,\cdots,a_k,a_1x) \]
对任意整数 $x$

\[(a_1,a_2,a_3,\cdots,a_k)=(a_1,a_2+a_1x,a_3,\cdots,a_k) \]
若 $p$ 是素数，则

\[(p,a_1,\cdots,a_k)= \begin{cases} p, &p\mid a_j,j=1,2,\cdots,k \1, &p\nmid a_j \end{cases} \]

定理 9

如果存在 $x_1,\cdots,x_k$，使得 $a_1x_1+\cdots+a_kx_k = 1$，则 $a_1,\cdots,a_k$ 是既约的.

定理 10

设正整数 $m \mid (a_1,\cdots,a_k)$.我们有

\[m(a_1/m,\cdots,a_k/m)=(a_1,\cdots,a_k) \]

特别的，有

\[(\frac{a_1}{(a_1,\cdots,a_k)},\cdots,\frac{a_k}{(a_1,\cdots,a_k)})=1 \]

定理 11

\[[a_1,a_2,\cdots,a_i,\cdots,a_k]=[a_i,a_2,\cdots,a_1,\cdots,a_k]=[-a_1,a_2,\cdots,a_i,\cdots,a_k]=[\left\vert a_1 \right\vert,\left\vert a_2 \right\vert\cdots,\left\vert a_i \right\vert,\cdots,\left\vert a_k \right\vert] \]
若 $a_j \mid a_1 (2\leq j\leq k)$，则

\[[a_1,\cdots,a_k]=\left\vert a_1 \right\vert \]
对任意的 $d\mid a_1$

\[[a_1,a_2]=[a_1,a_2,d];[a_1,\cdots,a_k]=[a_1,\cdots,a_k,d] \]

定理 12

设 $m > 0$.我们有

\[[ma_1,\cdots,ma_k]=m[a_1,\cdots,a_k] \]

§3

定理 1

设 $a,b$ 是两个给定的整数，$a\neq 0$，那么，一定存在唯一的一对整数 $q$ 与 $r$，满足

\[b=qa+r,0\leq r<\left\vert a \right\vert \]

此外，$a \mid b$ 的充分必要条件是 $r=0$

定理 2

设 $a,b$ 是两个给定的整数，$a\neq 0$；再设 $d$ 是一给定的整数。那么，一定存在唯一的一对整数 $q_1$ 与 $r_1$，满足

\[b=q_1a+r_1,d\leq r_1<\left\vert a \right\vert+d \]

此外，$a\mid b$ 的充分必要条件是 $a\mid r_1$

推论 3

设 $a > 0$

任一整数被 $a$ 除后所得的最小非负余数是且仅是 $0,1,\cdots,a-1$ 这 $a$ 个数中的 $1$ 个
相邻的 $a$ 个整数被 $a$ 除后，恰好取到这 $a$ 个余数。特别的，一定有且仅有一个数被 $a$ 整除

定理 4

设 $u_0,u_1$ 是给定的两个整数，$u_1\neq 0$，$u_1 \nmid u_0$.我们一定可以重复应用定理 $1$ 得到下面 $k+1$ 个不等式：

\[u_0=q_0u_1+u_2\u_1=q_1u_2+u_3\u_2=q_2u_3+u_4\\cdots\u_{k-2}=q_{k-2}u_{k-1}+u_k\u_{k-1}=q_{k-1}u_{k}+u_{k+1}\u_k=q_ku_{k+1}\]

以上的算法就称为辗转相除法或 Euclid 算法

§4

定理 1

$a_j\mid c(1\leq j\leq k)$ 的充分必要条件是 $[a_1,\cdots,a_k]\mid c$

定理 2

设 $D$ 是正整数，那么 $D=(a_1,\cdots,a_k)$ 的充分必要条件是：

$D\mid a_j(a\leq j\leq k)$
若 $d \mid a_j(a\leq j \leq k)$，则 $d\mid D$

定理 3

设 $m > 0$,我们有

\[m(b_1,\cdots,b_k)=(mb_1,\cdots,mb_k) \]

定理 4

$(a_1,a_2,a_3,\cdots,a_k)=((a_1,a_2),a_3,\cdots,a_k)$
$(a_1,\cdots,a_{k+r})=((a_1,\cdots,a_k),(a_{k+1},\cdots,a_{k+r}))$

定理 5

设 $(m,a)=1$,则有$ (m,ab)=(m,b)$

定理 6

设 $(m,a)=1$,那么，若 $m\mid ab$，则 $m\mid b$

定理 7

$[a_1,a_2](a_1,a_2)=\left\vert a_1 \right\vert\left\vert a_2 \right\vert$

定理 8

$(a_1,\cdots,a_k)=\min{s=a_1x_1+\cdots+a_kx_k:x_j\in \mathbb{Z}(a\leq j\leq k),s>0}$
一定存在一组整数 $x_{1,0},\cdots,x_{k,0}$,使得

\[(a_1,\cdots,a_k)=a_1x_{1,0}+\cdots +a_kx_{k,0} \]

§5

定理 1

设 $p$ 是素数，$p \mid a_1a_2$，那么 $p\mid a_1$ 或 $p\mid a_2$ 至少有一个成立。一般地，若 $p\mid a_1\cdots a_k$，那么 $p\mid a_1,\cdots,p\mid a_k$ 至少有一个成立。

定理 2

设 $a > 1$，那么必有

\[a=p_1p_2\cdots p_s \]

其中 $p_j (1\leq j\leq s)$ 是素数，且在不计次序的意义下，表示式是唯一的。

推论 3

设 a 由它的标准素因数分解式给出，那么 d 是 a 的正除数的充分必要条件是

\[a=p_1^{e_1}p_2^{e_2}\cdots p_s^{e_s},0\leq e_j\leq \alpha_j,1\leq j\leq s. \]

推论 4

设 $a$ 由它的标准素因数分解式给出，

\[b=p_1^{\beta_1}p_2^{\beta_2}\cdots p_s^{\beta_s} \]

这里允许某个 $\alpha_j$ 或 $\beta_j$ 为零，那么

\[(a,b)= p_1^{\delta_1}p_2^{\delta_2}\cdots p_s^{\delta_s}, \delta_j=\min(\alpha_j,\beta_j), 1\leq j\leq s \]

\[[a,b]= p_1^{\gamma_1}p_2^{\gamma_2}\cdots p_s^{\gamma_s}, \gamma_j=\max(\alpha_j,\beta_j), 1\leq j\leq s \]

以及

\[(a,b)[a,b]=ab. \]

推论 5

若 $(a,b)=1$，$ab=c^k$，那么

\[a=u^k,b=v^k \]

推论 6

设 $a$ 是正整数，$\tau (a)$ 表示 $a$ 的所有正除数的个数.若 $a$ 有标准素因数分解式，则

\[\begin{aligned} \tau(a) &=(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_s+1) \&=\tau(p_1^{\alpha_1})\cdots\tau(p_s^{\alpha_s}). \end{aligned} \]

推论 7

设 $a$ 是正整数， $\sigma(a)$ 表示 $a$ 的所有正除数之和，那么，$\sigma(1)=1$，当 $a$ 有标准素因数分解式时，

\[\begin{aligned} \sigma(a) &=\frac{p_1^{\alpha_1+1}-1}{p_1-1}\cdots\ \frac{p_s^{\alpha_s+1}-1}{p_s-1} \&=\sigma(p_1^{\alpha_1})\cdots\sigma(p_s^{\alpha_s}). \end{aligned} \]

引理 8

设 f(n) 是定义在正整数集合上的复值函数，正整数 a 由它的标准素因数分解式给出，那么

\[\sum_{d\mid a}f(d)=\sum_{e_1=0}^{\alpha_1}\cdots\sum_{e_s=0}^{\alpha_s}f(p_1^{e_1}p_2^{e_2}\cdots p_s^{e_s}) \]

\[\prod_{d\mid a}f(d)=\prod_{e_1=0}^{\alpha_1}\cdots\prod_{e_s=0}^{\alpha_s}f(p_1^{e_1}p_2^{e_2}\cdots p_s^{e_s}) \]

初等数论（第三版）定理合集

码农公寓

初等数论

第一章 整除理论

§1

定理1

定理2

定理3

定理四

定理5

§2

定理1

定理2

定理3

定理4

定理5

推论 6

定理 7

定理 8

定理 9

定理 10

定理 11

定理 12

§3

定理 1

定理 2

推论 3

定理 4

§4

定理 1

定理 2

定理 3

定理 4

定理 5

定理 6

定理 7

定理 8

§5

定理 1

定理 2

推论 3

推论 4

推论 5

推论 6

推论 7

引理 8

相关文章

第一章整除理论