数论

内容

数论的噩梦

一、整除约数倍数

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就为最大公约数

代码：

递归

int gcd(int a,int b){return b?gcd(b,a%b):a;}

非递归

int gcd(int x,int y)
{
     int t=y%x;
     while (t!=0)
         y=x,x=t,t=y%x;
     return x;
}

扩欧会以后单独讲。

六、\( \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 )是一个积性函数

证明

(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 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 )，可以同时约去。

所以