吉法师的博客

不知道能否追到喜欢的人呀,今年努力下吧~ 2022.1.4

初等数论学习

一、整数

1.基础

1.1 良序性质

每个非空的正整数集合都有一个最小元

部分整数集合没有最小元,如小于100的整数,负整数,所有整数。

1.2 证明根号2是无理数

有理数都可以写成p/q的形式,其中p和q是整数

证明

1.3 代数数和超越数

如果x是整系数多项式的根,则称为代数数,如根号2,和任何有理数。

有理数a/b是bx-a的根(a,b是整数且b不为0),所有有理数是代数数。

如果数a不是代数数,则称为超越数,如π,e(1+1/x)^x的极限

1.4 抽屉原理(鸽笼原理)

抽屉原理I:把n+1个苹果放到n个抽屉里,则至少有一个抽屉中有2个或2个以上的苹果。 抽屉原理II:把mxn+r个苹果放到n个抽屉里,则至少有一个抽屉中有不少于m+l个苹果。

1.5 求和符号

100 ←上界 n ∑ i = 1+2+3+4+5+···+100 i=1↘下界 i

1.6 数学归纳法

数学归纳法需要两个步骤:

  1. 设S属于命题里的正整数集合,命题对整数1为真。(基础步骤)

  2. 证明对每个正整数n,n属于S则n+1也疏忽S。(归纳步骤)

数学归纳法

1.7 斐波那契数列

fn = fn-1 + fn-2

如f3 =f1 + f2 = 1+1 = 2 f4 = 3 f5 = 5 f6 = 8 ……

1.8 整除性

a|b 表示a可以整除b。

1.9 整数运算的复杂度

用大O记法来表示。

2 素数

每一个大于1的正素数都有一个素因子

2.1 素性校验

  1. 如果n是一个合数,则n一定有一个不超过根号n的素因子(艾拉托色尼斯筛法)

比如小于100的合数,一定有小于10的素因子,小于10的素数为2,3,5,7,则分别筛去能被2,3,5,7整除的数即可。

  1. 梅森素数

形如2^n - 1的素数

  1. 哥德巴赫猜想

每一个大于2的正偶数可以写成两个素数的和

  1. 欧几里得原理

求(a,b)用辗转相除法,最后一个乘数就是a和b的最大公因数。

2.2 算数基本原理

每一个大于1的正整数都可以被唯一地写成素数的乘积,在乘积中的素因子按照非降序排列。

2.3 因子分解法

试除法

设n是42833,n不能被2,3,5整除,但是7|n,得到42833 = 7 * 6119

6119不能被7,11,13,17,19,23整除,但6119 = 29 * 211

因为 29 >= 根号211 ,所以211是素数,42833 = 7 * 29 * 211

这个方法的素因式分解效率很低。

2.4 特殊的同余式

威尔逊定理

当p是素数时,(p-1)! 可以被p整除


Share