数论之整数相关

- 日理万妓 2022-05-25 04:40 75阅读 0赞

近期计划学习区块链，鉴于底层原理基础，主要从两个方向学起，一方面学习区块链相关原理及技术，另一方面从底层支撑开始，学习密码学等底层知识，其中数论作为密码学基础，因此从初等数论着手。

首先那，数论是数学的一个分支，他主要研究的内容是正整数集合，特别重要的是素数。按照研究方法看，分初等数论和高等数论，初等数论研究本质是利用整数环的整除性质，包括整除理论、同余理论、连分数理论。高等数论则包括了更为深刻的数学研究工具。它大致包括代数数论、解析数论、计算数论等等。

数学嘛，是需要做一些题进行练习，本帖主要为整理思路和知识点，方便后期持续学习。目前主要基于《初等数论及其应用》第5版[(\[美\]Kenneth H.Rosen )][Kenneth H.Rosen]。后期不断补充完善。好了，没有时间了，快上车。

良序性质（The Well-Ordering Property）：每个非空的正整数集合都有一个最小元。良序性质作为定义正整数集合的公理。

定义：if ∃p和q,且q≠0，（p、q∈**Z**），s.t r=p/q，则称实数r是有理数，如果r不是有理数则r是无理数。

定理：2^(1/2)是无理数。*可用反证法证明*

定义：如果α是整系数多项式的根，则α称为**代数数**，即∃整数a0，a1,...,an，s.t a0+a1α^1+a2α^2+...+anα^n=0，if α不是代数数，则α为**超越数****。**2^(1/2)是代数数，是x^2-2=0的根。e和π是超越数。

**最大整数函数：**实数x的最大整数（greatest integer）记为\[x\]，是小于或者等于x的最大整数，即\[x\]满足，\[x\] ≤x<\[x\]+1的整数。

**分数部分**：实数x的分数部分（fractional part）记为\{x\}，是x与\[x\]的差，即\{x\}=x-\[x\],因为\[x\] ≤x<\[x\]+1，则0≤\{x\}<1,同样x=\{x\}+\[x\],因此x的最大取整也叫作x的**整数部分**。

定理：（**鸽笼原理**）if把k+1 或者更多的物体放入k个盒子中，那么至少有一个盒子中有两个或者更多的物体。

定理：（狄利克雷逼近定理）if α是一个实数，n是一个正整数，则存在整数a和b，1≤a≤n, s.t |aα-b|<1/n。一个实数的前n个倍数之一必定在某个整数的1/n邻域内。

*  等比数列：通项式![formula][] 前n项和![formula][formula 1]
 *  等差数列：通项公式 ![formula][formula 2]   前n项和 ![formula][formula 3]

**可数集（Countable set）**：是每个元素能与自然数集N的每个元素之间能建立一一对应的集合。如果将可数集的每个元素标上与它对应的那个自然数记号，那么可数集的元素就可以按自然数的顺序排成一个无穷序列a1，a2，a3，…an，…。

定理：有理数集合是可数的。

**乌拉姆数列**是由乌拉姆在1964年提出的。数列的首两项U1和U2定义为1和2，对于n>2，Un为最小而又能刚好以一种方法表达成之前其中两个相异项的和。例如3=1+2，故U3=3；4=1+3（注意2+2不计算在内），故U4=4；5=2+3=1+4，所以它不在数列内。首几项是1, 2, 3, 4, 6, 8, 11, 13, 16, 18, 26, 28, 36, 38, 47, 48, 53, 57, 62, 69, 72, 77, 82, 87, 97, 99...

[Kenneth H.Rosen]: http://www.baidu.com/link?url=0miCz3KCisT1EZ9V3YgFLlJJX9J6lkS2NAFO-IsH_feP5kJQQgPFqC9RNdPM0_x3
[formula]: /images/20220525/3e0f0f6b0c5541d6a1d61ccd82cd4d09.png
[formula 1]: https://ss2.baidu.com/6ONYsjip0QIZ8tyhnq/it/u=1747555526,1280050457&fm=58
[formula 2]: https://ss2.baidu.com/6ONYsjip0QIZ8tyhnq/it/u=420932096,2579434093&fm=58
[formula 3]: /images/20220525/c789da5cac9c41e5af95ff718a9658b6.png