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−1bk−1+ak−2bk−2+...+a1b+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=[logbn](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−1ak−2...a1a0)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−1r−1=q1⋅r0+r1,0<r1<r0r0=q2⋅r1+r2,0<r2<r1...rn−3=qn−1⋅rn−2+rn−1,0<rn−1<rn−2rn−2=qn⋅rn−1+rn,0<rn<rn−1rn−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−2tj=(−qj)⋅tj−1+tj−2
其中
q
j
=
[
r
j
−
2
r
j
−
1
]
q_j=[\cfrac{r_{j-2}}{r_{j-1}}]
qj=[rj−1rj−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
参考资料
信息安全数学基础(第二版)陈恭亮