跳到主要内容

算术基本定理证明、等价关系、同余和乘法逆元

算术基本定理证明​

定理2-2(算术基本定理):任何非零整数nn可以表示出如下乘积形式:n=±p1e1…prern=\pm p_1^{e_1}\ldots p_r^{e_r}。其中,p1…prp_1\ldots p_r是互不相同的素数,e1…ere_1\ldots e_r是正整数。

存在性(任何非零整数nn可以表示出如下乘积形式:n=±p1e1…prern=\pm p_1^{e_1}\ldots p_r^{e_r})

证明:

n=1n=1:nn是0个素数的乘积,存在性成立。

n>1n>1:

假设所有小于nn的正整数都可以表示成素数的乘积。

对于nn,分两种情况:

若nn本身是素数,明显成立。

若nn是合数,存在整数1\<a\<n1\<a\<n,1\<b\<n1\<b\<n,使得n=abn=ab。

a,ba,b都可以表示成素数的乘积,那么ab=nab=n也可以,存在性成立。

定理7-1:设pp是素数,a,b∈Za,b\in\mathbb{Z},则p∣ab→p∣ap|ab\rightarrow p|a或p∣bp|b。 推论:设pp是素数,a1,…,ak∈Za_1,\ldots,a_k\in\mathbb{Z},则p∣a1…ak→p∣aip|a_1\ldots a_k\rightarrow p|a_i,i∈{1,k}i\in\{1,k\}。

唯一性(p1…pr=q1…qsp_1\ldots p_r=q_1\ldots q_s,p1,…,prp_1,\ldots,p_r中可以有重复素数,q1,…,qsq_1,\ldots,q_s也可以有重复素数)

证明:

r=0r=0:必有s=0s=0,唯一性成立。

r>0r>0:必有s>0s>0。假设r−1r-1时,唯一性成立。对于rr,考虑素数p1p_1,既然p1p_1是等式左边的因子,它必然是右边的因子。即:p1∣q1…qsp_1|q_1\ldots q_s。

根据推论,必有qjq_j,使得p1∣qjp_1|q_j,因为qjq_j是素数,所以p1=qjp_1=q_j。

从等式两边消掉p1p_1和qjq_j。左边变成r−1r-1的情况,根据归纳假设,r−1r-1时满足唯一性。

所以rr时也满足唯一性。得证。

等价关系​

例一:实数集合R\mathbb{R},二元关系“==”。有: 自反性:对于所有a∈Ra\in\mathbb{R},都有a=aa=a; 对称性:对于所有a,b∈Ra,b\in\mathbb{R},都有a=b→b=aa=b\rightarrow b=a; 传递性:对于所有a,b,c∈Ra,b,c\in\mathbb{R},都有a=b,b=c→a=ca=b,b=c\rightarrow a=c。

例二:全体三角形集合TT,二元关系“≅\cong”。有: 自反性:对于所有△A∈T\triangle A\in T,都有△A≅△A\triangle A\cong\triangle A。 对称性:对于所有△A,△B∈T\triangle A,\triangle B\in T,都有△A≅△B→△B≅△A\triangle A\cong\triangle B\rightarrow\triangle B\cong\triangle A。 传递性:对于所有△A,△B,△C∈T\triangle A,\triangle B,\triangle C\in T,都有△A≅△B\triangle A\cong\triangle B,△B≅△C→△A≅△C\triangle B\cong\triangle C\rightarrow\triangle A\cong\triangle C。

定义:设集合SS,定义在SS上的二元关系RR。如果RR满足以下性质,则称它为“等价关系”:

自反性:对于所有a∈Sa\in S,都有(a,a)∈R(a,a)\in R。

对称性:对于所有a,b∈Sa,b\in S,都有(a,b)∈R→(b,a)∈R(a,b)\in R\rightarrow(b,a)\in R。

传递性:对于所有a,b,c∈Sa,b,c\in S,都有(a,b)∈R,(b,c)∈R→(a,c)∈R(a,b)\in R,(b,c)\in R\rightarrow(a,c)\in R。

例三:S=RS=\mathbb{R},二元关系R={(x,y):x2=y2, x,y∈S}R=\{(x,y):x^2=y^2,\ x,y\in S\}。 自反性:对于所有x∈Sx\in S,都有x2=x2x^2=x^2,所以(x,x)∈R(x,x)\in R。 对称性:对于所有x,y∈Sx,y\in S,x2=y2→y2=x2→(y,x)∈Rx^2=y^2\rightarrow y^2=x^2\rightarrow(y,x)\in R。 传递性:对于所有x,y,z∈Sx,y,z\in S,都有(x,y)∈R(x,y)\in R,(y,z)∈R→x2=y2, y2=z2→x2=z2→(x,z)∈R(y,z)\in R\rightarrow x^2=y^2,\ y^2=z^2\rightarrow x^2=z^2\rightarrow(x,z)\in R。

例四(非等价关系)实数集合R\mathbb{R}、二元关系“>>”。 存在x∈Rx\in\mathbb{R},x>xx>x不成立。(非自反) 存在x,y∈Rx,y\in\mathbb{R},有x>yx>y成立但y>xy>x不成立。(非对称) 对于所有x,y,z∈Rx,y,z\in\mathbb{R},都有x>y, y>z→x>zx>y,\ y>z\rightarrow x>z。

同余​

a≡b(modn)a\equiv b\pmod n:设nn为正整数,整数aa和bb分别模nn,如果得到相同的余数,就称aa和bb在模nn下满足同余关系(congruence relation),简称同余。

定义(同余关系):设a,b,n∈Za,b,n\in\mathbb{Z},n>0n>0,如果n∣(a−b)n\mid(a-b),就称aa和bb在模nn下同余,记作a≡b(modn)a\equiv b\pmod n。

令a=q1n+r1a=q_1n+r_1,b=q2n+r2b=q_2n+r_2。有a−b=(q1−q2)n+(r1−r2)=qna-b=(q_1-q_2)n+(r_1-r_2)=qn(r1−r2=0r_1-r_2=0)。

性质:a≡b(modn)⟷a=qn+ba\equiv b\pmod n\longleftrightarrow a=qn+b,存在q∈Zq\in\mathbb{Z}。

令a=q1n+ra=q_1n+r,b=q2n+rb=q_2n+r,

有a=q1n+b−q2n=(q1−q2)n+b=qn+ba=q_1n+b-q_2n=(q_1-q_2)n+b=qn+b,

→(a−b)=qn\rightarrow(a-b)=qn。

同余运算法则:

a≡b(modn)a\equiv b\pmod n:

a+m≡b+m(modn)a+m\equiv b+m\pmod n,m∈Zm\in\mathbb{Z}。

a−m≡b−m(modn)a-m\equiv b-m\pmod n,m∈Zm\in\mathbb{Z}。

a×m≡b×m(modn)a\times m\equiv b\times m\pmod n,m∈Zm\in\mathbb{Z}。

am≡bm(modn)a^m\equiv b^m\pmod n,m∈Nm\in\mathbb{N}。

乘法逆元​

定义(乘法逆元):设a∈Za\in\mathbb{Z},n∈Nn\in\mathbb{N},如果az≡1(modn)az\equiv1\pmod n,称zz是模nn下aa的乘法逆元,记作a−1=za^{-1}=z。 aa的乘法逆元是z=a−1z=a^{-1},z=a−1z=a^{-1}的乘法逆元是aa。 z−1=(a−1)−1=a(−1)×(−1)=az^{-1}=(a^{-1})^{-1}=a^{(-1)\times(-1)}=a。

有三点需要注意:

  1. 模nn下互为乘法逆元,一般只考虑比nn小的。
  2. aa在模nn内的乘法逆元a−1a^{-1}(1≤a−1\<n1\le a^{-1}\<n)是唯一的。
  3. 乘法逆元存在的条件:gcd⁡(a,n)=1⟷\gcd(a,n)=1\longleftrightarrow模nn下,aa有乘法逆元。

设gcd⁡(a,n)=d (d>1)\gcd(a,n)=d\ (d>1)。 假设a−1=ba^{-1}=b,则ab≡1(modn)ab\equiv1\pmod n,有ab=qn+1ab=qn+1, 即ab−qn=1ab-qn=1。 因为d∣ad\mid a,d∣nd\mid n, 所以d∣1d\mid1,矛盾,假设不成立。

求乘法逆元​

扩展的欧几里得算法:

设gcd⁡(a,n)=1\gcd(a,n)=1,

根据裴蜀定理,有

as+tn=1as+tn=1,

等式两边模nn,得

as≡1(modn)as\equiv1\pmod n,

易知,模nn下aa的逆元是ss。

本文字数:0 字

预计阅读时间:0 分钟


统计信息加载中...

有问题?请向我提出issue