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
参考资料
信息安全数学基础（第二版）陈恭亮