初等数论

第一章 整除理论

§1

定理1

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

1. 当 \(n=1\) 时，\(P(1)\) 成立
2. 由 \(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\) 的一种性质或命题，若

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

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

定理5

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

§2

定理1

1. \(a\mid b \Leftrightarrow -a\mid b \Leftrightarrow a\mid -b \Leftrightarrow \left\vert a \right\vert\mid\left\vert b \right\vert\)
2. \(a\mid b\) 且 \(b\mid c \Rightarrow a\mid c\)
3. \(a\mid b_1,\cdots,a\mid b_k \Leftrightarrow\) 对任意 \(x,y\in \mathbb{Z}\)，有 \(a\mid b_1x_1+\cdots+b_kx_k\)
4. 设 \(m\neq 0\),\(a\mid b \Leftrightarrow ma\mid mb\)
5. \(a\mid b\) 且 \(b\mid a \Rightarrow b=\pm a\)
6. 设 \(b\neq 0\)，\(a\mid b \Rightarrow \left\vert a \right\vert \leq \left\vert b \right\vert\)
7. 设 \(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

1. \(a > 1\) 是合数的充分必要条件是

   \[a=de,1<d<a,1<e<a \]

2. 若 \(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\)

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

定理 7

素数有无穷多个

定理 8

1. \[(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) \]

2. 若 \(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 \]

3. 对任意整数 \(x\)

   \[(a_1,\cdots,a_k)=(a_1,\cdots,a_k,a_1x) \]

4. 对任意整数 \(x\)

   \[(a_1,a_2,a_3,\cdots,a_k)=(a_1,a_2+a_1x,a_3,\cdots,a_k) \]

5. 若 \(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

1. \[[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] \]

2. 若 \(a_j \mid a_1 (2\leq j\leq k)\)，则

   \[[a_1,\cdots,a_k]=\left\vert a_1 \right\vert \]

3. 对任意的 \(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\)

1. 任一整数被 \(a\) 除后所得的最小非负余数是且仅是 \(0,1,\cdots,a-1\) 这 \(a\) 个数中的 \(1\) 个
2. 相邻的 \(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)\) 的充分必要条件是：

1. \(D\mid a_j(a\leq j\leq k)\)
2. 若 \(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

1. \((a_1,a_2,a_3,\cdots,a_k)=((a_1,a_2),a_3,\cdots,a_k)\)
2. \((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

1. \((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}\)

2. 一定存在一组整数 \(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)\) 是素数，且在不计次序的意义下，表示式是唯一的。