首页 > 笔记 > 数论

数论

数论的噩梦

一、整除 约数 倍数

a|b表示b除以a余0,也就是a能整除b。称a是b的约数,b是a的倍数。

若a|b, a|c, 则a|(b+c)

若a|b, 那么对所有整数c, a|bc

若a|b, b|c, 则a|c

二、素数 合数

约数只有1和本身的数是素数,除此以外还有其他约数的数是合数。1既不是素数也不是合数。

三、唯一分解定理

 

每个大于1的自然数均可写为质数的积,而且这些素因子按大小排列之后,写法仅有一种方式。

\(x=a_1^{p_1} \times a_2^{p_2} \cdots a_n^{p_n}\)

 

x的约数个数:

\((p_1+1) \times (p_2+1) \cdots (p_n+1)\)

 

例如

(60=2^2 \times 3 \times 5)

对于2可以取0/1/2个

个数为:(3 \times 2 \times 2=12)

四、最大公约数gcd( )和最小公倍数lcm[ ]

公式:

\(x=a_1^{p_1} \times a_2^{p_2} \cdots a_n^{p_n}\)

\(y=a_1^{q_1} \times a_2^{q_2} \cdots a_n^{q_n}\)

 

\(gcd(x,y)=a_1^{min(p_1,q_1)} \times a_2^{min(p_2,q_2)} \cdots a_n^{min(p_n,q_n)}\)

\(lcm[x,y]=a_1^{max(p_1,q_1)} \times a_2^{max(p_2,q_2)} \cdots a_n^{max(p_n,q_n)}\)

 

\( gcd(a,b)=gcd(a−b,b) \)

\( gcd(a,b)=gcd(a \mod b,a) \)

\( a \times b=gcd(a,b) \times lcm[a,b] \)

因为gcd选的是小的,lcm选的是大的。。

五、欧几里德算法(辗转相除)

gcd(a,b)=gcd(a,a+b)

设 c|a,c|b

所以 c|a+b

若c不整除a 或 c不整除b

c都不整除a+b

所以gcd(a,a+b)属于c,且为最大的

 

推论 gcd(a,b)=gcd(a,a mod b)

就是减了很多次b。。

按照的推论向下推,直到b=0

这是a就为最大公约数

代码:

递归

非递归

扩欧会以后单独讲。

六、\( \sum \)和\( \prod \)

( \sum )连加

\( \sum_{i=1}^{n}=1+2+3 \cdots +n\)

( \prod )连乘

\( \prod_{i=1}^{n}=1 \times 2 \times 3 \cdots \times n\)

都满足交换律分配律

七、其他符号约定&&高斯函数

[条件]=0(如果条件为假)或1(如果条件为真)

高斯函数

([x])或( \lceil x \rceil ) 表示不超过x的最大的整数(向上取整)

( \lfloor x \rfloor ) 表示不小于x的最小的整数(向下取整)

计算机中的取整为向0取整!

八、欧拉函数

( \varphi (n))表示小于n的数中中与n互质的数的个数,特殊地,( \varphi (1)=1)

性质:

(1)

\( \varphi (p)=p-1  |  p为质数\)

证明:p只有p和1两个约数

(2)

\( \varphi (p^k)=(p-1)p^{k-1}  |  p为质数\)

证明( \varphi (p^k)=p^k-(p-1)^{k-1}=(p-1)p^{k-1} )

即(1 \cdots p^k)中只有( \frac{p^k}{p}=p^{k-1})个数和(p^k)不互质,其余的数都和(p^k)互质

可以推广一下

\( \varphi (n)= \prod_i p_i^{k_i-1}(p_i-1),n= \prod_i p_i^{k_i}\)

我们可以发现每一个(p_i^{k_i})都是互质,那么利用( \varphi )是积性函数和唯一分解定理可以证明。

(3)

( \varphi (ab)= \varphi (a) \varphi (b) , gcd(a,b)=1)

说明( \varphi )是一个积性函数

证明

images

(4)

\(n= \sum _{d|n} \varphi (d)\)

证明。。算了

(5)

\( \varphi =n(1- \frac{1}{p_1})(1- \frac{1}{p_2}) \cdots (1- \frac{1}{p_m})\)

可以求( \varphi )

证明:

我们知道了( \varphi (n)= \prod_i p_i^{k_i-1}(p_i-1),n= \prod_i p_i^{k_i})

变形可以得到

( \varphi (n)= \prod_i p_i^{k_i-1} \times \frac{p_i-1}{p_i}=n \times \prod_i (1- \frac{1}{p_i}))

九、同余

a,b对p取模得到相同的余数,称a,b在模p意义下同余,记为(a \equiv b \pmod{p} )

性质:

同余关系的自反、传递、对称性

(a \equiv a \pmod{p})

若(a \equiv b \pmod{p}),则(b \equiv a \pmod{p})

若(a \equiv b \pmod{p}),则(b \equiv a \pmod{p})

若(a \equiv b \pmod{p}),(b \equiv c \pmod{p}),则(a \equiv c \pmod{p})

加减

若(a \equiv b \pmod{p}),(c \equiv b \pmod{p}),则(a \pm c \equiv b \pm d \pmod{p})

若(a \equiv b \pmod{p}),(c \equiv b \pmod{p}),则(a \times c \equiv b \times d \pmod{p})

十、欧拉定理和费马小定理

欧拉定理:若a,p为正整数且(a,p)=1,则满足:

\(a^{ \varphi (p)} \equiv 1 \pmod{p}\)

费马小定理:若a为正整数,p为质数,且(a,p)=1,则满足:

\(a^{p-1} \equiv 1 \pmod{p}\)

证明

引理1

若a,b,c为任意3个整数,m为正整数,且((m,c)=1),则当(a \times c \equiv b \times c \pmod{m})时,有(a \equiv b \pmod{m})

证明:

\(a \times c \equiv b \times c \pmod{m}\)

可得

\(a \times c – b \times c \equiv 0 \pmod{m}\)

可得

\((a – b) \times c \equiv 0 \pmod{m}\)

因为(m,c)=1即m,c互质,c可以约去,

\(a – b \equiv 0 \pmod{m}\)

可得

\(a \equiv b \pmod{m}\)

引理2

设m是一个整数,且m>1,b是一个整数且(m,b)=1.

如果(a_1,a_2,a_3,…a_m)是模m的一个完全剩余系,

则(b \times a[1],b \times a[2],b \times a[3],…b \times a[m])也构成模m的一个完全剩余系.

证明:若存在2个整数ba和ba[j]同余即(b \times a \equiv b \times a[j] \pmod{m}),根据引理1则有(a \equiv a[j] \pmod{m}).

根据完全剩余系的定义可知这是不可能的,因此不存在2个整数ba和ba[j]同余.所以(b \times a[1],b \times a[2],b \times a[3],…b \times a[m])构成模m的一个完全剩余系.

总证明:

构造素数P的即约剩余系

\(P= \{ 1,2,3, \cdots p-1 \} \)

( \because (a,b)=1)由引理二可得

\(A= \{ a,2a,3a, \cdots (p-1)a \} \)

也是P的一个即约剩余系。由即约剩余系的性质

\(1 \times 2 \times 3 \times \cdots (p-1) \equiv a \times 2a \times 3a \times \cdots (p-1)a \pmod{p} \)

\( (p-1)! \equiv (p-1)! \times a^{p-1} \pmod{p}\)

易知( ((p-1)!,p)=1 ),可以同时约去。

所以

\(a^{p-1} \equiv 1 \pmod{p}\)

证毕


1 COMMENT

  1. Pointer2017-12-14 下午9:00

    ceil 返回大于或者等于指定表达式的最小整数(向上取整)
    floor返回小于或者等于指定表达式的最大整数(向下取整)

如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×