鲸鱼的树洞

初等数论笔记

发布于

编辑于


我会将学习初等数论过程中的所有笔记都整理到这里。使用的教材是哈尔滨工业大学出版社出版的《基础数论入门》。


第 1 章 自然数的基本性质

Peano(皮亚诺)公理

  1. 00 是自然数;
  2. 每一个确定的自然数 aa,都有一个确定的后继数 aa'aa' 也是自然数;
  3. 对于每个自然数 bbccb=cb=c 当且仅当 bb 的后继数等于 cc 的后继数;
  4. 00 不是任何自然数的后继数;
  5. 任意关于自然数的命题,如果证明:它对自然数 00 是真的,且假定它对自然数 aa 为真时,可以证明对 aa' 也真。那么,命题对所有自然数都真。

其中第 5 条引出了数学归纳法。

一般用 N\mathbb N 表示自然数集 {0,1,2,}\left\{0, 1, 2,\cdots\right\}

(第一)数学归纳法

任给关于自然数 nn 的一个命题 P(n)P(n), 如果 P(0)P(0) 成立,而且对任何自然数 nn 只要 P(n)P(n) 成立便有 P(n+1)P(n+1) 成立,则命题 P(n)P(n) 对所有自然数成立。

证明:对任意 nNn\in \mathbb N,都有 2nn+12^n\geq n+1

证明:当 n=0n=0 时,200+12^0\geq 0+1 成立。

假设对 nn2nn+12^n\geq n+1,则 2n+12(n+1)=2n+2(n+1)+12^{n+1}\geq 2(n+1)=2n+2\geq (n+1)+1

由归纳法,得对任意 nNn\in \mathbb N,都有 2nn+12^n\geq n+1

数学归纳法(一般形式)

设命题 P(m)P(m) 对于整数 mm0(m0Z)m\geq m_0(m_0\in \mathbb{Z}) 有意义。假定 P(m0)P(m_0) 成立;并且对任何整数 mm0m\geq m_0,如果假设 P(m)P(m) 成立能够得出 P(m+1)P(m+1) 成立,那么对于整数 mm0m\geq m_0 总有 P(m)P(m) 成立。

(第二)数学归纳法(串值归纳法)

任给关于自然数 nn 的一个命题 P(n)P(n), 如果 P(0)P(0) 成立,而且对任何 nNn\in \mathbb{N} 只要 P(0),,P(n)P(0),\cdots ,P(n) 都成立便有 P(n+1)P(n+1),则命题 P(n)P(n) 对所有自然数 nn 成立。

证明:令命题 Q(n)Q(n) 表示 P(0),,P(n)P(0),\cdots ,P(n) 都成立。

nn 进行归纳。P(0)P(0) 成立即 Q(0)Q(0) 成立。

由第一数学归纳法,由 P(0),,P(n)P(0), \cdots ,P(n) 成立可以得出 P(n+1)P(n+1) 成立。

即由 Q(n)Q(n) 成立可以得出 Q(n+1)Q(n+1) 成立。

由第一数学归纳法,Q(n)Q(n) 对所有自然数 nn 成立。从而命题 P(n)P(n) 对所有自然数 nn 成立。

例 1.1

例 1.2

例 1.3

例 1.3

例 1.4

例 1.5

最小数原理

自然数集 N\mathbb{N} 的任一个非空子集必有最小元。

证明:假设 N\mathbb{N} 的一个非空子集 SS 没有最小元。

显然,0S0\notin S。(否则 00 就是 SS 的最小元。)

假设 1,2,,nS1,2,\cdots ,n\notin S,则 n+1Sn+1\notin S。(否则 n+1n+1 就是 SS 的最小元)

因此 SS 为空集,矛盾。因此自然数集 N\mathbb{N} 的任一个非空子集必有最小元。

第 2 章 整除性、素数及算数基本定理

整除的定义

对于 a,bZa, b\in \mathbb{Z},如果有 qZq\in \mathbb{Z} 使得 aq=baq=b,则称 aa 整除 bb,记为 aba\mid b。当 aa 不整除 bb 时,记为 aba\nmid b

Eratosthenes(埃拉托色尼)筛法(埃氏筛法)

m,Nm, N 为正整数,且 N<mN\sqrt{N}<m\le N,则 mm 为素数当且仅当不超过 N\sqrt{N} 的素数都不整除 m。

应用

当筛选 100100 以内的素数时,先把 11 筛去。接着依次将 2,32, 3\cdots 的倍数都筛去。由于 100=10\sqrt{100}=10,因此只需筛去小于等于 1010 的素数之倍数即可。即在这种情况下,只需要筛去 2,3,5,72, 3, 5, 7 的倍数,剩下的就都是素数了;)

Eratosthenes(埃拉托色尼)筛法(埃氏筛法)

证明:若 mm 为素数,则它没有真因子,

从而不被不超过 N\sqrt{N} 的素数所整除。

mm 为合数,则存在 ppqq 使得 m=pqm=pq,且有 pqp\leq q

p=p2pq=mNp=\sqrt{p^2}\leq \sqrt{pq}=\sqrt{m}\leq \sqrt{N}

因此 mm 被不超过 N\sqrt{N} 的素数 pp 所整除。

因此 mm 为素数当且仅当不超过 N\sqrt{N} 的素数都不整除 m。

算数基本定理(整数的唯一分解定理)

任何大于 11 的整数 nn 可表示成有限个(可重复)素数的乘积。当不考虑乘积中因子的顺序时这种分解是唯一的。

根据以上定理,大于 11 的整数 nn 可以唯一地表示为 p1α1prαr{p_1}^{\alpha_1}\cdot \cdots \cdot {p_r}^{\alpha_r} 的形式,其中 p1<<prp_1 <\cdots <p_r 为不同素数,α1,,αr\alpha_1,\cdots ,\alpha_r 为整数。

例 2.1

例 2.2

例 2.3

例 2.4

例 2.5

例 2.6

第三章 带余除法、最大公因数及最小公倍数

带余除法

a,bZa, b\in \mathbb Zb0b\neq0,则有唯一的 q,rZq, r\in \mathbb Z 使得

a=bq+r(0r<b)a=bq+r(0\leq r <\left|b\right|)

证明:(存在性)令 a+bZ={a+bx}a+bZ=\left\{a+bx\right\}

b0b\neq0 可知,(a+bZ)N\left(a+bZ\right)\cap N\neq \varnothing

由最小数定理,(a+bZ)N\left(a+bZ\right)\cap N 有最小元,

记为 r=abq,qZr=a-bq, q\in \mathbb Z,可证 0r<b0\leq r<\left|b\right|

qqrr 即为所有。

最大公因数

a1,,anZa_1,\cdots ,a_n\in \mathbb ZaZa\in \mathbb Z,若对于任意的 ii,有 aaia|a_i,则称 aaa1,,ana_1,\cdots ,a_n 的公因(约)数。

dNd\in \mathbb Naia_i 的公因数,且 aia_i 的任何公因数都整除 dd,则称 dda1,,ana_1,\cdots ,a_n 的最大公因数,记为 d=(a1,,an)d=(a_1,\cdots, a_n)

a1==an=0a_1=\cdots=a_n=0,则 (a1,,an)=0(a_1,\cdots,a_n)=0

aia_i 不全为 00,则 (a1,,an)=max{所有的公因数}(a_1,\cdots,a_n)=\max\left\{\text{所有的公因数}\right\}

公因数是最大公因数的因数,最大公因数是公因数的倍数。

最大公因数可由 aia_i 线性表出,即 d=a1x1++anxnd=a_1x_1+\cdots+a_nx_n,其中 xix_i 不唯一,可由辗转相除法得出。

最小公倍数

a1,,anZa_1,\cdots ,a_n\in \mathbb ZaZa\in \mathbb Z,若对于任意的 ii,有 aiaa_i|a,则称 aaa1,,ana_1,\cdots ,a_n 的公倍数。

mNm\in \mathbb Naia_i 的公倍数,且 mm 整除 aia_i 的任何公倍数,则称 mma1,,ana_1,\cdots ,a_n 的最小公倍数,记为 m=[a1,,an]m=[a_1,\cdots, a_n]

aia_i 中有 00,则 [a1,,an]=0[a_1,\cdots,a_n]=0

aia_i 都不为 00,则 [a1,,an]=max{所有的公倍数}[a_1,\cdots,a_n]=\max\left\{\text{所有}\textbf{正}\text{的公倍数}\right\}

公倍数是最小公倍数的倍数,最小公倍数是公倍数的因数。