算术基本定理证明
定理2-2（算术基本定理）：任何非零整数n可以表示出如下乘积形式：n=±p1e1...prer。其中，p1...pr是互不相同的素数，e1...er是正整数.
存在性（任何非零整数n可以表示出如下乘积形式：n=±p1e1...prer）
证明：
n=1：n是0个素数的乘积，存在性成立.
n>1:
假设所有小于n的正整数都可以表示成素数的乘积。
对于n，分两种情况：
若n本身是素数，明显成立.
若n是合数，存在整数1<a<n,1<b<n,使得n=ab.
a,b都可以表示成素数的乘积，那么ab=n也可以，存在性成立.
定理7-1:设p是素数，a,b∈Z，则p|ab→p|a或p|b
推论：设p是素数，a1,...,ak∈Z，则p|a1..ak→p|ai,i∈
唯一性（p1...pr=q1..qs,p1,...pr中可以有重复素数,q1..qs也可以有重复素数）
证明：
r=0:必有s=0,唯一性成立.
r>0:必有s>0.假设r-1时，唯一性成立。对于r，考虑素数p1,既然p1是等式左边的因子，它必然是右边的因子。即：p1|q1...qs.
根据推论，必有qj，使得p1|qj,因为qj是素数，所以p1=qj。
从等式两边消掉p1和qj。左边变成r-1的情况，根据归纳假设，r-1时满足唯一性。
所以r时也满足唯一性.得证.
等价关系
例一：实数集合R，二元关系"="。有：
自反性：对于所有a∈R，都有a=a;
对称性：对于所有a,b∈R，都有a=b→b=a;
传递性：对于所有a,b,c∈R，都有a=b,b=c→a=c;
例二：全体三角形集合T，二元关系"≌".有：
自反性：对于所有△A∈T，都有△A≌△A。
对称性：对于所有△A，△B∈T，都有△A≌△B
传递性：对于所有△A,△B,△C∈T，都有△A≌△B，可知△A≌△C.
定义：设集合S，定义在S上的二元关系R。如果R满足以下性质，则称它为“等价关系”：
自反性：对于所有a∈S，都有(a,a)∈R
对称性：对于所有a,b∈S，都有(a,b)∈R→(b,a)∈R
传递性：对于所有a,b,c∈S→(a,c)∈R
例三：S=R，二元关系R={(x,y):x2=y2,x,y∈S}
自反性：对于所有x∈S，都有x2=x2,所以(x,x)∈R
对称性：对于所有x,y∈S→x2=y2→y2=x2→(y,x)∈R
传递性：对于所有x,y,z∈S，都有(x,y)∈R，(y,z)∈R→x2=y2,y2=z2→x2=z2→(x,z)∈R.
例四（非等价关系）实数集合R、二元关系">".
存在x∈R，x>x不成立.(非自反)
存在x,y∈R，有x>y成立但y>x不成立(非对称)
对于所有x,y,z∈R，都有x>y,y>z→x>z.
同余
a≡b(mod n):设n为正整数，整数a和b分别模n，如果得到相同的余数，就称a和b在模n下满足同余关系(congruence relation)，简称同余.
定义（同余关系）：设a,b,n∈Z，n>0，如果n|(a-b)，就称a和b在模n下同余，记作a≡b(mod n).
令a=q1n+r1,b=q2n+r2。有a-b=(q1-q2)n+(r1-r2)=qn(r1-r2=0).
性质:a≡b(mod n)↔a=qn+b,存在q∈Z
令a=q1n+r,b=q2n+r
有a=q1n+b-q2n
=(q1-q2)n+b
=qn+b
→(a-b)=qn
同余运算法则：
a≡b(mod n)：
a+m≡b+m(mod n),m∈Z
a-m≡b-m(mod n),m∈Z
axm≡bxm(mod n),m∈Z
am≡bm(mod n),m∈N
乘法逆元
定义（乘法逆元）：设a∈Z,n∈N,如果az≡1(mod n),称z是模n下a的乘法逆元,记作a^-1=z.
a的乘法逆元是z=a-1,z=a-1的乘法逆元是a
z-1=(a-1)-1=a((-1)x(-1))=a
有三点需要注意：
1.模n下互为乘法逆元，一般只考虑比n小的.
2.a在模n内的乘法逆元a-1(1<=a-1<n)是唯一的.
3.乘法逆元存在的条件：gcd(a,n)=1 ↔ 模n下,a有乘法逆元.
设gcd(a,n)=d(d>1).
假设a^-1=b,则ab≡1(mod n)，有ab=qn+1,
即ab-qn=1
因为,d|a,d|n
所以,d|1,矛盾，假设不成立.
求乘法逆元
扩展的欧几里得算法：
设gcd(a,n)=1
根据裴蜀定理，有
as+tn=1
等式两边模n，得
as≡1(mod n)
易知，模n下a的逆元是s
标签：...,p1,同余,素数,逆元,乘法,密码学,mod From： https://www.cnblogs.com/xiaoyeah/p/17136726.html