1-1整数

0不是自然数

整除性

定理:设a,b是正整数,则b|a且a|b,当且仅当a=正负b.特别地,a|1当且仅当a=正负1.

证明一下个个位数之和是3的倍数,整齐也是三的倍数:

1-2 素数

(该定义可拓展到负整数,但在本文中仅指正整数) 定义:设n为整数,n>=2,除了1和n以外,没有其他正整数整除n,n称作”素数”(通常用p表示);否则,n称为”合数”. PS:1既不是素数已不是合数 PS:n为合数,则n=ab,其中1<a<n,1<b<n 引理2-1:任何大于1的整数必有素因子. 定理2-1:任何合数n都至少有一个不超过根号n的素因子.(n>1是合数,则存在素数p,使得p<=根号n) 定理2-2:任何非零整数n,可以表示成如下的乘积形式: n=p1^k1p2^k2p3^k3…pn^kn (p1…pn是互不相同的素数,k1..kn是正整数). 欧几里得定理2-3:素数有无穷个

1-3模运算

a mod b:设a,b属于整数,且b>0,如果q,r是整数,满足a=qb+r,且0<=r<b,则定义:a mod b:=r 负数如何求模? 让负数一直加上模数直到为非负数

模运算的性质

b|a <=> a mod b=0
(a + b) % p = (a % p + b % p) % p
(a - b) % p = (a % p - b % p) % p
(a * b) % p = (a % p * b % p) % p
~~除法没有~~
a ^ b % p = ((a % p) ^ b) % p

1-4最大公约数

设a,b是整数,如果d是整数且d|a,d|b,则称d是a和b的公因子(公约数) 如果d>=0,且a和b的所有公因子都整除d,则称d是a和b的最大公约数,记作gcd(a,b). PS:公因子可以是任意整数(包含0,负数) PS:最大公约数只能是0或正整数,不能是负的

欧几里得算法

设a>=b>=0,求gcd(a,b)
数学原理:
b=0时,gcd(a,0)=a #任何整数都是0的公因子
b>0时,gcd(a,b)=gcd(b,r) #a=qb+r,如果d时b和r的因子a=qpd+kd
=>gcd(rn,0)=rn

1-5扩展欧几里得算法

定理5-1:设a,b属于整数,d=gcd(a,b),则存在s,t属于整数,使得as+bt=d

特别的:gcd(a,b)=1<=>as+bt=1

推论:d|v<=>as+bt=v

扩展的欧几里得算法:(又译作”广义欧几里得算法”)

用途:计算as+bt=gcd(a,b)中的 s和t

裴蜀定理：若a,b是整数,且	gcd	(a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立

注意：此处的x和y是整数（即可以是负数）

例如5=gcd(20,15)

5 = 20*(-1) + 15*1

例如1=gcd(3,4)

1 = 3*1 + 4*(-1)

1-6最小公倍数

设a,b属于Z,如果m属于Z,分别是a和b的倍数,m称作a和b的公倍数.

lcm(a,b):a和b的最小公倍数

a,b不等于0:m是a和b所有正的公倍数中最小,m叫作a和b的最小公倍数

如果a,b有一个是0,那么他俩的最小公倍数就是0

1-7证明算术基本定理

等价关系

有时也用~表示集合上的等价关系

否定例子:

同余

定义(同余关系):设a,b,n是整数,n>0,如果n|(a-b),就称a和b在模n下同余,记作a≡b(mod n)

性质:a≡b(mod n)<=> a=qn+b,存在q属于Z

乘法逆元

倒数:两个数的乘积为1

你可能很疑惑为什么会把小数变成一个整数:

首先同模是由等价性的,所以 7/2 mod 5 =(7/2)*1 mod 5

又因为:2 x 3 mod 5 =1

所以(7/2)*1 mod 5= (7/2)*(2*3)mod 5=1

二分之一mod 7 = 4

注意1:模n下互为乘法逆元,一般只考虑比n小的

比如:模5下,2的乘法逆元是3,而不考虑8

注意2:a在模n内的乘法逆元是唯一的

注意3:乘法逆元存在的条件:

gcd(a,n)=1 <=>模n下,a有乘法逆元

一次同余逆元

2x ≡ 3 (mod 6) 因为2无法消除所以这个题无解

一次同余方程 有解的条件

若gcd(a,n)=d,则 ax≡b(mod n)有解 <=> d|b

为什么同模的两个数能同时除一个于n互质的数呢:

首先,我们想要除的这个数与n互质,由逆元,一个数的乘法逆元为分数

那么我们把两边同时称一个要出的这个数的倒数的乘法逆元,

让后把逆元变成要除的这个数的分之一,相乘就等于除了他

剩余类

同余关系(等价关系)

剩余类(等价类)

等价类:设 ~ 是集合S上的等价关系对于a属于S,定义其等价类为

{x ∈ S | x~a+}

剩余类:设a∈Z,定义其剩余类为:{x∈Z |x ≡ a(mod n}

剩余类也有这个性质

剩余类中的每个整数都叫作这个剩余类的代表元

比如:-10,-5,0,5,10等,都是[0]的代表元

剩余类的乘法逆元:

设 u= [a],v=[b] ,则

u和v互为乘法逆元<=>ab≡ 1(mod n)即:

u(和v)有乘法逆元<=>a(和b)与n互素

如果乘法逆元存在的话必然是唯一的

中国剩余定理CRT

在中国这个定理有一个名字叫孙子定理

物不知数:

x≡2(mod 3)

x≡3(mod 5)

x≡2(mod 7)

ni*的-1次方表示的是ni*在模ni的乘法逆元

欧拉定理和费马小定理

设a∈Z*n的乘法阶为k,则以下整数彼此不同:

a的0次方,1次方,2次方,3,次方…….a的k-1次方(所有运算都模n)

二次剩余

模p下二次剩余

p是奇数(p是素数,且p不等于2)

模p^k下的二次剩余

------本文已结束，感谢您的阅读------