算数基本定理@质因数分解原理

abstract

把自然数写成素数的乘积，结论就是著名的算术基本定理。

此定理建立了自然数与素数之间的一个重要的关系式。

算数基本定理是整除理论性质和结论的精华,是整个初等数论的基础

• 证明一些方程是否有整数解
• 能够从公式的角度解决许多直接计算但计算量大的问题,比如求一个数的正约数数量

素数相关的整除性质和结论

1. 设$p$是一个素数，$a$是任一整数，则有:$(p,a)=1$(即$p\nmid a$),或$(p,a)=p$(即$p|a$).
   • 证明：由素数的定义和整除的定义,上述结论是显然的
     • 由最大公约数的定义有$(p,a)|p$,而对于素数$p$,它只有2个约数$1,p$,从而:$1|p$,$p|p$
     • 可知$(p,a)=1$或$(p,a)=p$，由后者即得$p|a$.
     • 此定理直白地说就是,一个素数$p$的约数只有$1,p$,因此任意其他数$a$和$p$的公约数只有$1,p$两种可能;$(p,a)=1$或$(p,a)=p$,后者和$p|a$等价
2. 设$p$为素数，$p|ab$,且$p\nmid a$,则$p|b$.
   • 定理也表明,如果$p|ab$,则$a,b$至少有一个能被$p$整除
   • 证明：由$p\nmid a$及结论1，知$(p,a)=1$.故由公约数的性质(若$p|ab,(p,a)=1$则$p|b$),即知$p|b$.
3. 设$p|(a_1{a}_2\cdots a_s)$,则$p$至少能整除一个$a_i,1⩽i⩽s$.
   • 该结论也表明,如果$p\nmid a_i$,$1⩽i⩽s$,则$p\nmid (a_1{a}_2\cdots a_s)$
   • 证明：可以用反证法,利用结论2
     • 如$p\nmid a_1$，则由结论2知$p|(a_2\cdots a_s)$.
     • 如$p\nmid a_2$，同理可得$p|(a_3\cdots a_s)$.
     • …依次类推
     • 最终可得$p|a_{s} $.

定理1（算术基本定理）

设$n>1$，则$n$可分解成素数的乘积 $n=p_1{p}_2\cdots p_m,$

如果不计(较)这些素数的次序，则分解式(1)是惟一的．

或者是,如果将这些都元素升序(降序)排序,则分解结果唯一

证明分为两部分进行

可分解性

先证 $n$ 可分解成素数的乘积.

当 $n$ 是素数时，定理显然成立.

当 $n$ 是合数时，记 $p_1$ 为 $n$ 的最小素因子，则有

• $n=p_1{n}_1$,$1<n_1<n.$

• $n_1=p_2{n}_2$,$1<n_2<n_1$;

• $n_2=p_3{n}_3$,$1<n_3<n_2$;

• …继续上述过程

• $n_{m-1}=p_m$

得 $n>n_1>n_2>\cdots >1$,其中$1<n_{i+1}<n_i,(i=1,2,\cdots )$，此过程不能超过 $n$ 次，

只要$n_i$是个合数,就能继续分解,直到其变成一个素数为止

所以最后必有$n=p_1{p}_2\cdots p_m.$

惟一性

证明分解的唯一性,从分解后的约数数量和取值分别判断相等,并且通常取定一个顺序,便于比较取值对应相等

设 $n=p_1{p}_2\cdots p_m=q_1{q}_2\cdots q_t$，

其中 $p_1⩽p_2⩽\cdots ⩽p_m$，$q_1⩽q_2⩽\cdots ⩽q_t$，且 $p_i,q_j$ 均为素数 ($1⩽i⩽m$, $1⩽j⩽t$).

由 $p_1|q_1\cdots q_t$ 和结论 3 知, ∃ j ∈ {   1 , 2 , ⋯   , t   } \exist{j\in\set{1,2,\cdots,t}} ∃j∈{1,2,⋯,t} 满足$p_1|q_j$，由于$p_1,q_j$都是素数,即得 $p_1=q_j⩾q_1$.

同理可得 $q_1=p_i⩾p_1$. 因此有 $p_1=q_1$.

重复以上论证，依次可证明 $p_2=q_2,\dots ,p_m=q_t$，从而 $m=t$.

唯一标准分解式

把 (1) 式中相同素数写成幂的形式，即得

$n=p_1^{{\beta }_1}{p}_2^{{\beta }_2}\cdots p_r^{{\beta }_r}$,$(p_1<p_2<\cdots <p_r)$, ( β i ⩾ 1 ; ( i ∈ {   1 , 2 , ⋯   , r   } ) ) . (\beta_i \geqslant 1;(i\in\set{1,2,\cdots,r})). (βi​⩾1;(i∈{1,2,⋯,r})).

上式称为 $n$ 的标准分解式，对给定的 $n$，标准分解式是唯一的.

定理2 标准分解式和正约数个数

设 $n=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\cdots p_s^{{\alpha }_s}$ 是 $n$ 的标准分解式，若用 $\tau (n)$ 表示 $n$ 的所有正约数的个数，则有
$$\tau (n)=({\alpha }_1+1)({\alpha }_2+1)\cdots ({\alpha }_s+1).$$

说明

标准分解式不仅给出了整数$n$的素数乘积表示,还间接给出了该整数$n$的正约数(能够整除$n$的所有正整数,不仅仅是素因数)个数

证明

利用排列组合证明

$n$ 的正约数 $d$ 必形如 $d=p_1^{l_1}\cdots p_s^{l_s}$，其中

• $l_1$ 可取 0 至 ${\alpha }_1$，共有 $({\alpha }_1+1)$ 种取法；

• $l_2$ 可取 0 至 ${\alpha }_2$，共有 $({\alpha }_2+1)$ 种取法；

• …

• $l_i$可取$0$至${\alpha }_i$,共有$({\alpha }_i+1)$种取法;

• …

• 因此有

$$\tau (n)=({\alpha }_1+1)({\alpha }_2+1)\cdots ({\alpha }_s+1).$$

例

$12=2^2\times 3^1$，12 的正约数有 $(2+1)(1+1)=6$ 个。

$360=2^3\times 3^2\times 5^1$，360 的正约数有 $(3+1)(2+1)(1+1)=24$ 个。

定理3

设 $a,b$ 是任意两个正整数，且
$$a=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\cdots p_k^{{\alpha }_k},{\alpha }_i⩾0,1⩽i⩽k,$$

$$b=p_1^{{\beta }_1}{p}_2^{{\beta }_2}\cdots p_k^{{\beta }_k},{\beta }_i⩾0,1⩽i⩽k,$$

则

$$(a,b)=p_1^{r_1}{p}_2^{r_2}\cdots p_k^{r_k},r_i=\min ({\alpha }_i,{\beta }_i),1⩽i⩽k,$$

$$[a,b]=p_1^{l_1}{p}_2^{l_2}\cdots p_k^{l_k},l_i=\max ({\alpha }_i,{\beta }_i),1⩽i⩽k.$$

原文地址：https://blog.csdn.net/xuchaoxin1375/article/details/143784304

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！