1. 素因数分解式的性质
在第一篇里面我们证明了算术基本定理. 下面我们对素因数分解式进行更细致的考察.
首先我们对分解式中相同的素数进行合并, 得到 \(a=p_1^{\alpha_1}\cdots p_s^{\alpha_{s}}, p_1<p_2<\cdots<p_s\).
有以下性质:
- \(d|a,d>0\Lrarr d=p_1^{e_1}\cdots p_s^{e_{s}}, 0\leqslant e_j\leqslant \alpha_{j}, 1\leqslant j\leqslant s\)
- 设 \(b=p_1^{\beta_1}\cdots p_s^{\beta_{s}}\), 则 \((a,b)=p_1^{\min\{\alpha_1,\beta_1\}}\cdots p_s^{\min\{\alpha_s,\beta_s\}}, [a,b]=p_1^{\max\{\alpha_1,\beta_1\}}\cdots p_s^{\max\{\alpha_s,\beta_s\}}\).
- \((a,b)=1,ab=c^k\Rarr a=u^k,b=v^k\)
都十分简单, 证明略.
实际上整除理论到这里就已经基本结束了. 下面的都是应用了.
首先引入两个重要的数论函数. 这里我们只讨论最基础的内容.
除数函数: \(\tau(a)=\sum_{d|a}1\)
除数和函数: \(\sigma(a)=\sum_{d|a}d\)
对于它们的计算有:
- \(\tau(a)=\prod\limits_{i=1}^s(\alpha_i+1)=\prod\limits_{i=1}^s\tau(p_i^{\alpha_i})\)
- \(\sigma(a)=\prod\limits_{i=1}^s\dfrac{p_i^{\alpha_i+1}-1}{p_i-1}=\prod\limits_{i=1}^s\sigma(p_i^{\alpha_i})\)
利用上面的性质, 进行一些简单的排列组合和代数化简即可推出. 证明略.
2. 取整函数
设 \(x\in\mathbb{R}\). 记 \([x]\) 为不超过 \(x\) 的最大整数, 即 \([x]\leqslant x<[x]+1, [x]\in\mathbb{Z}\).
称 \([x]\) 为 \(x\) 的整数部分, 记 \(\{x\}=x-[x]\) 为 \(x\) 的小数部分.
这个函数有一车性质, 这里列举一部分:
- \(x\leqslant y\Rarr [x]\leqslant [y]\)
- \(x=m+v,m\in\mathbb{Z},0\leqslant v<1\Rarr m=[x],v=\{x\}\)
- \([x+m]=[x]+m,\{x+m\}=\{x\}, m\in\mathbb{Z}\)
- \([x]+[y]\leqslant [x+y]\leqslant [x]+[y]+1\)
- \([-x]=\begin{cases}-[x],&x\in\mathbb{Z}\\-[x]-1,&x\notin\mathbb{Z}\end{cases}\)
- \(\{-x\}=\begin{cases}0,&x\in\mathbb{Z}\\1-\{x\},&x\notin\mathbb{Z}\end{cases}\)
- \(\left[\dfrac{[x]}{m}\right]=\left[\dfrac{x}{m}\right],m\in\mathbb{Z}\)
这里只证明 7.
设 \([x]=qm+r, 0\leqslant r<m\), 则显然 \(\left[\dfrac{[x]}{m}\right]=q.\)
又 \(\dfrac{x}{m}=q+\dfrac{\{x\}+r}{m}\), 注意到 \(r<m\) 且为整数, \(\{x\}<1\), 易知 \(\dfrac{\{x\}+r}{m}<1, \left[\dfrac{x}{m}\right]=q=\left[\dfrac{[x]}{m}\right]\).
取整函数常用于计算整点个数. 设 \(y=f(x)\ (x_1<x\leqslant x_2)\) 为非负连续函数, 则考察曲边梯形 \(x_1<x\leqslant x_2, 0<y\leqslant f(x)\), 有:
- 该区域内整点个数为 \(\sum\limits_{n=x_1}^{x_2}[f(n)]\).
- \(0\leqslant \sum\limits_{n=x_1}^{x_2}f(n)-\sum\limits_{n=x_1}^{x_2}[f(n)]\leqslant [x_2]-[x_1]\).
这都是显然的, 证明略.
3. 阶乘的素因数分解式
我们用 \(a^k||b\) 表示 \(a^k|b, a^{k+1}\nmid b\).
设 \(p^{\alpha(p,n)}||n!\), 则 \(n!\) 的素因数分解式即为 \(n!=\prod_{p\leqslant n}p^{\alpha(p,n)}\). 我们只需求出 \(\alpha(p,n)\) 的值.
不难得出: \(\alpha(p,n)=\sum\limits_{j=1}^{\infin}[n/p^j]\).
解释: 对于 \(1<k\leqslant n,p^j||k\), 它恰被从 \(p\) 到 \(p^j\) 数了 \(j\) 次.