$k\bmod7^n$ 有立方根 条件

hbghlyj

据 oeis.org/A319305 所述：对于 $7\nmid k$，

当且仅当 $k\equiv1, 6\pmod{7}$ 时，对任何正整数 n，$k\bmod7^n$ 都有一个立方根。
此外，如果 $k$ 有立方根，那么 $k$ 恰好有三个立方根。

如何证明

hbghlyj

例如，$\{1,\dots,7\}$范围内，$x^3\equiv6\mod7$有3个解：3, 5, 6
$\{1,\dots,7^2\}$范围内，$x^3\equiv6\mod7^2$有3个解：24, 34, 40
$\{1,\dots,7^3\}$范围内，$x^3\equiv6\mod7^3$有3个解：83, 122, 138
$\{1,\dots,7^4\}$范围内，$x^3\equiv6\mod7^4$有3个解：769, 808, 824
$\{1,\dots,7^5\}$范围内，$x^3\equiv6\mod7^5$有3个解：3170, 3225, 10412
$\{1,\dots,7^6\}$范围内，$x^3\equiv6\mod7^6$有3个解：36784, 87260, 111254
$\ldots\ldots$
如何证明呢

hbghlyj

更加诡异的是，在 OEIS 还给出只有一行的 PARI 程序a(n) = lift(sqrtn(6+O(7^(n+1)), 3) * (-1-sqrt(-3+O(7^(n+1))))/2)\7^n
其中，第二个乘数好像是三次单位根 $\frac{-1-\sqrt{-3}}2$，这是复数吗？它能mod 7^n吗？怎么理解？？🤯

爪机专用

请勿刷屏

hbghlyj

hbghlyj 发表于 2024-11-3 19:24
a(n) = lift(sqrtn(6+O(7^(n+1)), 3) * (-1-sqrt(-3+O(7^(n+1))))/2)\7^n

函数 lift 用于提升，例如将整数模 p
提升为整数，或将多项式模 p
提升为多项式。

还是不太明白

kuing

点评
hbghlyj 最近帖子数量的增加是因为剖析、讨论旧帖。主要是旧帖子分解出來的，新帖子沒有很多🙂

刷屏不分新旧，总之版块主题列表开头一堆几乎都是你的帖子，那就形成了刷屏。

hbghlyj

已在 MSE 得到热心网友的解答：

Indeed, if $a \in \mathbb Z_7^\times$ (e.g. $k \in \mathbb Z$ not divisible by $7$), then the polynomial $x^3-a$ has a root modulo $7$ if and only if $a \equiv \pm 1 \pmod{7}$ (direct check in $\mathbb F_7$). Further, Hensel's Lemma guarantees that this is equivalent to it having a root in $\mathbb Z_7$.

Now as also discussed in comments, $\mathbb Z_7$ contains the $6$th roots of unity (for any odd $p$, $\mathbb Z_p$ contains exactly the ($p-1$)-th roots of unity). Since $3$ divides $6$, in particular there are two choices for $\zeta_3 \in \mathbb Z_7$ such that $\zeta_3^3=1\neq \zeta_3$, and by basic algebra, if $x$ is a root of $x^3-a$, then so is $\zeta_3x$, i.e. this polynomial factors completely in $\mathbb Z_7$ if and only if it has a root at all.

hbghlyj

hbghlyj 发表于 2024-11-3 19:24
第二个乘数好像是三次单位根 $\frac{-1-\sqrt{-3}}2$

PARI/GP \begin{align*}2^3&\equiv1\pmod{7^1}\\ 30^3&\equiv1\pmod{7^2}\\ 324^3&\equiv1\pmod{7^3}\\ 1353^3&\equiv1\pmod{7^4}\\ 1353^3&\equiv1\pmod{7^5}\\ 34967^3&\equiv1\pmod{7^6}\\ 740861^3&\equiv1\pmod{7^7}\\ 2387947^3&\equiv1\pmod{7^8}\\ 25447151^3&\equiv1\pmod{7^9}\\ 146507972^3&\equiv1\pmod{7^{10}}\end{align*}

? n=1;;lift((-1-sqrt(-3+O(7^n)))/2)

%1 = 2

? n=2;;lift((-1-sqrt(-3+O(7^n)))/2)

%2 = 30

? n=3;;lift((-1-sqrt(-3+O(7^n)))/2)

%3 = 324

? n=4;;lift((-1-sqrt(-3+O(7^n)))/2)

%4 = 1353

? n=5;;lift((-1-sqrt(-3+O(7^n)))/2)

%5 = 1353

? n=6;;lift((-1-sqrt(-3+O(7^n)))/2)

%6 = 34967

? n=7;;lift((-1-sqrt(-3+O(7^n)))/2)

%7 = 740861

? n=8;;lift((-1-sqrt(-3+O(7^n)))/2)

%8 = 2387947

? n=9;;lift((-1-sqrt(-3+O(7^n)))/2)

%9 = 25447151

? n=10;;lift((-1-sqrt(-3+O(7^n)))/2)

%10 = 146507972

这些三次单位根模 p 都是怎么算出来的？