文章目录
算术基本定理
整除性理论部分的中心问题
概念
（算术基本定理）在不计因数次序的意义下，任一大于 1 \,1\, 1的正整数 n \,n\, n都可以唯一分解成质因数的连乘积。
证 ： ( 1 ) 存 在 性 ： 第 二 数 学 归 纳 法 。 当 n = 2 时 ， 2 是 质 数 ， 命 题 成 立 ； 假 设 对 某 个 l > 2 , 当 2 ≤ n < l 时 ， 命 题 成 立 ， 则 当 n = l 时 ， 若 l 是 质 数 ， 则 命 题 成 立 ； 若 l 是 合 数 ， 则 必 有 l = l 1 l 2 ( 2 ≤ l 1 , l 2 < l ) , 则 由 归 纳 假 设 知 ， l 1 , l 2 均 可 表 示 为 质 数 的 连 乘 积 ： l 1 = p 1 ′ p 2 ′ ⋯ p k ′ , l 2 = p k + 1 ′ ⋯ p n ′ , 这 里 p i ′ ( i = 1 , ⋯ , n ) 为 质 数 ， 则 n = l = l 1 l 2 = ( p 1 ′ p 2 ′ ⋯ p k ′ ) ( p k + 1 ′ ⋯ p n ′ ) , 适 当 调 整 顺 序 后 ， 有 n = p 1 p 2 ⋯ p n ( p 1 ≤ p 2 ≤ ⋯ ≤ p n ) , 其 中 p i ( i = 1 , 2 , ⋯ , n ) 为 质 数 。 则 由 第 二 数 学 归 纳 法 知 ， 命 题 对 所 有 n > 1 的 正 整 数 都 成 立 。 ( 2 ) 唯 一 性 ： 假 设 n 有 两 种 质 因 数 分 解 式 ： n = p 1 p 2 ⋯ p n = q 1 q 2 ⋯ q m , 其 中 p i ( i = 1 , 2 , ⋯ , n ) , q j ( j = 1 , 2 , ⋯ , m ) 都 是 质 数 ， 且 p 1 ≤ p 2 ≤ ⋯ ≤ p n , q 1 ≤ q 2 ≤ ⋯ ≤ q m , 则 有 q 1 ∣ p 1 p 2 ⋯ p n , 于 是 存 在 p i ( i = 1 , 2 , ⋯ , n ) , 使 得 q 1 ∣ p i , 由 于 q 1 与 p 1 均 为 质 数 ， 则 有 q 1 = p i ≥ p 1 , 同 理 有 p 1 ≥ q 1 , 故 p 1 = q 1 , 此 时 p 2 ⋯ p n = q 2 ⋯ q m , 用 上 述 的 论 证 方 法 ， 可 得 p 2 = q 2 , p 3 = q 3 , ⋯ , 且 n = m , p n = q m 证：(1)\,存在性：第二数学归纳法。当\,n=2\,时，2\,是质数，命题成立；假设对某个\,l\, \gt 2\,,当\,2 \le n \lt l\,时，命题成立，则当\,n=l\,时，若\,l\,是质数，则命题成立；若\,l\,是合数，则必有\,l=l_1l_2\,(2 \le l_1,l_2 \lt l)\,,则由归纳假设知，\,l_1,l_2\,均可表示为质数的连乘积：l_1=p_1'p_2'\cdots p_k'\,,\,l_2=p_{k+1}'\cdots p_n'\,,这里\,p_i'\,(i=1,\cdots,n)\,为质数，则\,n=l=l_1l_2=(p_1'p_2'\cdots p_{k}')(p_{k+1}'\cdots p_n')\,,适当调整顺序后，有\,n=p_1p_2\cdots p_n\,(p_1 \le p_2 \le \cdots \le p_n)\,,其中\,p_i(i=1,2,\cdots,n)为质数。则由第二数学归纳法知，命题对所有\,n \gt 1\,的正整数都成立。(2)\,唯一性：假设\,n\,有两种质因数分解式：n=p_1p_2\cdots p_n=q_1q_2 \cdots q_m\,,其中\,p_i(i=1,2,\cdots,n)\,,\,q_j(j=1,2,\cdots,m)\,都是质数，且\,p_1 \le p_2 \le \cdots \le p_n\,,\,q_1 \le q_2 \le \cdots \le q_m\,,则有\,q_1 \mid p_1p_2 \cdots p_n\,,于是存在\,p_i\,(i=1,2,\cdots,n)\,,使得\,q_1 \mid p_i\,,由于\,q_1\,与\,p_1\,均为质数，则有\,q_1=p_i \ge p_1\,,同理有\,p_1 \ge q_1\,,故\,p_1=q_1\,,此时\,p_2\cdots p_n=q_2 \cdots q_m\,,用上述的论证方法，可得\,p_2=q_2\,,\,p_3=q_3\,,\,\cdots\,,且\,n=m\,,\,p_n=q_m\, 证：(1)存在性：第二数学归纳法。当n=2时，2是质数，命题成立；假设对某个l>2,当2≤n<l时，命题成立，则当n=l时，若l是质数，则命题成立；若l是合数，则必有l=l1l2(2≤l1,l2<l),则由归纳假设知，l1,l2均可表示为质数的连乘积：l1=p1′p2′⋯pk′,l2=pk+1′⋯pn′,这里pi′(i=1,⋯,n)为质数，则n=l=l1l2=(p1′p2′⋯pk′)(pk+1′⋯pn′),适当调整顺序后，有n=p1p2⋯pn(p1≤p2≤⋯≤pn),其中pi(i=1,2,⋯,n)为质数。则由第二数学归纳法知，命题对所有n>1的正整数都成立。(2)唯一性：假设n有两种质因数分解式：n=p1p2⋯pn=q1q2⋯qm,其中pi(i=1,2,⋯,n),qj(j=1,2,⋯,m)都是质数，且p1≤p2≤⋯≤pn,q1≤q2≤⋯≤qm,则有q1∣p1p2⋯pn,于是存在pi(i=1,2,⋯,n),使得q1∣pi,由于q1与p1均为质数，则有q1=pi≥p1,同理有p1≥q1,故p1=q1,此时p2⋯pn=q2⋯qm,用上述的论证方法，可得p2=q2,p3=q3,⋯,且n=m,pn=qm
（ n \,n\, n的标准分解式）根据算术基本定理，若把相同的质因数合并，则任一大于 1 \,1\, 1的正整数 n \,n\, n，唯一地分解成以下形式： n = p 1 α 1 p 2 α 2 ⋯ p k α k , 其 中 p 1 , p 2 , ⋯ , p k 是 质 数 ， 且 p 1 < p 2 < ⋯ < p k , α 1 , α 2 , ⋯ , α k 均 为 正 整 数 \begin{aligned}\,n=p_1^{\alpha_1}p_2^{\alpha_2} \cdots p_k^{\alpha_k}\,\end{aligned},其中\,p_1,p_2,\cdots,p_k\,是质数，且\,p_1 \lt p_2 \lt \cdots \lt p_k\,,\,\alpha_1,\alpha_2,\cdots,\alpha_k\,均为正整数 n=p1α1p2α2⋯pkαk,其中p1,p2,⋯,pk是质数，且p1<p2<⋯<pk,α1,α2,⋯,αk均为正整数。
推论： 若正整数 n \,n\, n的标准分解式为 n = p 1 α 1 p 2 α 2 ⋯ p k α k \,n=p_1^{\alpha_1}p_2^{\alpha_2} \cdots p_k^{\alpha_k}\, n=p1α1p2α2⋯pkαk，则 d \,d\, d是 n \,n\, n的正因数的充要条件为 d = p 1 b 1 p 2 b 2 ⋯ p k b k ( 0 ≤ b i ≤ α i , i = 1 , 2 , ⋯ , k ) \,d = p_1^{b_1}p_2^{b_2} \cdots p_k^{b_k}\,\,(0 \le b_i \le \alpha_i\,,\,i=1,2,\cdots,k) d=p1b1p2b2⋯pkbk(0≤bi≤αi,i=1,2,⋯,k)
若正整数 m = p 1 a 1 p 2 a 2 ⋯ p k a k , n = p 1 b 1 p 2 b 2 ⋯ p k b k ( a i ≥ 0 , b i ≥ 0 , i = 1 , 2 , ⋯ , k ) \,m=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}\,,\,n=p_1^{b_1}p_2^{b_2}\cdots p_k^{b_k}\,(a_i \ge 0\,,\,b_i \ge 0\,,\,i=1,2,\cdots,k)\, m=p1a1p2a2⋯pkak,n=p1b1p2b2⋯pkbk(ai≥0,bi≥0,i=1,2,⋯,k)则 ( m , n ) = p 1 r 1 p 2 r 2 ⋯ p k r k , [ m , n ] = p 1 s 1 p 2 s 2 ⋯ p k s k , 这 里 r i = min { a i , b i } , s i = max { a i , b i } 。 \,(m,n)=p_1^{r_1}p_2^{r_2}\cdots p_k^{r_k}\,,\,[\,m,n\,]=p_1^{s_1}p_2^{s_2}\cdots p_k^{s_k}\,,这里\,r_i=\min\{a_i,b_i\}\,,\,s_i=\max\{a_i,b_i\}\,。 (m,n)=p1r1p2r2⋯pkrk,[m,n]=p1s1p2s2⋯pksk,这里ri=min{ai,bi},si=max{ai,bi}。
上一定理的推广：若正整数 e 1 = p 1 a 11 ⋯ p k a 1 k , ⋯ , e n = p 1 a n 1 ⋯ p k a n k ( a i j ≥ 0 ; i = 1 , 2 , ⋯ , n ; j = 1 , 2 , ⋯ , k ) \,e_1=p_1^{a_{11}}\cdots p_k^{a_{1k}}\,,\,\cdots\,,\,e_n=p_1^{a_{n1}}\cdots p_k^{a_{nk}}\,\,(a_{ij} \ge 0\,;\,i=1,2,\cdots,n\,;\,j=1,2,\cdots,k)\, e1=p1a11⋯pka1k,⋯,en=p1an1⋯pkank(aij≥0;i=1,2,⋯,n;j=1,2,⋯,k)则 ( e 1 , ⋯ , e n ) = p 1 a 1 ⋯ p k a k , [ e 1 , ⋯ , e n ] = p 1 b 1 ⋯ p k b k , 这 里 a i = min { a 1 i , ⋯ , a n i } , b i = max { a 1 i , ⋯ , a n i } \,(e_1,\cdots,e_n)=p_1^{a_1}\cdots p_k^{a_k}\,,\,[\,e_1,\cdots,e_n\,]=p_1^{b_1}\cdots p_k^{b_k}\,,这里\,a_i=\min\{a_{1i}\,,\cdots,a_{ni}\}\,,\,b_i=\max\{a_{1i}\,,\cdots,a_{ni}\}\, (e1,⋯,en)=p1a1⋯pkak,[e1,⋯,en]=p1b1⋯pkbk,这里ai=min{a1i,⋯,ani},bi=max{a1i,⋯,ani}
例题
-
试证：对任意正整数
n
\,n\,
n，不等式
lg
(
n
)
≥
k
lg
(
2
)
\,\lg(n) \ge k\lg(2)\,
lg(n)≥klg(2)成立，这里
k
\,k\,
k是
n
\,n\,
n的不同质因数的个数。
证 ： 设 n 是 大 于 1 的 正 整 数 ( 当 n = 1 时 ， 上 述 不 等 式 显 然 成 立 ， 因 为 此 时 k = 0 , p 1 , p 2 , ⋯ , p k 是 n 的 k 个 相 异 的 质 因 数 ， n 的 标 准 分 解 式 是 n = p 1 t 1 p 2 t 2 ⋯ p k t k ( t i ≥ 1 , i = 1 , 2 , ⋯ , k ) , 由 于 p i ≥ 2 ( i = 1 , 2 , ⋯ , k ) , 即 n ≥ 2 t 1 2 t 2 ⋯ 2 t k = 2 t 1 + t 2 + ⋯ + t k ≥ 2 k , 则 l g ( n ) ≥ k lg ( 2 ) 证：设\,n\,是大于\,1\,的正整数(当\,n=1\,时，上述不等式显然成立，因为此时\,k=0\,,\,p_1,p_2,\cdots,p_k\,是\,n\,的\,k\,个相异的质因数，\,n\,的标准分解式是\,n=p_1^{t_1}p_2^{t_2}\cdots p_k^{t_k}\,\,(t_i \ge 1\,,\,i=1,2,\cdots,k)\,,由于\,p_i \ge 2\,(i=1,2,\cdots,k)\,,即\,n \ge 2^{t_1}2^{t_2}\cdots2^{t_k}=2^{t_1+t_2+\cdots+t_k} \ge 2^k\,,则\,lg(n) \ge k\lg(2) 证：设n是大于1的正整数(当n=1时，上述不等式显然成立，因为此时k=0,p1,p2,⋯,pk是n的k个相异的质因数，n的标准分解式是n=p1t1p2t2⋯pktk(ti≥1,i=1,2,⋯,k),由于pi≥2(i=1,2,⋯,k),即n≥2t12t2⋯2tk=2t1+t2+⋯+tk≥2k,则lg(n)≥klg(2) - 一个整数如果不能被任何质数的平方整除，则称为无平方因子整数，否则称为有平方因子整数。试证：对任意整数
n
\,n\,
n，有唯一一对正整数
k
,
l
\,k,l\,
k,l，使得
n
=
k
2
l
\,n=k^2l\,
n=k2l，这里
l
\,l\,
l是无平方因子整数 (即
l
\,l\,
l是
1
\,1\,
1或相异质数的乘积)
证 ： ( 1 ) 存 在 性 ： 当 n = 1 时 ， 存 在 唯 一 一 对 正 整 数 k = 1 , l = 1 , 使 得 n = k 2 l 。 当 n > 1 时 ， 设 n 的 标 准 分 解 式 为 n = p 1 l 1 p 2 l 2 ⋯ p s l s , 这 里 p 1 , p 2 , ⋯ , p s 是 相 异 的 质 数 。 若 l i 被 2 除 的 商 是 q i , 余 数 是 r i , 则 l i = 2 q i + r i ( i = 1 , 2 , ⋯ , s ) , 则 r i = 0 或 1 , 于 是 n = ( p 1 q 1 p 2 q 2 ⋯ p s q s ) 2 ⋅ p 1 r 1 p 2 r 2 ⋯ p s r s , 若 令 k = p 1 q 1 p 2 q 2 ⋯ p s q s , l = p 1 r 1 p 2 r 2 ⋯ p s r s , 则 n = k 2 l , 这 里 l 是 无 平 方 因 子 整 数 ； ( 2 ) 设 n = a 2 b , 这 里 b 是 无 平 方 因 子 整 数 ， 因 a ∣ n , b ∣ n , 故 由 算 术 基 本 定 理 的 推 论 知 ， a , b 一 定 具 有 下 列 形 式 ： a = p 1 e 1 p 2 e 2 ⋯ p s e s , b = p 1 t 1 p 2 t 2 ⋯ p s t s , 于 是 p 1 l 1 p 2 l 2 ⋯ p s l s = p 1 2 e 1 + t 1 p 2 2 e 2 + t 2 ⋯ p s 2 e s + t s ( i = 1 , 2 , ⋯ , s ) , 由 于 b 是 无 平 方 因 子 整 数 ， 故 t i = 0 或 1 。 于 是 e i 与 t i 分 别 是 2 除 l i 的 商 和 余 数 ， 所 以 e i = q i , t i = r i , 即 a = k , b = l 。 证：(1)\,存在性：当\,n=1\,时，存在唯一一对正整数\,k=1,l=1\,,使得\,n=k^2l\,。当\,n \gt 1\,时，设\,n\,的标准分解式为\,n=p_1^{l_1}p_2^{l_2}\cdots p_s^{l_s}\,,这里\,p_1,p_2,\cdots,p_s\,是相异的质数。若\,l_i\,被\,2\,除的商是\,q_i\,,\,余数是\,r_i\,,则\,l_i=2q_i+r_i\,(i=1,2,\cdots,s)\,,则\,r_i=0\,或\,1\,,于是\,n=(p_1^{q_1}p_2^{q_2}\cdots p_s^{q_s})^2 \cdot p_1^{r_1}p_2^{r_2}\cdots p_s^{r_s}\,,若令\,k=p_1^{q_1}p_2^{q_2}\cdots p_s^{q_s}\,,\,l=p_1^{r_1}p_2^{r_2}\cdots p_s^{r_s}\,,则\,n=k^2l\,,这里\,l\,是无平方因子整数；(2)\,设\,n=a^2b\,,这里\,b\,是无平方因子整数，因\,a \mid n\,,\,b \mid n\,,故由算术基本定理的推论知，a,b一定具有下列形式：a=p_1^{e_1}p_2^{e_2}\cdots p_s^{e_s}\,,\,b=p_1^{t_1}p_2^{t_2}\cdots p_s^{t_s}\,,于是\,p_1^{l_1}p_2^{l_2}\cdots p_s^{l_s}=p_1^{2e_1+t_1}p_2^{2e_2+t_2}\cdots p_s^{2e_s+t_s}\,(i=1,2,\cdots,s)\,,由于\,b\,是无平方因子整数，故\,t_i=0\,或\,1\,。于是\,e_i\,与\,t_i\,分别是\,2\,除\,l_i\,的商和余数，所以\,e_i=q_i\,,\,t_i=r_i\,,即\,a=k\,,\,b=l\,。 证：(1)存在性：当n=1时，存在唯一一对正整数k=1,l=1,使得n=k2l。当n>1时，设n的标准分解式为n=p1l1p2l2⋯psls,这里p1,p2,⋯,ps是相异的质数。若li被2除的商是qi,余数是ri,则li=2qi+ri(i=1,2,⋯,s),则ri=0或1,于是n=(p1q1p2q2⋯psqs)2⋅p1r1p2r2⋯psrs,若令k=p1q1p2q2⋯psqs,l=p1r1p2r2⋯psrs,则n=k2l,这里l是无平方因子整数；(2)设n=a2b,这里b是无平方因子整数，因a∣n,b∣n,故由算术基本定理的推论知，a,b一定具有下列形式：a=p1e1p2e2⋯pses,b=p1t1p2t2⋯psts,于是p1l1p2l2⋯psls=p12e1+t1p22e2+t2⋯ps2es+ts(i=1,2,⋯,s),由于b是无平方因子整数，故ti=0或1。于是ei与ti分别是2除li的商和余数，所以ei=qi,ti=ri,即a=k,b=l。