|
|
本帖最后由 hbghlyj 于 2023-2-14 16:53 编辑 《简明数论》50页 习题七
5. 证明: $n !(n-1) ! \mid(2 n-2) !$.
6. 设 $a, b$ 是正整数, $(a, b)=1$. 证明 $: a ! b ! \mid(a+b-1) !$.
7. 设 $\alpha(p, n)$ 由 §7 定理 1 给出, 证明: $\alpha(p, n)<n /(p-1)$.
8. 证明 : $(2 n) ! /(n !)^{2}$ 是偶数.
9. 设 $a, b$ 是正整数. 证明 $: a ! b !(a+b) ! \mid(2 a) !(2 b) !$.
10. 设正整数 $n$ 的 $p$ 进位表示是:\begin{gathered}
n=a_{0}+a_{1} p+\cdots+a_{k} p^{k}, \\
0 \leqslant a_{j}<p, \quad 0 \leqslant j \leqslant k-1, \quad 1 \leqslant a_{k}<p .
\end{gathered}证明:(i) $a_{j}=\left[n / p^{j}\right]-p\left[n / p^{j+1}\right], 0 \leqslant j \leqslant k$;
(ii) 若 $p$ 是素数, $\alpha(p, n)$ 由 §7 定理 1 给出, 则
$$
\alpha(p, n)=\frac{n-A_n}{p-1}, \quad A_{n}=a_{0}+a_{1}+\cdots+a_{k} .
$$
11. 设 $n, a, b$ 是正整数. 证明:
$$
n ! \mid b^{n-1} a(a+b) \cdots(a+(n-1) b) .
$$
12. 设 $m, n$ 是正整数. 证明: $n !(m !)^{n} \mid(m n) ! $.
────────────────────────────────────────────────────
5.只需证明对任意素数$p$,$\left[\frac{2 n-2}p\right]⩾\left[\frac{n}p\right]+\left[\frac{n-1}p\right]$.
证明:
因为$\frac{n}p⩾\left[\frac{n}p\right],\frac{n-1}p⩾\left[\frac{n-1}p\right]$,而且不可能同时取等,
故$\frac{2 n-1}p>\left[\frac{n}p\right]+\left[\frac{n-1}p\right]$.
即$2 n-1>p\left(\left[\frac{n}p\right]+\left[\frac{n-1}p\right]\right)$.
因为右边是整数,所以$2 n-2⩾p\left(\left[\frac{n}p\right]+\left[\frac{n-1}p\right]\right)$.
即$\frac{2 n-2}p⩾\left[\frac{n}p\right]+\left[\frac{n-1}p\right]$.
因为右边是整数,所以$\left[\frac{2 n-2}p\right]⩾\left[\frac{n}p\right]+\left[\frac{n-1}p\right]$
注:卡塔兰数$C_{n-1}={\frac {1}{n}}{2n-2 \choose n-1}={\frac {(2n-2)!}{n!\,(n-1)!}}$
6.只需证明对任意素数$p$,$\left[\frac{a+b-1}p\right]⩾\left[\frac{a}p\right]+\left[\frac{b}p\right]$.
证明:
因为$\frac{a}p⩾\left[\frac{a}p\right],\frac{b}p⩾\left[\frac{b}p\right]$.因为$(a,b)=1$,所以不可能同时取等,
故$\frac{a+b}p>\left[\frac{a}p\right]+\left[\frac{b}p\right]$.
即$a+b>p\left(\left[\frac{a}p\right]+\left[\frac{b}p\right]\right)$.
因为右边是整数,所以$a+b-1⩾p\left(\left[\frac{a}p\right]+\left[\frac{b}p\right]\right)$.
即$\frac{a+b-1}p⩾\left[\frac{a}p\right]+\left[\frac{b}p\right]$.
因为右边是整数,所以$\left[\frac{a+b-1}p\right]⩾\left[\frac{a}p\right]+\left[\frac{b}p\right]$.
7. 由 §7 定理 1,$\alpha(p, n)=\sum_{j=1}^∞\left[n\over p^j\right]<\sum_{j=1}^∞{n\over p^j}={n\over p-1}$,又见stackexchange
或者使用10(ii)来证.
8.由第5题,${n !(n-1) !\over(2 n-2) !}$是整数,因此${(2 n) ! \over(n !)^2}=\frac{2n}n·{n !(n-1) !\over(2 n-2) !}=2{n !(n-1) !\over(2 n-2) !}$是偶数.
9.利用习题六第9题（$∀x,y∈\Bbb R:[2x]+[2y]⩾[x]+[y]+[x+y]$,又见这帖）即可。
10.(i)$a_{j}=(a_j+a_{j+1}p+⋯+a_kp^{k-j})-p(a_{j+1}+⋯+a_kp^{k-j-1})=\left[n / p^{j}\right]-p\left[n / p^{j+1}\right]$
(ii)\begin{aligned}\alpha(p, n)&=\sum _{i=1}^{ k }\left\lfloor {\frac {n}{p^{i}}}\right\rfloor \\&=\sum _{i=1}^{ k }\left(a_{ k }p^{ k -i}+\cdots +a_{i+1}p+a_{i}\right)\\&=\sum _{i=1}^{ k }\sum _{j=i}^{ k }a_{j}p^{j-i}\\&=\sum _{j=1}^{ k }\sum _{i=1}^{j}a_{j}p^{j-i}\\&=\sum _{j=1}^{ k }a_{j}\cdot {\frac {p^{j}-1}{p-1}}\\&=\sum _{j=0}^{ k }a_{j}\cdot {\frac {p^{j}-1}{p-1}}\\&={\frac {1}{p-1}}\sum _{j=0}^{ k }\left(a_{j}p^{j}-a_{j}\right)\\&={\frac {1}{p-1}}\left(n-A_n\right).\end{aligned}
又见Legendre's formula / Alternate form
11. 利用习题五第 1 题的方法, 对于任意$n!$的素因数 $p$, 去证明左边所含$p$的次数小于右边所含$p$的次数.
若 $p \mid b$, 利用第7题的结论, $α(p,n)<\frac{n}{p-1}⩽n-1$ 即可.
若$p \nmid b$, 设$p^e\|n$, $c=p^e$, 只需证明以下结论：
设 $(b, c)=1, c \mid n !$, 则 $c \mid a(a+b)(a+2 b) \cdots(a+(n-1) b) $.
证明：
因为$(b, c)=1$,所以存在整数$b'$使$bb'\equiv 1\pmod c$, 从而\begin{align*}&a(a+b)(a+2 b) \cdots(a+(n-1) b)
\\\equiv &abb'(abb'+b)(abb'+2 b) \cdots(abb'+(n-1) b)
\\=&b^n·ab'(ab'+1)(ab'+2) \cdots(ab'+(n-1))\pmod c\end{align*}
因为$ab',(ab'+1),(ab'+2), \dots,(ab'+(n-1))$是$n$个连续整数,所以是$n!$的倍数,所以是$c$的倍数.证毕.
又见stackexchange
12. 只要证
$$
\boxed{\text{对任一素数 $p$, 有}\sum_{j=1}^∞\left[n m / p^{j}\right] \geqslant n \sum_{j=1}^∞\left[m / p^{j}\right]+\sum_{j=1}^∞\left[n / p^{j}\right] }
$$
设 $m=p^{l} c, p \nmid c$. 当 $j \leqslant l$ 时, $\left[n m / p^{j}\right]=n\left[m / p^{j}\right]$, 因此
$$
\sum_{j=1}^l\left[n m / p^{j}\right]= n \sum_{j=1}^l\left[m / p^{j}\right]\tag1
$$
当 $j>l$ 时, 设 $m$ $=q_{j} p^{j}+r_{j}, 0<r_{j}<p^{j}-1$. 我们有
$$
\left[n m / p^{j}\right]=n q_{j}+\left[n r_{j} / p_{j}\right]=n\left[m / p^{j}\right]+\left[n\left\{m / p^{j}\right\}\right] .
$$
由此及 $\left\{m / p^{j}\right\}=\left\{c / p^{j-l}\right\} \geqslant 1 / p^{j-l}$ 推出(作代换$j←j-l$)
$$
\sum_{j>l}\left[n m / p^{j}\right] \geqslant n \sum_{j>l}\left[m / p^{j}\right]+\sum_{j=1}^{\infty}\left[n / p^{j}\right] .\tag2
$$
将(1),(2)式相加即得所要结果.
本题用排列组合法证简单:
在$mn$阶置换中,$n$个不交的长度为$m$的轮换之积的个数为$(m n) !\over n !(m !)^n$ |
|
