初等数论
第一章 整除理论
§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)\) 是素数，且在不计次序的意义下，表示式是唯一的。