算术基本定理

整除性理论部分的中心问题

概念

（算术基本定理）在不计因数次序的意义下，任一大于$1$的正整数$n$都可以唯一分解成质因数的连乘积。

$证：(1)存在性：第二数学归纳法。当n=2时，2是质数，命题成立；假设对某个l>2,当2\le n<l时，命题成立，则当n=l时，若l是质数，则命题成立；若l是合数，则必有l=l_1{l}_2(2\le l_1,l_2<l),则由归纳假设知，l_1,l_2均可表示为质数的连乘积：l_1=p_1^{\prime }{p}_2^{\prime }\cdots p_k^{\prime },l_2=p_{k+1}^{\prime }\cdots p_n^{\prime },这里p_i^{\prime }(i=1,\cdots ,n)为质数，则n=l=l_1{l}_2=(p_1^{\prime }{p}_2^{\prime }\cdots p_k^{\prime })(p_{k+1}^{\prime }\cdots p_n^{\prime }),适当调整顺序后，有n=p_1{p}_2\cdots p_n(p_1\le p_2\le \cdots \le p_n),其中p_i(i=1,2,\cdots ,n)为质数。则由第二数学归纳法知，命题对所有n>1的正整数都成立。(2)唯一性：假设n有两种质因数分解式：n=p_1{p}_2\cdots p_n=q_1{q}_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_1{p}_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$

（$n$的标准分解式）根据算术基本定理，若把相同的质因数合并，则任一大于$1$的正整数$n$，唯一地分解成以下形式：$\begin{array}{r}n=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\cdots p_k^{{\alpha }_k}\end{array},其中p_1,p_2,\cdots ,p_k是质数，且p_1<p_2<\cdots <p_k,{\alpha }_1,{\alpha }_2,\cdots ,{\alpha }_k均为正整数$。

推论： 若正整数$n$的标准分解式为$n=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\cdots p_k^{{\alpha }_k}$，则$d$是$n$的正因数的充要条件为$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)$

若正整数$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,n)=p1r1p2r2⋯pkrk,[m,n]=p1s1p2s2⋯pksk,这里ri=min⁡{ai,bi},si=max⁡{ai,bi}。\,(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)=p1r1​​p2r2​​⋯pkrk​​,[m,n]=p1s1​​p2s2​​⋯pksk​​,这里ri​=min{ai​,bi​},si​=max{ai​,bi​}。

上一定理的推广：若正整数$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,⋯,en)=p1a1⋯pkak,[e1,⋯,en]=p1b1⋯pkbk,这里ai=min⁡{a1i,⋯,ani},bi=max⁡{a1i,⋯,ani}\,(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$，不等式$\lg (n)\ge k\lg (2)$成立，这里$k$是$n$的不同质因数的个数。
  $证：设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}\cdots 2^{t_k}=2^{t_1+t_2+\cdots +t_k}\ge 2^k,则lg(n)\ge k\lg (2)$
• 一个整数如果不能被任何质数的平方整除，则称为无平方因子整数，否则称为有平方因子整数。试证：对任意整数$n$，有唯一一对正整数$k,l$，使得$n=k^{2}l$，这里$l$是无平方因子整数 (即$l$是$1$或相异质数的乘积)
  $证：(1)存在性：当n=1时，存在唯一一对正整数k=1,l=1,使得n=k^{2}l。当n>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^{2}l,这里l是无平方因子整数；(2)设n=a^{2}b,这里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。$

End