近世代数理论基础5：算术基本定理

2019-02-10 本文已影响2人溺于恐

算术基本定理

平凡因数

设 $a\gt 1$ 为任一整数,则 $\pm 1$ 与 $\pm a$ 是他的因数,称为平凡因数

素数

若 $p\in Z_+,p\gt 1$ 只有平凡因数,则称p为素数,否则称为合数

定理

定理：设p为素数,则 $\forall a\in Z$ ,有 $p|a$ 或 $(p,a)=1$

证明：

$\because (p,a)\gt 0且(p,a)|p$

$又p为素数$

$p的正素因数只有1与p$

$\therefore (p,a)=1或(p,a)=p$

$即(p,a)=1或p|a\qquad\mathcal{Q.E.D}$

推论：设 $a_1,a_2,\cdots,a_n\in Z$ , $p$ 为素数,且 $p|a_1a_2\cdots a_n$ ,则p整除某个 $a_i$

证明：

$n=1时,结论显然成立$

$假设n=k-1时,结论成立$

$下证n=k时结论也成立$

$令a=a_1a_2\cdots a_{k-1}$

$则p|a或(p,a)=1$

$由归纳假设$

$\exists i,1\le i\le k-1使p|a_i$

$若(p,a)=1$

$则\exists s,t\in Z使sp+ta=1$

$上式两边乘a_k可得$

$spa_k+taa_k=spa_k+ta_1a_2\cdots a_k=a_k$

$\because p|a_1a_2\cdots a_k$

$\therefore p|a_k\qquad\mathcal{Q.E.D}$

算术基本定理

定理：任一大于1的整数一定能表成素数的乘积,且该表示法除了次序外是唯一的,即若 $a\in Z,a\gt 1$ ,则有 $a=p_1p_2\cdots p_n$ ,其中 $p_i$ 为素数,且若又有 $a=q_1q_2\cdots q_m$ ,其中 $q_i$ 为素数,则 $m=n$ ,且适当调整次序后,对任意的 $1\le i\le n$ 都有 $p_i=q_i$

证明：

$若a=2$

$\because 2为素数,结论显然成立$

$假定定理对所有小于a的正整数均成立$

$下证定理对整数a也成立$

$若a为素数,则结论显然成立$

$若a为合数,则a=bc,其中1\lt b,c\lt a$

$由归纳假设$

$b=p_1p_2\cdots p_k,c=p_{k+1}p_{k+2}\cdots p_n$

$\therefore 对一切正整数(\ge 2)$

$均可分解成a=p_1p_2\cdots p_n$

$若又有a=q_1q_2\cdots q_m$

$则p_1p_2\cdots p_n=q_1q_2\cdots q_m$

$\therefore p_1|q_1q_2\cdots q_m$

$\therefore \exists q_j使p_1|q_j$

$\because p_1,q_j都为素数$

$\therefore p_1=q_j$

$通过调整次序,不妨设p_1=q_1$

$\therefore p_2p_3\cdots p_n=q_2q_3\cdots q_m$

$由归纳假设有$

$n-1=m-1且经过适当调整次序后p_i=q_i,i=2,3,\cdots,n$

$\therefore m=n且对任意的1\le i\le n有p_i=q_i\qquad\mathcal{Q.E.D}$

推论：

(1)任一大于1的正整数a都可唯一写成a的标准分解式

$a=p_1^{k_1}p_2^{k_2}\cdots p_t^{k_t},k_i\gt 0,i=1,2,\cdots t$

其中 $p_1\lt p_2\lt \cdots\lt p_t$ 为素数

(2) $\forall a,b\in Z_+$ 且 $a=p_1^{k_1}p_2^{k_2}\cdots p_t^{k_t},k_i\ge 0$

$b=p_1^{j_1}p_2^{j_2}\cdots p_t^{j_t},k_j\ge 0$

则 $(a,b)=p_1^{l_1}p_2^{l_2}\cdots p_t^{l_t}$

$[a,b]=p_1^{m_1}p_2^{m_2}\cdots p_t^{m_t}$

其中 $l_i=min\{k_i,j_i\},m_i=max\{k_i,j_i\},i=1,2,\cdots,t$

欧拉函数

定义：设 $a\in N$ ,记集合 $\{1,2,3,\cdots,a\}$ 中与a互素的整数个数为 $\varphi(a)$ , $\varphi$ 是一个定义在全体正整数集合上的一个函数,称为欧拉函数

例：设p为素数,则集合 $\{1,2,\cdots,p\}$ 中,与p互素的元为 $1,2,\cdots,p-1$ ,因此 $\varphi(p)=p-1$

注： $\forall k\ge 1$ ,有 $\varphi(p^k)=p^k-p^{k-1}$

集合 $\{1,2,\cdots,p^k\}$ 中有 $p^k$ 个元,对于该集合中任一元a, $(a,p^k)\gt 1\Leftrightarrow a=pt$ ,故与 $p^k$ 不互素的元有 $p^{k-1}$ 个,从而与 $p^k$ 互素的元有 $p^k-p^{k-1}$ 个

上一篇下一篇

猜你喜欢

热点阅读