初等数论(第三版) 定理合集

2021/8/24 23:36:36

本文主要是介绍初等数论(第三版) 定理合集,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

初等数论

第一章 整除理论

§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)\) 是素数,且在不计次序的意义下,表示式是唯一的。



这篇关于初等数论(第三版) 定理合集的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程