$p\mid n^3 -3n - 1 \implies p=3 \lor p\equiv \pm1\pmod{9}$

业余的业余

令 $p$ 为 $n^3-3 n-1$ ($n$为整数) 的质因数. 求证 $p=3$ 或 $p \equiv \pm 1\pmod 9$.
这题应该有些难度。还没有开始想。要求模拟这样一个例子:
定理: 令 $p$ 为 $n^3+n^2-2 n-1$ ($n$为整数) 的质因数. 则 $p=7$ 或 $p \equiv \pm 1\pmod 7$
证明: 有这样的 $n \in \mathbb{F}_p$ 满足 $n^3+n^2-2 n-1=0$. 令 $\alpha \in \mathbb{F}_{p^2}$ 为 $x^2-n x+1$ 的根, 那么 $\alpha \neq 0$ 且 $n=\alpha+\alpha^{-1}$. 我们有
$$
\begin{aligned}
0 & =\left(\alpha+\alpha^{-1}\right)^3+\left(\alpha+\alpha^{-1}\right)^2-2\left(\alpha+\alpha^{-1}\right)-1 \\
& =\alpha^3+3 \alpha+3 \alpha^{-1}+\alpha^{-3}+\alpha^2+2+\alpha^{-2}-2\left(\alpha+\alpha^{-1}\right)-1 \\
& =\alpha^3+\alpha^2+\alpha+1+\alpha^{-1}+\alpha^{-2}+\alpha^{-3}
\end{aligned}
$$
两边同乘以 $\alpha^3(\alpha-1)$ 有
$$
\alpha^7-1=0
$$
故 $\alpha$ 在 $\mathbb{F}_{p^2}$ 中的度（还是秩? order） $o(\alpha)$ 整除7。以下自然。
这个有趣的结论成立的关键在于对多项式 $f(x)=x^3+x^2-2 x-1$ ，我们有
$$
f\left(x+x^{-1}\right)=x^{-3} \Phi_7(x) .
$$
因 $\Phi_m(x)$ 是reciprocal, 故对任意 $m \geq 2$, 存在 $f(x) \in \mathbb{Z}[x]$ 使得
$$
f\left(x+x^{-1}\right)=x^{-\phi(m) / 2} \Phi_m(x) .
$$

hbghlyj

令 $\alpha \in \mathbb{F}_{p^2}$ 为 $x^2-n x+1$ 的根

如何證明存在根

hbghlyj

artofproblemsolving.com/community/c6h1910442p13099166
math.stackexchange.com/questions/3800911
math.stackexchange.com/questions/3989610
artofproblemsolving.com/community/c1068820h2215443p16802675
artofproblemsolving.com/community/c6h2088712p15083204
artofproblemsolving.com/community/c6h1412003p7937406
artofproblemsolving.com/community/c7h2210278p16721046

业余的业余

天哪，你太厉害了。好像方向刚好相反，看来是个重要条件。

业余的业余

如何證明存在根

根的存在性有个定理。如果老兄有兴趣, 回头我把证明整理上来。

业余的业余

用这个帖子整理下分圆多项式(cyclotomic polynomial)的知识。这个我基本是跳过了的, 回头整理下, 也算是给自己补漏, 并希望有微益于有缘人。

基本上现在在做的事是证明Dirichlet的这么个定理（的一些特殊情形）。

设 $a$ 和 $m$ 为互质的整数, 那么存在无限多的整数 $k$ 使得 $m k+a$ 为质数。

我们用欧几里德证明有无限多质数的那么个思路或者说套路, 证明这个定理的一些特例, 比如 $4 k \pm 1$.

以 $4 k-1$ 型为例, 欧式套路需要两点
1. 每个大于 2 (这是个摆设, 多数应用下都是恒真的)的 $4 k-1$ 型的整数都有一个 $4 k-1$ 型的质因数;
2. 设法构造一个两两互质的无穷整数数列, 让数列中的每一项都是 $4 k-1$ 型的。

随着情况越来越复杂, 需要不断地往工具箱里添加新的武器。比如证明形如 $q k+1$ (其中 $q$ 为质数)的质数有无穷多个时, 就引入了分圆多项式 (的特殊情形)。
要往欧式套路上引, 最主要的工作是构造一个两两互质的无穷数列, 其中每一项都含有 $q k+1$ 型的质因数。我们希望有一个工具来检验一个质数 $p$, 看它用质数 $q$ 取模时,是否是余 1 。分圆多项式隆重登场。

[特殊情形] $q$ 是一个质数时, 定义第 $q$ 个分圆多项式为
$$
\Phi_q(x)=\frac{x^q-1}{x-1}=x^{q-1}+x^{q-2}+\cdots+1 .
$$

我们有如下命题

令 $q$ 为奇素数。若对某个整数 $n$ 有质数 $p$ 整除 $\Phi_q(n)$ ，那么 $p \equiv 1\pmod q$ 或 $p=q$.
形式化的表述为:
$p, q \in\{$ 奇素数 $\} \wedge \exists_{n \in \mathbb{Z}}\left(p \mid \Phi_q(n)\right) \Longrightarrow p \equiv 1\pmod q \vee p=q$

证明: 因为 $\Phi_q(n) \mid n^q-1$ ，我们有 $p \mid n^q-1$ ，故 $o_p(n) \mid q$ 。那么 $o_p(n)=1$ 和 $o_p(n)=q$ 必居其一。
若 $o_p(n)=q$, 显然有 $p \equiv 1\pmod q$.
若 $o_p(n)=1$, 则 $n \equiv 1\pmod p$ 这时
$$
\Phi_q(n) \equiv 1^{q-1}+\cdots+1 \equiv q\pmod q
$$
这意味着 $p \mid q$ ，从而 $p=q$.

证毕

补充说明: (定义) 整数 $n$ 模 $m$ 的阶
当 $\operatorname{gcd}(n, m)=1$ 时, 我们称满足 $n^d \equiv 1\pmod m$ 的最小正整数 $d$ 为整数 $n$ 模 $m$ 的阶, 记为 $o_m(n)$.

有了分圆多项式这个工具，我们就可以构造对 $q k+1$ 型的欧式证法的无穷数列了。

为消除可能的 $p=q$ 的情形, 我们令 $a_1=\Phi_q(q), a_{n+1}=\Phi_q\left(q a_1 a_2 \cdots a_n\right)$. 这样就构造出了两两互质, 且每个元素都包含 $k q+1$ 型质数的无穷数列, 从而证明了 $q k+1$型素数无穷。

业余的业余

现在考虑 $q k+1$ 其中 $q$ 不是质数。
$o_p(a)=q \Longrightarrow p \equiv 1\pmod q$ 继续成立。其难点在于找到多项式 $\Phi_q(x)$ 使其根模 $p$ 的阶正好是 $q$, 而不是 $q$ 的某个真约数。可以试一下, 在 $\mathbb{Z}[x]$ 中找这个多项式有些棘手。办法是跳出整数甚至实数的限制, 在复数域中, $x^q-1$ 可因式分解为:
$$
x^q-1=\prod_{k=1}^q\left(x-\zeta_q^k\right)
$$
其中 $\zeta_q=e^{2 \pi i / q}$, 是单位数(1)的第 $q$ 个原始根。 $\zeta_q^{k}$ 均匀地分布在单位圆上, 这大概是分圆多项式得名的原因。这个跳出 $\mathbb{Z}$ 进到 $\mathbb{C}$ 的做法和后面的 跳出 $\mathbb{F}_p[x]$ 进到某个 $\mathbb{F}_{p^n}[x]$ 的处理如出一辄。两个对照着看更容易理解。

我们来看看 $\zeta_q^k$ 的阶, 即满足 $\zeta_q^{k d}=1$ 的最小正整数, 记为 $o\left(\zeta_q^k\right)$. 我们有
$$
\zeta_q^{k d}=1 \Leftrightarrow q\mid k d \Leftrightarrow \frac{q}{\operatorname{gcd}(q, k)}\mid \frac{k}{\operatorname{gcd}(q, k)} d \Leftrightarrow \frac{q}{\operatorname{gcd}(q, k)} \mid d
$$
故有 $o\left(\zeta_q^k\right)=q / \gcd(q, k)$. 当且仅当 $\operatorname{gcd}(q, k)=1$ 时, 这个阶为 $q$. 于是有如下定义

第 $q$ 分圆多项式
$$
\Phi_q(x)=\prod_{\substack{1 \leq k \leq q \\ \operatorname{gcd}(q, k)=1}}\left(x-\zeta_q^k\right)
$$

hbghlyj 探讨了分圆多项式基本性质, 等我比较下看有没有什么需要补充的。

业余的业余

1楼问题：
math.stackexchange.com/questions/3800911/prime-numbers-which-divide-n3-3n1
这个帖子对我有一些启发。
一度以为题目错了, 怎么可能 $n^3-3 n-1$ 和 $n^3-3 n+1$ 都是 $p=3$ 或 $p \equiv \pm 1\pmod 9$ 呢?

用电子表格测试了一些数据发现还真这么邪门。

模拟一楼的套路,
We have some $n \in \mathbb{F}_p$ such that $n^3-3 n-1=0$. Let $\alpha \in \mathbb{F}_{p^2}$ be a root of $x^2-n x+1$. Then $\alpha \neq 0$ and $n=\alpha+\alpha^{-1}$. Now
\begin{align}
0 & =\left(\alpha+\alpha^{-1}\right)^3-3\left(\alpha+\alpha^{-1}\right)-1\nonumber \\
& =\alpha^3-1+\alpha^{-3} \\
(1) \times \alpha^3 & \Longrightarrow 0=\alpha^6-\alpha^3+1 \\
(2) \times \alpha^3 & \Longrightarrow 0=\alpha^9-\alpha^6+\alpha^3 \\
(2)+(3) & \Longrightarrow \alpha^9=-1 \\
& \Longrightarrow \alpha^{18}=1\nonumber
\end{align}
We have $o(\alpha) \nmid 9$ and $o(\alpha) \mid 18$. Let $A$ denote the set of possible $o(\alpha)$. We have $1,3,9 \notin A$ as they divide 9 which is not $o(\alpha)$. We are left with $\{2,6,18\}$. Let's examine them one by one.
i. When $o(\alpha)=2$. By $\alpha^2=2$ and $\alpha^9=-1$, we have $\alpha=-1 \Longrightarrow \alpha^3=-1$. Plug $\alpha^6=1$ and $\alpha^3=-1$ into (2), we get $0=3$. This has to mean the characteristic of $F_p^2, p$, is 3 ;
ii. When $o(\alpha)=6$, we have $\alpha^6=1$ and $\alpha^9=-1$, hence $\alpha^3=-1$. This is the same as the above case, so again we have $p=3$;
iii. When $(\alpha)=18$. We have $18 \mid p^2-1$. In the mean time, we obviously have $2 \nmid n^3-3 n-1$, so $p^2-1$ is even. Consequently $18\left|p^2-1 \Longleftrightarrow 9\right| p^2-1 \Longrightarrow \exists_{k \in \mathbb{Z}}\left(9 k=p^2-1\right) \Longrightarrow 0 \equiv p^2-1\pmod 9\Longrightarrow p^2 \equiv 1\pmod 9 \Longrightarrow p= \pm 1\pmod 9$

In conclusion, we have $p=3$ or $p \equiv \pm 1\pmod 9$.

abababa

业余的业余 发表于 2023-10-24 06:35

这帖我存了一个pdf，但我编辑不了别人的帖子，上传一下那个pdf。
模p多项式.pdf (743.91 KB, 下载次数: 5)

2023-11-6 19:46 上传

点击文件名下载附件