$C_{2p}^p=2 \mod p^2$

realnumber

p为奇素数，求证:(1)$C_{2p}^p=2   \mod p$,  (2)$C_{2p}^p=2   \mod p^2$
以前似乎在奥数论坛看到过，这个论坛都搜不到了.

爪机专用

哪个奥数论坛？奥数之家？那个早挂了

abababa

\begin{align*}
\binom{2p}{p}
&=\frac{(2p)!}{p!(2p-p)!}
=\frac{2p\cdot(2p-1)\cdots(2p-p+1)\cdot p\cdot(p-1)\cdots(1)}{p^2(p-1)!}\\
&\equiv\frac{2p^2(-1)^p(p-1)!(p-1)!}{p^2(p-1)!}\equiv-2(p-1)!\equiv2\pmod{p}
\end{align*}

最后一个恒等号是根据威尔逊定理

hbghlyj

使用 Vandermonde 恒等式
$$\sum\limits_{i=0}^{k} {m \choose i}{n \choose k-i} = {m+n \choose k}.$$设 $m = n = k = p$ 得
$${2p \choose p} = {p \choose 0}{p \choose p}+{p \choose 1}{p \choose p-1}+\cdots+{p \choose p-1}{p \choose 1}+{p \choose p}{p \choose 0}.$$右边的第一个和最后一个项等于 1。
$${2p \choose p} = 1+{p \choose 1}{p \choose p-1}+\cdots+{p \choose p-1}{p \choose 1}+1.$$
由于 $p$ 是素数，$p$ 整除 ${p \choose k}$，对于所有 $1 \le k \le p-1$。
所以剩余的每个项都能被 $p^2$ 整除，因此 ${2p \choose p}\equiv2 \pmod {p^2}$。

hbghlyj

推廣：如果 $p$ 是素数，且 $a,b$ ($a\ge b$) 是任意正整数，则
$$\binom{pa}{pb}\equiv \binom{a}{b}\pmod {p}$$
$$\binom{pa}{pb}\equiv \binom{a}{b}\pmod {p^2}$$

hbghlyj

hbghlyj 发表于 2024-11-5 09:13
推廣：如果 $p$ 是素数，且 $a,b$ ($a\ge b$) 是任意正整数，则$\binom{pa}{pb}\equiv \binom{a}{b}\pmod {p}$

知乎专栏- Wolstenholme定理 有此问题！
质数$p\ge5,$

• $ \left(\begin{array}{c}a p \\ b p\end{array}\right)\equiv\left(\begin{array}{l}a \\ b\end{array}\right)\pmod{p^3}$
  取$a=2,b=1$推出$\left(\begin{array}{c}2 p \\ p\end{array}\right)\equiv2\pmod{p^3}$，注意到$\dfrac{2p}p\left(\begin{array}{c}2 p-1 \\ p-1\end{array}\right)=\left(\begin{array}{c}2 p \\ p\end{array}\right)$，即得$\left(\begin{array}{c}2 p-1 \\ p-1\end{array}\right)\equiv1\pmod{p^3}$
• $(p-1) !\left(1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{p-1}\right) \equiv0\pmod{p^{2}}$
  $(p-1) !^{2}\left(1+\frac{1}{2^{2}}+\frac{1}{3^{2}}+\cdots+\frac{1}{(p-1)^{2}}\right) \equiv 0\pmod{p}$
• 若$\left\{k_1, 2^2 k_{2}, \dots, \left(\frac{p-1}{2}\right)^{2} \cdot k_{\frac{p-1}{2}}\right\}$对模$p$同余
  且$k_1,k_2,\dots,k_{p-1\over2}$都小于1
  则有$k_1+\dots+k_{p-1\over2}$被$p$整除.
• 注意到问题2的第1式可以首尾相加！$\displaystyle \Leftrightarrow p^2\Bigg|(p-1)!\sum_{i=1}^{p-1\over2}{p\over i(p-i)}\Leftrightarrow p\Bigg|\sum_{i=1}^{p-1\over2}{(p-1)!\over i(p-i)}$

以上全部等价！

hbghlyj

hbghlyj 发表于 2024-11-5 09:17
4. $\displaystyle p\Bigg|\sum_{i=1}^{p-1\over2}{(p-1)!\over i(p-i)}$

问题4怎么证明？
手写无法识别！
只知道左下角写的是:
$\implies k^2i(p-i)=-(ki)^2\equiv-1\pmod p$
由威尔逊定理得$(p-1)!\equiv-1\pmod p$
$\implies(p-1)!\equiv k^2i(p-i)\pmod p$
$\implies\displaystyle \sum_{i=1}^{p-1\over2}{(p-1)!\over i(p-i)}\equiv k^2\equiv{p^3-p\over24}\equiv0\pmod p$

realnumber

hbghlyj 发表于 2024-11-5 17:05
使用 Vandermonde 恒等式
$$\sum\limits_{i=0}^{k} {m \choose i}{n \choose k-i} = {m+n \choose k}.$$设  ...

看懂了,恒等式可以理解为$(1+x)^{2p}=(1+x)^p(1+x)^p$展开后$x^p$的系数

hbghlyj

realnumber 发表于 2024-11-5 09:24
看懂了,恒等式可以理解为$(1+x)^{2p}=(1+x)^p(1+x)^p$展开后$x^p$的系数

你能看看 5 楼的一般问题吗？您的问题是 $a=2,b=1$ 的特殊情况$${ap \choose bp} \equiv {a \choose b} \pmod{p^2}$$
对于 $p \geq 5$，它可以加强为$${ap \choose bp} \equiv {a \choose b} \pmod{p^3}$$

realnumber

hbghlyj 发表于 2024-11-5 17:18
问题4怎么证明？
手写无法识别！
只知道左下角写的是:

$i(p-i)=-i^2  \mod p$,
$k_i^2$就是$i^2$的逆元,
$ \sum_{i=1}^{p-1\over2}{(p-1)!\over i(p-i)}\equiv -\sum_{i=1}^{(p-1)/2}k_i^2\equiv-{p^3-p\over24}\equiv0\pmod p$

hbghlyj

Wikipedia
对于素数 $p \geq 5$，
$${2p-1 \choose p-1} \equiv 1 \pmod{p^3}$$
成立。 例如，$p= 7$ 表示 1716 比 343 的倍数大一。该定理由Joseph Wolstenholme于 1862 年首次证明。1819 年，查尔斯·巴贝奇 (Charles Babbage) 证明了模 $p^{2}$ 的同余当 $p \geq 3$ 时成立。一个等价定理是模 $p$ 的同余定理
$${ap \choose bp} \equiv {a \choose b} \pmod{p^3}$$
，这是 Wilhelm Ljunggren 提出的（在特殊情况下 $b = 1$，则由 J.W.L.Glaisher 提出），并且受到了卢卡斯定理的启发。

没有已知的合数满足Wolstenholme定理，据推测也没有（见下文）。满足模 $p^4$ 同余的素数称为 Wolstenholme素数。

As Wolstenholme himself established, his theorem can also be expressed as a pair of congruences for (generalized) harmonic numbers:
$$1+{1 \over 2}+{1 \over 3}+\dots+{1 \over p-1} \equiv 0 \pmod{p^2} \mbox{, and}$$
$$1+{1 \over 2^2}+{1 \over 3^2}+\dots+{1 \over (p-1)^2} \equiv 0 \pmod p. $$
(Congruences with fractions make sense, provided that the denominators are coprime to the modulus.)
For example, with $p=7$, the first of these says that the numerator of 49/20 is a multiple of 49, while the second says the numerator of 5369/3600 is a multiple of 7.

hbghlyj

hbghlyj 发表于 2024-11-5 09:17
1. 质数$p\ge5,$
$\left(\begin{array}{c}2 p-1 \\ p-1\end{array}\right)\equiv1\pmod{p^3}$
$ \left(\begin{array}{c}a p \\ b p\end{array}\right)\equiv\left(\begin{array}{l}a \\ b\end{array}\right)\pmod{p^3}$

1.的证明
证明Wolstenholme定理的方法不止一种。下面是一个使用组合数学和代数证明Glaisher版本的Wolstenholme定理。

设 $p$ 为任意素数，$a$ 和 $b$ 为任意非负整数。则一个有 $ap$ 个元素的集合 $A$ 可以被分成 $a$ 个长度为 $p$ 的环，并且这些环可以分别旋转。因此，阶为 $p$ 的循环群的 $a$ 次直和作用在集合 $A$ 上，并且扩展到作用在大小为 $bp$ 的子集的集合上。这个群作用的每个轨道都有 $p^k$ 个元素，其中 $k$ 是与轨道中的子集 $B$ 部分地相交的环的数量。大小为 1 的轨道有 $\textstyle {a \choose b}$ 个，并且没有大小为 $p$ 的轨道。因此我们首先得到 Babbage 定理
$${ap \choose bp} \equiv {a \choose b} \pmod{p^2}.$$
通过检查大小为 $p^2$ 的轨道，我们还得到
$${ap \choose bp} \equiv {a \choose b} + {a \choose 2}\left({2p \choose p} - 2\right){a -2 \choose b-1} \pmod{p^3}.$$
除此之外，这个方程告诉我们，Wolstenholme 定理的第二种形式当 $a=2$ 和 $b=1$ 时成立则对于所有正整数 $a$ 和 $b$ 成立。

从组合学转到代数，对于每个固定的 $b$，这个同余的两边都是 $a$ 的多项式。因此，当 $a$ 是任意整数时，同余仍然成立，无论是正数还是负数，只要 $b$ 是一个固定的正整数。特别地，如果 $a=-1$ 且 $b=1$，同余变为
$${-p \choose p} \equiv {-1 \choose 1} + {-1 \choose 2}\left({2p \choose p} - 2\right) \pmod{p^3}.$$
因${-1 \choose 1}=-1,{-1 \choose 2}=1$，
$${-p \choose p} \equiv -1 + {2p \choose p} - 2 \pmod{p^3}.$$
使用 ${-p \choose p} = \frac{(-1)^p}2{2p \choose p}$ 这个同余变成了 $\textstyle {2p \choose p}$ 的一个方程
$$\frac{-1}2{2p \choose p}\equiv {2p \choose p} - 3 \pmod{p^3}$$
当 $p$ 是奇数时，将两边同乘2，
$$3{2p \choose p} \equiv 6 \pmod{p^3}.$$
当 $p$≠3 时，我们可以将两边同除以 3 来完成论证${2p \choose p} \equiv 2 \pmod{p^3}$。

模 $p^4$ 可以类似地推导出
$${ap \choose bp} \equiv {a \choose b} \pmod{p^4}$$
对于所有正整数 $a$ 和 $b$ 成立，当且仅当它在 $a=2$ 和 $b=1$ 时成立，即当且仅当 $p$ 是 Wolstenholme 素数。

hbghlyj

hbghlyj 发表于 2024-11-5 09:13
推廣：如果 $p$ 是素数，且 $a,b$ ($a\ge b$) 是任意正整数，则
$$\binom{pa}{pb}\equiv \binom{a}{b}\pmod {p}$$

Sylow 第一定理. Sylow $p$-子群存在.
证明：记 $U = \{ X \subset G \mid |X| = p^n \}$ 为 $G$ 的 $p^n$ 元子集之集. 则
\[
    |U| = \binom{p^n m}{p^n} \equiv m \pmod p.
\]
因此, $p \nmid |U|$.
而 $G$ 通过左乘作用于 $U$,
故存在轨道 $O \subset U$ 使得 $p \nmid |O|$.
取 $X \in O$, 设 $H \subset G$ 是 $X$ 的稳定子,
从而 $|O| = [G : H]$, 故 $p^n \mid |H|$.
另一方面, 取 $x \in X$, 则 $H x \subset X$,
从而 $|H| = |H x| \leq |X| = p^n$.
因此, $|H| = p^n$, 故 $H$ 是 $G$ 的 Sylow $p$-子群.

---

M. A. Armstrong 所著
Groups and Symmetry 中有类似的证明：
Let $G$ be a finite group whose order is divisible by the prime number $p$. Suppose $p^m$ is the highest power of $p$ which is a factor of $|G|$ and set $k=|G| / p^m$.
(20.1) The group $G$ contains at least one subgroup of order $p^m$.

Proof of (20.1). Let $X$ denote the collection of all subsets of $G$ which have $p^m$ elements and let $G$ act on $X$ by left translation, so that the group element $g \in G$ sends the subset $A \in X$ to $g A$. The size of $X$ is the binomial coefficient $\left(\begin{array}{c}k p^m \\ p^m\end{array}\right)$, which is not divisible by $p$ (see Exercise 20.14). Hence, there must be an orbit $G(A)$ whose size is not a multiple of $p$.
By Orbit-Stabilizer theorem We have $|G|=|G(A)| .\left|G_A\right|$, consequently $\left|G_A\right|$ is divisible by $p^m$. Now $G_A$ is the stabilizer of $A$, so if $a \in A$ and $g \in G_A$, then $g a \in A$. This means that the whole right coset $G_A a$ is contained in $A$ whenever $a \in A$, and $\left|G_A\right|$ cannot exceed $p^m$. Therefore, $G_A$ is a subgroup of $G$ which has order $p^m$.

hbghlyj

这个有关组合数的同余式怎么证明?
$\displaystyle{p^3\choose p^2}\equiv{p^2\choose p}\ (\mathrm{mod}\ p^8)$
回答：你的结论仅当 $p\geq 5$ 时成立。Charles Helou和Guy Terjanian的这篇文章中的性质2.(1)

令 $p$ 为素数，$p\geq5$，$m,n\in \mathbb{N},0\leq m\leq n$，则有：$${np\choose mp}\equiv{n\choose m}\cdot(1-mn(n-m)(\frac{p^3}{2}B_{p^3-p^2-2}-\frac{p^5}{6}B_{p-3}+\frac{1}{5}(m^2-mn+n^2)p^5B_{p-5}))\quad(\mathrm{mod} p^{6+v_p(n-m)+v_p({n \choose m})})$$
（其中 $B_n$ 是伯努利数）可以直接推出你的结论（$n=p^2,m=p$， 同余的次数是 $8$，右边那一大坨能被 $p^7$ 整除）。根据后面的推论和注记，我们有如下结论：

令 $p$ 为素数，$p\geq 5$，$m,n\in\mathbb{N},0\leq m\leq n$，则有$${np \choose mp}\equiv{n \choose m}\quad (\mathrm{mod}\ p^{3+v_p(m)+v_p(n)+v_p(n-m)+v_p({n\choose m})})$$
以及Romeo Mestrovic写过一篇关于Wolstenholme定理的各种推广的综述：arxiv.org/pdf/1111.3057

hbghlyj

拉格朗日定理及其应用 作者：LesterCircle
定理 7.2 (Wilson). $p$ 为素数, 则
$$
(p-1)!\equiv-1(\bmod p)
$$一般是利用数论倒数进行证明, 这里我们利用 Lagrange 定理来证明, 顺带引出常用的构造方法.

定理 7.2 的证明. 令 $f(x)=(x-1)(x-2) \cdots(x-(p-1))-\left(x^{p-1}-1\right)$.
$f(x)$ 是一个 $p-2$ 次多项式, 其在模 $p$ 意义下的次数不超过 $p-2$. 显然, $x=1,2, \cdots, p-1$ 都是同余方程 $f(x) \equiv 0(\bmod p)$ 的解，那么定理7.1，$f(x)$ 展开式中 $x$ 各次幂系数均被 $p$ 整除。

特别地, 考察 $f(x)$ 的常数项, 有
$$
(-1)^{p-1}(p-1)!+1 \equiv 0(\bmod p)
$$
对于 $p=2$, 得 $(p-1)!\equiv 1 \equiv-1(\bmod p)$;
对于 $p>2$, 得 $(p-1)!\equiv-(-1)^{p-1} \equiv-1(\bmod p)$.
于是对任意素数 $p$, $(p-1)!\equiv-1(\bmod p)$, 命题得证.

定理 7.3 (Wolstenholme,1862). 若 $p$ 是大于 3 的素数, 则
$$
1+\frac{1}{2}+\cdots+\frac{1}{p-1} \equiv 0\left(\bmod p^2\right) .
$$
定理 7.3 的证明.
$$
\begin{aligned}
f(x) & =(x-1)(x-2) \cdots(x-(p-1))-\left(x^{p-1}-1\right) \\
& =a_{p-2} x^{p-2}+\cdots+a_1 x+a_0 .
\end{aligned}
$$
根据定理 7.2 的证明, 可知 $a_{p-2} \equiv \cdots \equiv a_1 \equiv a_0 \equiv 0(\bmod p)$.
由 $a_{p-2} p^{p-2}+\cdots+a_1 p+a_0=f(p)=(p-1)!-p^{p-1}+1=a_0-p^{p-1}$, 得 $a_1 p \equiv 0\left(\bmod p^3\right) \Longrightarrow a_1 \equiv 0\left(\bmod p^2\right)$, 即
$$
\begin{aligned}
a_1&= (-1)^{p-2}(p-1)!\sum_{k=1}^{p-1} \frac{1}{k} \equiv 0\left(\bmod p^2\right) \\
&\Longrightarrow 1+\frac{1}{2}+\cdots+\frac{1}{p-1} \equiv 0\left(\bmod p^2\right) .
\end{aligned}
$$
注. 定理 7.3 的几个等价命题:
(1) $\binom{2 p-1}{p-1} \equiv 1\left(\bmod p^3\right)$;
(2) $1+\frac{1}{2^2}+\cdots+\frac{1}{(p-1)^2} \equiv 0(\bmod p)$;
(3) $\binom{a p}{b p} \equiv\binom{a}{b}\left(\bmod p^3\right)$;
(4) $\sum_{k=1}^{p-1} \frac{1}{n p+k} \equiv 0\left(\bmod p^2\right)$.

事实上，
对于 (1), 更一般地有: (Guerin Theorem)
$$
\begin{aligned}
a_1(m-1) p & \equiv f(m p)-f(p) \\
& \equiv(m p-1)(m p-2) \cdots((m-1) p+1)-(p-1)!-p^{p-1}\left(m^{p-1}-1\right) \\
& \equiv(p-1)!\left[\binom{m p-1}{p-1}-1\right]\left(\bmod p^3\right) .
\end{aligned}
$$
对于 (2),
$$
\begin{aligned}
1+\frac{1}{2^2}+\cdots+\frac{1}{(p-1)^2} & \equiv 1+2^2+\cdots+(p-1)^2 \\
& \equiv \frac{(p-1) p(2 p-1)}{6} \equiv 0(\bmod p)
\end{aligned}
$$
另一方面, 根据组合恒等式, 有
$$
\begin{aligned}
\binom{p}{k}= & \binom{p-1}{k}+\binom{p}{k-1} \Rightarrow\binom{p-1}{k} \equiv(-1)^k(\bmod p), k=1,2, \cdots, p-1 \\
& 2\left[\binom{2 p-1}{p-1}-1\right]=\binom{2 p}{p}-2=\sum_{i=0}^p\binom{p}{i}^2-2=p^2 \cdot \sum_{i=1}^{p-1}\left[\frac{1}{i}\binom{p-1}{i-1}\right]^2 .
\end{aligned}
$$
于是
$$
2\left[\binom{2 p-1}{p-1}-1\right] \equiv p^2 \cdot \sum_{i=1}^{p-1} \frac{1}{i^2}\left(\bmod p^3\right) .
$$
对于 (3) (4), 我们在下面单独证明.
定理 7.4 (Wilhelm Ljunggren,1952). 若 $p$ 是大于 3 的素数, 则
$$
\binom{a p}{b p} \equiv\binom{a}{b}\left(\bmod p^3\right) .
$$
定理 7.4 的证明.$$
\begin{aligned}
f(x) & =(x-1)(x-2) \cdots(x-(p-1))-\left(x^{p-1}-1\right) \\
& =a_{p-2} x^{p-2}+\cdots+a_1 x+a_0
\end{aligned}
$$
则
$$
a_{p-2}(n p)^{p-2}+\cdots+a_1 n p+a_0=f(n p)=\prod_{k=1}^{p-1}(n p-k)-(n p)^{p-1}+1 .
$$
对上式两边模 $p^3$ ，并结合 $a_1 \equiv 0\left(\bmod p^2\right)$ ，得对于任意整数 $n$
$$
\prod_{k=1}^{p-1}(n p-k) \equiv a_0-1=(p-1)!\left(\bmod p^3\right)
$$
注意到
$$
\binom{a p}{b p} \prod_{m=1}^b \prod_{k=1}^{p-1}(m p-k)=\binom{a}{b} \prod_{m=1}^b \prod_{k=1}^{p-1}[(a-b+m) p-k]
$$
于是
$$
\begin{aligned}
\binom{a p}{b p}[(p-1)!]^b & \equiv\binom{a p}{b p} \prod_{m=1}^b \prod_{k=1}^{p-1}(m p-k) \\
& =\binom{a}{b} \prod_{m=1}^b \prod_{k=1}^{p-1}[(a-b+m) p-k] \\
& \equiv\binom{a}{b}[(p-1)!]^b\left(\bmod p^3\right),
\end{aligned}
$$
即 $\binom{a p}{b p} \equiv\binom{a}{b}\left(\bmod p^3\right)$ ，命题得证。
注. E.Jacobsthal 于 1952 年证明了一个更强的结论: $\binom{a p}{b p} \equiv\binom{a}{b}\left(\bmod p^l\right)$, 其中 $l$是 $p^3 a b(a-b)$ 中 $p$ 的幂次.
若素数 $p$ 满足 $\binom{2 p-1}{p-1} \equiv 1\left(\bmod p^4\right)$ ，则称这样的素数为 Wolstenholme 素数，目前已知的 Wolstenholme 素数为 16843 和 2124679，如果存在下一个，则它至少大于 $10^9$.
对于更高的幂次, 还有如下结论
$$
\begin{aligned}
\binom{2 p-1}{p-1} & \equiv 1-2 p \sum_{k=1}^{p-1} \frac{1}{k}\left(\bmod p^4\right), p \geqslant 5 \\
\binom{2 p-1}{p-1} & \equiv 1-p^2 \sum_{k=1}^{p-1} \frac{1}{k^2} \equiv 1+2 p \sum_{k=1}^{p-1} \frac{1}{k}\left(\bmod p^5\right), p \geqslant 7 \\
\binom{2 p-1}{p-1} & \equiv 1+2 p \sum_{k=1}^{p-1} \frac{1}{k}+\frac{2 p^3}{3} \sum_{k=1}^{p-1} \frac{1}{k^3} \\
& \equiv 1-2 p \sum_{k=1}^{p-1} \frac{1}{k}-2 p^2 \sum_{k=1}^{p-1} \frac{1}{k^2}\left(\bmod p^6\right), p \geqslant 7 \\
\binom{2 p-1}{p-1} & \equiv 1-2 p \sum_{k=1}^{p-1} \frac{1}{k}+2 p^2\left[\left(\sum_{k=1}^{p-1} \frac{1}{k}\right)^2-\sum_{k=1}^{p-1} \frac{1}{k^2}\right] \\
& \equiv 1-2 p \sum_{k=1}^{p-1} \frac{1}{k}+4 p^2 \sum_{1 \leqslant i<j \leqslant p-1} \frac{1}{i j}\left(\bmod p^7\right), p \geqslant 11
\end{aligned}
$$
定理 7.5. 素数 $p>3$, 则
$$
\sum_{k=1}^{p-1} \frac{1}{n p+k} \equiv 0\left(\bmod p^2\right) .
$$
定理 7.5 的证明. 令
$$
\begin{aligned}
f(x) & =(x-1)(x-2) \cdots(x-(p-1))-\left(x^{p-1}-1\right) \\
& =a_{p-2} x^{p-2}+\cdots+a_1 x+a_0
\end{aligned}
$$
则
$$
\begin{aligned}
& {[x-(n p+1)][x-(n p+2)] \cdots[x-(n p+p-1)]-(x-n p)^{p-1}+1 } \\
= & f(x-n p)=a_{p-2}(x-n p)^{p-2}+\cdots+a_2(x-n p)^2+a_1(x-n p)+a_0
\end{aligned}
$$
比较两边 $x$ 一次项的系数, 并模 $p^2$, 得
$$
(-1)^{p-2} \prod_{s=1}^{p-1}(n p+s) \sum_{k=1}^{p-1} \frac{1}{n p+k} \equiv a_1 \equiv 0\left(\bmod p^2\right),
$$
即
$$
\sum_{k=1}^{p-1} \frac{1}{n p+k} \equiv 0\left(\bmod p^2\right),
$$
命题得证.
定理 7.6 (Euler 判别法). $p$ 为素数, $\operatorname{gcd}(a, p)=1$, 则
$$
\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}}(\bmod p) .
$$
定理 7.6 的证明. 若 $\left(\frac{a}{p}\right)=1$, 设 $d^2 \equiv a(\bmod p)$, 则根据 Fermat 小定理, $a^{\frac{p-1}{2}} \equiv$ $d^{p-1} \equiv 1(\bmod p)$ ，即 $\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}}(\bmod p)$ 。

若 $\left(\frac{a}{p}\right)=-1$, 则 $p>2$, 根据 Fermat 小定理, $p \left\lvert\,\left(a^{\frac{p-1}{2}}+1\right)\left(a^{\frac{p-1}{2}}-1\right)\right.$.假设 $a^{\frac{p-1}{2}} \not \equiv-1(\bmod p)$ ，则 $a^{\frac{p-1}{2}} \equiv 1(\bmod p)$ ，说明 $a$ 是模 $p$ 意义下多项式 $f(x)=x^{\frac{p-1}{2}}-1$ 的根.

根据定理 7.1, $f(x)$ 在模 $p$ 意义下至多有 $\frac{p-1}{2}$ 个根，而 $1^2, 2^2, \cdots,\left(\frac{p-1}{2}\right)^2$ 都是 $f(x) \equiv 0(\bmod p)$ 的根且两两模 $p$ 不同余. 于是必定存在 $d \in\left\{1,2, \cdots, \frac{p-1}{2}\right\}$ 使得 $d^2 \equiv a(\bmod p)$, 这与 $\left(\frac{a}{p}\right)=-1$ 矛盾! 故 $\left(\frac{a}{p}\right)=-1 \equiv a^{\frac{p-1}{2}}(\bmod p)$.
定理 7.7. $p$ 为素数, $n$ 为正整数, $n \leqslant p$, 则同余方程
$$
f(x)=x^n+a_{n-1} x^{n-1}+\cdots+a_1 x+a_0 \equiv 0(\bmod p), f(x) \in \mathbb{Z}[x]
$$
在模 $p$ 意义下恰有 $n$ 个解的充要条件是 $x^p-x$ 除以 $f(x)$ 后的余式在模 $p$ 意义下为 0 。

定理 7.7 的证明. 设
$$
x^p-x=f(x) q(x)+r(x), \operatorname{deg} r(x)<n, \operatorname{deg} q(x)=p-n \text {. }
$$
必要性: 已知 $f(x) \equiv 0(\bmod p)$ 恰有 $n$ 个解 $x_1, x_2, \cdots, x_n$, 那么根据 Fermat小定理, $x_i^p-x_i \equiv 0(\bmod p)$ ，进而有 $r\left(x_i\right) \equiv 0(\bmod p)$ 。但是根据定理7.1, $r(x) \equiv 0(\bmod p)$ 至多有 $\operatorname{deg} r(x)<n$ 个解，于是必有 $r(x) \equiv 0(\bmod p)$ 。
充分性: 已知 $r(x) \equiv 0(\bmod p)$, 则根据 Fermat 小定理, $f(x) q(x) \equiv x^p-x \equiv$ $0(\bmod p)$ 恰有 $p$ 个解 $0,1,2, \cdots, p-1$ 。
但是根据定理 7.1,
$f(x) \equiv 0(\bmod p)$ 至多有 $n$ 个解, $q(x) \equiv 0(\bmod p)$ 至多有 $p-n$ 个解,于是 $f(x) \equiv 0(\bmod p)$ 恰有 $n$ 个解, $q(x) \equiv 0(\bmod p)$ 恰有 $p-n$ 个解.
综上，命题得证。

推论. $p$ 为素数, $d$ 是 $p-1$ 的正因子, $(a, p)=1$, 若 $x^d-a \equiv 0(\bmod p)$ 有解, 则在模 $p$ 意义下恰有 $d$ 个解。

hbghlyj

hbghlyj 发表于 2024-11-5 11:48
则
\[
    |U| = \binom{p^n m}{p^n} \equiv m \pmod p.
\]
因此, $p \nmid |U|$.

mod p 同余由Lucas' theorem很容易证明
$p^mn$的$p$进制表示是$\overline{n00\dots0}$, $p^m$的$p$进制表示是$\overline{100\dots0}$, 所以
$${p^mn \choose p^m}\equiv{n \choose 1}{0\choose0}{0\choose0}\dots{0\choose0}=n\pmod p$$

hbghlyj

hbghlyj 发表于 2024-11-5 13:35
mod p 同余由Lucas' theorem很容易证明
$p^mn$的$p$进制表示是$\overline{n00\dots0}$, $p^m$的$p$进制表示 ...

为了避免使用卢卡斯定理，我们可以由Lucas' theorem的组合证明给出以下证明:
Partition a set $S$ of size $p^mn$ greedily into a disjoint union of parts each of size some power of$~p$, taken as large as possible. Now let the cyclic group of order the largest $p$-power present act on $S$, by having its generator rotate each of the parts one unit forward. This acts on subsets of $S$ as well. Counting the number of $p^m$-element subsets modulo$~p$, we can ignore all those whose orbit has size divisible by$~p$; given the order of the group acting, these are all subsets, except those completely invariant under the action. But the smallest parts in our partition are of size $p^m$, and only the $p^n$-subsets precisely equal to one of those parts will be invariant under the action. There are $n\bmod p$ such parts, which gives the stated congruence modulo$~p$.

hbghlyj

hbghlyj 发表于 2024-11-5 13:35
mod p 同余由Lucas' theorem很容易证明
$p^mn$的$p$进制表示是$\overline{n00\dots0}$, $p^m$的$p$进制表示 ...

为了避免使用卢卡斯定理，我们可以由Lucas' theorem的生成函数证明给出以下证明:
The idea is that you calculate the coefficient of $a^{p^n(k-1)}b^{p^n}$ in two ways and compare the results. The equality is only a congruence modulo $p$, so the result we get is also a congruence modulo $p$.

The first way:
$$(a+b)^{p^nk}=\sum_{i=0}^{p^nk}{p^nk\choose i}a^{p^nk-i}b^i.$$
To get a term $a^{p^n(k-1)}b^{p^n}$ we must select $i=p^n.$ Thus we get that
$$
(a+b)^{p^nk}=\cdots+{p^nk\choose p^n}a^{p^n(k-1)}b^{p^n}+\cdots.
$$

The second way:
Here we calculate (after that application of Freshman's dream)
$(a^{p^n}+b^{p^n})^k$. Again using the binomial theorem. This time we get
$$
(a^{p^n}+b^{p^n})^k=\sum_{i=0}^k{k\choose i}a^{p^n(k-i)}b^{p^ni}.
$$
To get the desired term we must select $i=1$. Thus
$$
(a^{p^n}+b^{p^n})^k=\cdots+{k\choose 1}a^{p^n(k-1)}b^{p^n}+\cdots.
$$
We are working in an algebraic structure (to be more precise: the ring of polynomials in two unknowns $a,b$, with coefficients in the residue class ring of integers $\mathbb{Z}_p$), where the presentation of a polynomial in terms of the basis of monomials is unique. Therefore we can conclude that in the ring
$\mathbb{Z}_p$ we have
$$
{p^nk\choose p^n}={k\choose 1},
$$
or, writing the same thing as a congruence, the claim
$$
{p^nk\choose p^n}\equiv k\pmod p.
$$

hbghlyj

hbghlyj 发表于 2024-11-5 11:48
Sylow 第一定理. Sylow $p$-子群存在.
证明：记 $U = \{ X \subset G \mid |X| = p^n \}$ 为 $G$ 的 $p^n$ 元子集之集. 则
\[
    |U| = \binom{p^n m}{p^n} \equiv m \pmod p.
\]
因此, $p \nmid |U|$.

实际上在以上 Sylow 定理的证明中我们不需要证mod p 同余，只需要它不被 p 整除即可：

$p$为质数, $p \nmid n$, 则$p\large∤{p^mn \choose p^m}$. MSE
证明. 将${p^mn \choose p^m}$写成$n$与$p^m-1$个分数之积
$${p^mn \choose p^m}
= n\frac{p^mn-1}{p^m-1}\frac{p^mn-2}{p^m-2}\dots\frac{p^mn-p^m+1}{p^m-p^m+1}$$
$p \nmid n$, 由Exercise 20.14知$\frac{p^mn-1}{p^m-1},\frac{p^mn-2}{p^m-2},\dots,\frac{p^mn-p^m+1}{p^m-p^m+1}$都不被$p$整除, 因此$p\large∤{p^mn \choose p^m}$.

hbghlyj

hbghlyj 发表于 2024-11-5 13:49
由Exercise 20.14知$\frac{p^mn-1}{p^m-1},\frac{p^mn-2}{p^m-2},\dots,\frac{p^mn-p^m+1}{p^m-p^m+1}$都不被$p$整除

这里使用了 M. A. Armstrong 所著Groups and Symmetry 中的练习20.14，这是给读者的练习，书中没有答案！

$p$ 为质数, $p∤k$, $0⩽x⩽p^m-1$, 则 $p\large∤{kp^m-x\over p^m-x}$.

这是我尝试的证明，请检查是否正确？

要证明$p$不整除$kp^m-x\over p^m-x$等价于证明分子与分母含因数$p$次数相同.
记$\nu_p(n)$为$n$含因数$p$次数. [它有一个性质: 若$\nu_p(a)>\nu_p(b)$, 则$\nu_p(a\pm b)=\nu_p(b)$.]
因为$\nu_p(x)<m=\nu_p(p^m)$, 所以$\nu_p(p^m-x)=\nu_p(x)$.
因为$\nu_p(x)<m=\nu_p(kp^m)$, 所以$\nu_p(kp^m-x)=\nu_p(x)$.
即$\nu_p(p^m-x)=\nu_p(kp^m-x)$. 证毕.