信安数基第一章:整数的可除性

1.1整除的概念,欧几里得除法

1.1.1整除的概念

定义1.1.1:设a,b是任意两个整数,其中b ≠ 0,如果存在一个整数q使得等式
a = q ⋅ b a = q·b a=q⋅b
成立,就称b整除a,记作b\vert a,并把b叫做a的因数,a叫做b的倍数。同时,不是因数也被记为 a ∤ b a\nmid b a∤b

因此:

​ ·0是任何非0整数的倍数

​ ·1是任何整数的因数

​ ·任何整数a是其自身的倍数,也是其自身的因数

此外,因数在遍历时还具有一定的对称性,表现在:

​ ·b遍历整数a的所有因数时,-b也遍历a的所有因数

​ ·b遍历整数a的所有因数时,a/b也遍历a的所有因数

*整除具有传递性:设a,b,c ≠ 0是三个整数,若 c ∣ b c\vert b c∣b, b ∣ a b\vert a b∣a, 则 c ∣ a 则c\vert a 则c∣a

*在加法和减法运算中,整除的性质是保持的=>对于定义1.1.1,在整数a,b的线性组合中,整除的性质是保持的

​ ·上述性质可以推广至任意个整数

例1.16设a,b,c ≠ 0为三个整数, c ∣ a , c ∣ b c\vert a,c\vert b c∣a,c∣b。如果存在整数s,t使得 s ⋅ a + t ⋅ b = 1 s·a + t·b = 1 s⋅a+t⋅b=1,求证:c = ±1

定义1.1.2:设整数n ≠ 0,±1,如果除了显然因数±1和±n外,n没有其他因数,那么n就叫做素数,否则n叫做合数

​ ·1不是质数的原因:保证质因数分解的唯一性

1.1.2素数的埃氏筛法

定理1.1.7:设n为正整数,如果对于所有的素数p ≤ sqrt(n),p都不是n的因数,那么n一定是素数

应用:对任意给定的正整数N,用埃氏筛法求出不超过N的所有素数只需要依次删除不大于sqrt(n)的所有素数除自身以外的所有倍数

信安数基第一章:整数的可除性

*算法实现的思路可以是先找出大于0的最小素数m,然后用埃氏筛法筛出不超过m^2的所有素数;再进行迭代获得更大的

1.1.3欧几里得除法

带余数的除法(对!就是小学学的那个!!!)

定理1.1.9(欧几里得除法):设a,b是两个整数,其中b>0,则存在唯一的整数q,r,使得
a = q ⋅ b + r , 0 ≤ r < b a = q·b + r, 0≤r<b a=q⋅b+r,0≤r<b
其中q叫a被b除所得的不完全商,r为a被b除所得的余数

①定理1.19的存在性证明:

考虑一个整数序列
. . . , − 3 ⋅ b , − 2 ⋅ b , − b , 0 , b , 2 ⋅ b , 3 ⋅ b , . . . ...,-3·b,-2·b,-b,0,b,2·b,3·b,... ...,−3⋅b,−2⋅b,−b,0,b,2⋅b,3⋅b,...
这个序列会将实数轴分成无数个长度为b的区间,而a肯定会落在一个区间内,因此存在一个整数q使得
q ⋅ b ≤ a < ( q + 1 ) ⋅ b q·b≤a<(q+1)·b q⋅b≤a<(q+1)⋅b
令 r = a − q ⋅ b r = a - q·b r=a−q⋅b,则有
a = q ⋅ b + r , 0 ≤ r < b a = q·b + r, 0≤r<b a=q⋅b+r,0≤r<b
②定理1.19的唯一性证明(反证法)

如果分别存在整数q,r与q‘,r’满足定义式,则有
a = q ⋅ b + r , 0 ≤ r < b a = q ′ ⋅ b + r ′ , 0 ≤ r ′ < b a = q·b + r,0≤r<b\\ a = q'·b + r',0≤r'<b a=q⋅b+r,0≤r<ba=q′⋅b+r′,0≤r′<b
两式相减,有
( q − q ′ ) ⋅ b = − ( r − r ′ ) (q-q')·b=-(r-r') (q−q′)⋅b=−(r−r′)
当q≠q‘时,左式绝对值大于等于b,而右式绝对值小于b,这是不可能的,所以矛盾,所以q = q’,r = r‘

定义1.1.4:设x是实数,称x的整数部分为小于等于x的最大整数,记为[x],此时有
[ x ] ≤ x < [ x ] + 1 [x]≤x<[x]+1 [x]≤x<[x]+1

1.1.4素数的平凡判别

*对给定的正整数N,若N被所有不大于sqrt(N)的素数做欧几里得除法的余数都部位0,则N是素数

1.1.5欧几里得除法的一般余数

定理1.1.10(带一般余数的欧几里得除法):设a,b是两个整数,其中b>0,则对任意给定的整数c,存在唯一的整数q,r,使得
a = q ⋅ b + r , c ≤ r < b + c a = q·b + r, c≤r<b+c a=q⋅b+r,c≤r<b+c
定理1.1.10的证明同定理1.1.9

*一些特殊的一般余数:最小非负余数、最小正余数、最大非正余数、最大非负余数、绝对值最小余数(理解就行)

1.2整数的表示

1.2.1b进制

定理1.2.1:设b是大于1的正整数,则每个正整数n都可以唯一的表示成
n = a k − 1 b k − 1 + a k − 2 b k − 2 + . . . + a 1 b + a 0 ( 1.4 ) n = a_{k-1}b^{k-1}+a_{k-2}b^{k-2}+...+a_{1}b+a_0\qquad (1.4)\\ n=ak−1​bk−1+ak−2​bk−2+...+a1​b+a0​(1.4)
其中 a i a_i ai​是整数, 0 ≤ a i ≤ b − 1 , i = 1 , 2 , . . . , k − 1 0≤a_i≤b-1,i=1,2,...,k-1 0≤ai​≤b−1,i=1,2,...,k−1,且首项系数不等于0。

上述定理中b是被表示整数的进制;a是每一位的值

对定义中的式子,有
k − 1 = [ l o g b n ] ( 1.4.2 ) k-1 = [log_bn]\qquad (1.4.2)\\ k−1=[logb​n](1.4.2)
即b进制的整数n有k-1位

定义1.2.1:用以下式表示展开式1.4
n = ( a k − 1 a k − 2 . . . a 1 a 0 ) b ( 1.5 ) n = (a_{k-1}a_{k-2}...a_{1}a_{0})_b\qquad (1.5)\\ n=(ak−1​ak−2​...a1​a0​)b​(1.5)
并称其为整数n的b进制表示

*推论:任何正整数都可以表示成不同的2的幂的和

进制转换

①进制转换时,先用式1.4.2求出b进制下整数n的位数k

②然后用 [ n / ( b k − 1 ) ] [n/(b^{k-1})] [n/(bk−1)]求出最高位系数,为方便表示,记为m

③ n ′ = n − ( b k − 1 ) ⋅ m n' = n-(b^{k-1})·m n′=n−(bk−1)⋅m

④对n’重复步骤①~③直到只有1位且求出该位系数(包括小数)

b进制四则运算

像小学做计算那样列长式就可以(二进制运算有特殊法则,本课不涉及)

1.3最大公因数与广义欧几里得除法

1.3.1最大公因数

定义1.3.1:设 a 1 , a 2 , . . . , a n a_1, a_2, ..., a_n a1​,a2​,...,an​为n个整数(n≥2),若整数d是它们中每一个数的因数,则d就是它们的公因数

​ 如果整数 a 1 , . . . , a n a_1, ..., a_n a1​,...,an​不全为0,那么这些整数所有公因数中最大的一个就叫做 a 1 a_1 a1​到 a n a_n an​的最大公因数,记作 ( a 1 , . . . , a n ) (a_1, ..., a_n) (a1​,...,an​),或者 G C D ( a 1 , . . . , a n ) GCD(a_1, ..., a_n) GCD(a1​,...,an​)

​ 特别地,当 ( a 1 , . . . , a n ) = 1 (a_1,...,a_n) = 1 (a1​,...,an​)=1时,称 a 1 , . . . , a n a_1, ..., a_n a1​,...,an​互质

贝祖(Bézout)定理:若a,b是整数,且 G C D ( a , b ) = d GCD(a,b) = d GCD(a,b)=d,那么对于任意的整数x,y, a ⋅ x + b ⋅ y a·x + b·y a⋅x+b⋅y都一定是d的倍数,特别地,一定存在整数x,y,使得 a ⋅ x + b ⋅ y = d a·x + b·y = d a⋅x+b⋅y=d成立

​ ·贝祖定理的证明附在下面,但是一般不要求掌握

我们设$ d=\gcd(a,b) , 则 显 而 易 见 , ,则显而易见, ,则显而易见,d \mid a , 且 ,且 ,且d \mid b$。

根据整除的性质,我们得出$ d \mid ax+by ( x,y \in Z ) $。······(式1)

所以根据(式1)以及整除的意义得出$ ax+by=dk ( k \in Z^+ ) $。

当 k = 1 k=1 k=1时,则 a x + b y = d ax+by=d ax+by=d。

根据(式1),我们还可以得出 d ∣ x d \mid x d∣x,且 d ∣ y d \mid y d∣y。

至此,定理证毕。

​ ·贝祖定理也可以扩展至任意个整数: a 1 , . . . , a n a_1, ..., a_n a1​,...,an​的最大公因数d是集合
{ s 1 ⋅ a 1 + . . . + s n ⋅ a n ∣ s 1 , . . . , s n ∈ Z } \{s_1·a_1+...+s_n·a_n|s_1,...,s_n\in Z\} {s1​⋅a1​+...+sn​⋅an​∣s1​,...,sn​∈Z}
中的最小正整数

定理1.3.3:设a,b,c是三个不全为零的整数,若 a = q ⋅ b + c a = q·b+c a=q⋅b+c,其中q是整数,则 ( a , b ) = ( b , c ) (a,b) = (b,c) (a,b)=(b,c)。

证:设 d = ( a , b ) d = (a,b) d=(a,b), d ′ = ( b , c ) d'=(b,c) d′=(b,c),则 d ∣ a d\vert a d∣a, d ∣ b d\vert b d∣b,取 a = m ⋅ d a = m·d a=m⋅d, b = n ⋅ d b = n·d b=n⋅d,则 m ⋅ d = q ⋅ n ⋅ d + c m·d = q·n·d+c m⋅d=q⋅n⋅d+c

即 c = ( m − q ⋅ n ) ⋅ d c = (m-q·n)·d c=(m−q⋅n)⋅d,即d是b,c的公倍数,所以 d ≤ d ’ d≤d’ d≤d’

对d‘做相同操作,可得 d ′ ≤ d d'\leq d d′≤d

因此, d = d ′ d = d' d=d′

1.3.2广义欧几里得除法计算最大公因数

广义欧几里得除法

过程的描述:设a,b是任意两个正整数,记 r − 2 = a r_{-2}=a r−2​=a, r − 1 = b r_{-1}=b r−1​=b,反复运用欧几里得除法(辗转相除),有
r − 2 = q 0 ⋅ r − 1 + r 0 , 0 < r 0 < r − 1 r − 1 = q 1 ⋅ r 0 + r 1 , 0 < r 1 < r 0 r 0 = q 2 ⋅ r 1 + r 2 , 0 < r 2 < r 1 . . . r n − 3 = q n − 1 ⋅ r n − 2 + r n − 1 , 0 < r n − 1 < r n − 2 r n − 2 = q n ⋅ r n − 1 + r n , 0 < r n < r n − 1 r n − 1 = q n + 1 ⋅ r n + r n + 1 , r n + 1 = 0 r_{-2} = q_0·r_{-1}+r_0, \qquad 0<r_0<r_{-1}\\ r_{-1} = q_1·r_{0}+r_1, \qquad 0<r_1<r_{0}\\ r_0 = q_2·r_1+r_2, \qquad 0<r_2<r_1\\ ...\\ r_{n-3} = q_{n-1}·r_{n-2}+r_{n-1}, \qquad 0<r_{n-1}<r_{n-2}\\ r_{n-2} = q_{n}·r_{n-1}+r_{n}, \qquad 0<r_{n}<r_{n-1}\\ r_{n-1} = q_{n+1}·r_{n}+r_{n+1}, r_{n+1}=0\\ r−2​=q0​⋅r−1​+r0​,0<r0​<r−1​r−1​=q1​⋅r0​+r1​,0<r1​<r0​r0​=q2​⋅r1​+r2​,0<r2​<r1​...rn−3​=qn−1​⋅rn−2​+rn−1​,0<rn−1​<rn−2​rn−2​=qn​⋅rn−1​+rn​,0<rn​<rn−1​rn−1​=qn+1​⋅rn​+rn+1​,rn+1​=0

* r n r_n rn​即为a,b的最大公因数

*经过有限步骤,必然存在n使得 r n + 1 = 0 r_{n+1}=0 rn+1​=0 ,因为 r i r_i ri​是初始为有限整数b,且随着i的增加, r i r_i ri​单调递减

贝祖等式

  • s ⋅ a + t ⋅ b = G C D ( a , b ) s·a+t·b=GCD(a,b) s⋅a+t⋅b=GCD(a,b)即为贝祖等式

  • 贝祖等式的数学证明较复杂,不要求掌握

  • 贝祖等式中的s和t可以通过将辗转相除每步的 q i q_i qi​和 r i r_i ri​递归地代入下步直到 r n + 1 r_{n+1} rn+1​

  • 若用递归表达式表达贝祖等式,则需要将其改写为

s n ⋅ a + t n ⋅ b = ( a , b ) s_n·a+t_n·b = (a,b) sn​⋅a+tn​⋅b=(a,b)

对 j = 0 , 1 , . . . , n − 1 , n j = 0, 1, ..., n-1, n j=0,1,...,n−1,n,这里 s j s_j sj​, t j t_j tj​归纳的定义为
{ s − 2 = 1 , s − 1 = 0 t − 2 = 1 , t − 1 = 0 s j = ( − q j ) ⋅ s j − 1 + s j − 2 t j = ( − q j ) ⋅ t j − 1 + t j − 2 \begin{cases} s_{-2}=1,s_{-1}=0 \\ t_{-2}=1,t_{-1}= 0 \\ s_{j}=(-q_{j})·s_{j-1}+s_{j-2} \\ t_{j}=(-q_{j})·t_{j-1}+t_{j-2} \end{cases} ⎩⎪⎪⎪⎨⎪⎪⎪⎧​s−2​=1,s−1​=0t−2​=1,t−1​=0sj​=(−qj​)⋅sj−1​+sj−2​tj​=(−qj​)⋅tj−1​+tj−2​​
其中 q j = [ r j − 2 r j − 1 ] q_j=[\cfrac{r_{j-2}}{r_{j-1}}] qj​=[rj−1​rj−2​​],为广义欧几里得除法中的不完全商,满足 r k = q k + 2 ⋅ r k + 1 + r k + 2 r_k = q_{k+2}·r_{k+1}+r_{k+2} rk​=qk+2​⋅rk+1​+rk+2​

1.3.5最大公因数的进一步性质

定理1.3.9:设a,b是任意两个不全为零的整数,d是正整数,则d是整数a,b的最大公因数的充要条件是

  • d ∣ a d\vert a d∣a, d ∣ b d\vert b d∣b

  • 对整数e,若 e ∣ a e\vert a e∣a, e ∣ b e\vert b e∣b,则 e ∣ d e\vert d e∣d

定理1.3.10:设a,b是任意两个不全为零的整数

​ (i)若m是任一正整数,则 ( m ⋅ a , m ⋅ b ) = m ⋅ ( a , b ) (m·a,m·b)=m·(a,b) (m⋅a,m⋅b)=m⋅(a,b)

​ (ii)若非零整数d满足 d ∣ a d\vert a d∣a, d ∣ b d\vert b d∣b,则 ( a d , b d ) = ( a , b ) ∣ d ∣ (\cfrac{a}{d},\cfrac{b}{d})=\cfrac{(a,b)}{\vert d\vert } (da​,db​)=∣d∣(a,b)​。特别地
( a ( a , b ) , b ( a , b ) ) = 1 (\cfrac{a}{(a,b)},\cfrac{b}{(a,b)})=1 ((a,b)a​,(a,b)b​)=1
定理1.3.11:设a,b,c是三个整数,且b≠0,c≠0。如果 ( a , c ) = 1 (a,c)=1 (a,c)=1,则
( a , b , c ) = ( b , c ) (a,b,c) = (b,c) (a,b,c)=(b,c)
证:设 d = ( a , b , c ) d=(a,b,c) d=(a,b,c), d ′ = ( b , c ) d'=(b,c) d′=(b,c),有 d ′ ∣ b d'\vert b d′∣b, d ′ ∣ c d'\vert c d′∣c,进而 d ′ ∣ a ⋅ b d'\vert a·b d′∣a⋅b, d ’ ∣ c d’\vert c d’∣c​。再根据定理1.3.9,得到 d = d ′ d=d' d=d′

​ 反过来,因为 ( a , c ) = 1 (a,c)=1 (a,c)=1,依据广义欧几里得除法,存在整数s,t使得 s ⋅ a + t ⋅ c = 1 s·a+t·c=1 s⋅a+t⋅c=1

​ 两端同时乘b,得到 s ⋅ ( a b ) + ( t b ) ⋅ c = b s·(ab)+(tb)·c=b s⋅(ab)+(tb)⋅c=b

​ 又由 d ∣ a d\vert a d∣a, d ∣ c d\vert c d∣c,可得到 d ∣ [ s ⋅ ( a b ) + ( t b ) ⋅ c ] d\vert [s·(ab)+(tb)·c] d∣[s⋅(ab)+(tb)⋅c],即 d ∣ b d\vert b d∣b,同样可依据定理1.3.9,得到 d ∣ d ′ d\vert d' d∣d′

​ 所以 d = d ′ d=d' d=d′,定理成立

定理1.3.12:设 a 1 , . . . , a n a_1,...,a_n a1​,...,an​,c为整数,如果 ( a i , c ) = 1 (a_i,c)=1 (ai​,c)=1, 1 ≤ i ≤ n 1≤i≤n 1≤i≤n则
( a 1 , . . . a n , c ) = 1 (a_1,...a_n,c)=1 (a1​,...an​,c)=1
定理1.1.13:设a,b和u,v都是不全为0的整数,如果满足
a = q ⋅ u + r ⋅ v , b = s ⋅ u + t ⋅ v a=q·u+r·v, b = s·u+t·v a=q⋅u+r⋅v,b=s⋅u+t⋅v
其中,q,r,t,s都是整数,且 q ⋅ t − r ⋅ s = 1 q·t-r·s =1 q⋅t−r⋅s=1,则 ( a , b ) = ( u , v ) (a,b)=(u,v) (a,b)=(u,v)

证:设 d = ( a , b ) d=(a,b) d=(a,b), d ′ = ( u , v ) d'=(u,v) d′=(u,v),则可得到
d ′ ∣ ( q ⋅ u + r ⋅ v ) = a d ′ ( s ⋅ u + t ⋅ v ) = b d'|(q·u+r·v)=a\\d'(s·u+t·v)=b d′∣(q⋅u+r⋅v)=ad′(s⋅u+t⋅v)=b
因而 d ′ ∣ d d'\vert d d′∣d

又由假设可以得到 u = t ⋅ a + ( − s ) ⋅ b , v = ( − r ) ⋅ a + q ⋅ b u=t·a+(-s)·b,v=(-r)·a+q·b u=t⋅a+(−s)⋅b,v=(−r)⋅a+q⋅b,同理可得 d ∣ d ′ d\vert d' d∣d′

因此d=d’,定理成立

多个整数的最大公因数

定理1.3.14:设 a 1 , a 2 , . . . , a n a_1,a_2,...,a_n a1​,a2​,...,an​是n个整数,且 a 1 ≠ 0 a_1≠0 a1​​=0。令
( a 1 , a 2 ) = d 2 , ( d 2 , a 3 ) = d 3 , . . . , ( d n − 1 , a n ) = d n (a_1,a_2)=d_2, (d_2,a_3)=d_3,...,(d_{n-1},a_n)=d_n (a1​,a2​)=d2​,(d2​,a3​)=d3​,...,(dn−1​,an​)=dn​
则 ( a 1 , a 2 , . . . , a n ) = d n (a_1,a_2,...,a_n)=d_n (a1​,a2​,...,an​)=dn​且存在整数 s 1 , s 2 , . . . , s n s_1,s_2,...,s_n s1​,s2​,...,sn​使得
s 1 ⋅ a 1 + s 2 ⋅ a 2 + . . . + s n ⋅ a n = d n s_1·a_1+s_2·a_2+...+s_n·a_n = d_n s1​⋅a1​+s2​⋅a2​+...+sn​⋅an​=dn​

1.3.7形为 2 a − 1 2^a-1 2a−1的整数及其最大公因数

引理1.3.1:设a,b是两个正整数,则 2 a − 1 2^a-1 2a−1被 2 b − 1 2^b-1 2b−1除的最小非负余数为 2 r − 1 2^r-1 2r−1。其中,r为a被b除的最小余数

引理1.3.2:设a,b为为两个正整数,则 2 a − 1 2^a-1 2a−1和 2 b − 1 2^b-1 2b−1的最大公因数为 2 ( a , b ) − 1 2^{(a,b)}-1 2(a,b)−1

​ 证明不难,可以自己尝试

定理1.3.16:设a,b为两个正整数,则 2 a − 1 2^a-1 2a−1和 2 b − 1 2^b-1 2b−1互素的充要条件为 ( a , b ) = 1 (a,b)=1 (a,b)=1,即a,b互素

1.4整除的进一步性质以及最小公倍数

1.4.1整除的进一步性质

定理1.4.2若p是质数,且 p ∣ a ⋅ b p\vert a·b p∣a⋅b,则 p ∣ a p\vert a p∣a或 p ∣ b p\vert b p∣b

​ p是质数的前置条件很重要

定理1.4.3:若p是质数, a 1 , . . . , a n a_1, ..., a_n a1​,...,an​为n个整数,若 p ∣ a 1 ⋅ . . . ⋅ a n p\vert a_1·...·a_n p∣a1​⋅...⋅an​,则p一定整除某一个整数 a k , k ∈ [ 1 , n ] a_k, k\in [1,n] ak​,k∈[1,n]

1.4.3最小公倍数与最大公因数

定义1.4.1:设 a 1 , . . . , a n a_1, ..., a_n a1​,...,an​是n个整数,若D是这n个整数的倍数,则称D为 a 1 , . . . , a n a_1, ..., a_n a1​,...,an​的公倍数。

​ a 1 , . . . , a n a_1, ..., a_n a1​,...,an​所有公倍数中最小的正整数叫做它们的最小公倍数,记作 [ a 1 , . . . , a n ] [a_1, ..., a_n] [a1​,...,an​]

定理1.4.5:设 a , b a,b a,b是两个正整数,则

  • 若 a ∣ D a\vert D a∣D, b ∣ D b\vert D b∣D,则 [ a , b ] ∣ D [a,b]\vert D [a,b]∣D
  • [ a , b ] = a ⋅ b ( a , b ) [a,b]=\cfrac{a·b}{(a,b)} [a,b]=(a,b)a⋅b​

多个整数的最小公倍数:定理1.4.6:设 a 1 , . . . , a n a_1, ..., a_n a1​,...,an​是n个整数,设
[ a 1 , a 2 ] = D 2 , [ D 2 , a 3 ] = D 3 , . . , [ D n − 1 , a n ] = D n [a_1,a_2] = D_2, [D_2,a_3]=D_3,..,[D_{n-1},a_n]=D_n [a1​,a2​]=D2​,[D2​,a3​]=D3​,..,[Dn−1​,an​]=Dn​
则 [ a 1 , . . . , a n ] = D n [a_1, ..., a_n]=D_n [a1​,...,an​]=Dn​

1.5整数分解与算术基本定理

定理1.5.1(整数分解定理):对于给定正整数 n > 1 n>1 n>1,若存在整数a,b使得
n ∣ ( a 2 − b 2 ) , n ∤ ( a − b ) , n ∤ ( a + b ) n|(a^2-b^2), n\nmid (a-b), n\nmid (a+b) n∣(a2−b2),n∤(a−b),n∤(a+b)
则 ( n , a − b ) , ( n , a + b ) (n,a-b),(n,a+b) (n,a−b),(n,a+b)都是n的真因数

证:

  • 若 ( n , a − b ) (n,a-b) (n,a−b)不是n的真因数,则 ( n , a − b ) (n,a-b) (n,a−b)为1或n
    • 对 ( n , a − b ) = 1 (n,a-b)=1 (n,a−b)=1,由 n ∣ ( a + b ) ⋅ ( a − b ) n\vert (a+b)·(a-b) n∣(a+b)⋅(a−b),推出 n ∣ ( a + b ) n\vert (a+b) n∣(a+b),与假设矛盾
    • 对 ( n , a − b ) = n (n,a-b)=n (n,a−b)=n,推出 n ∣ ( a − b ) n\vert (a-b) n∣(a−b),与假设矛盾

​ 得证

定理1.6.1:任一整数n>1都可以表示成素数的乘积。在不考虑相乘顺序的情况下,该表达式是唯一的。

​ 当表达式的所有数都以幂次的形式给出,即写成
n = p 1 α 1 ⋅ p 2 α 2 ⋅ . . . ⋅ p s α s α i > 0 , i = 1 , . . . , s n = p_1^{\alpha _1}·p_2^{\alpha _2}·...·p_s^{\alpha _s}\\\alpha^i>0,i=1,...,s n=p1α1​​⋅p2α2​​⋅...⋅psαs​​αi>0,i=1,...,s
​ 的形式,此时该式被称为n的标准分解式

定理1.6.6:设a,b是两个正整数,则存在整数 a ′ ∣ a , b ′ ∣ b a'\vert a,b'\vert b a′∣a,b′∣b使得
a ′ ⋅ b ′ = [ a , b ] , ( a ′ , b ′ ) = 1 a'·b' = [a,b], (a',b')=1 a′⋅b′=[a,b],(a′,b′)=1

参考资料

信息安全数学基础(第二版)陈恭亮

裴蜀定理

上一篇:第二次作业


下一篇:CRM客户管理系统哪个好用