看心情填坑

我又来存档了。

二次剩余问题是求$x^{2}\equiv a(modp)$给出a求x的一种问题。

这里已经讲得非常清楚了，不再赘述。所以下文讨论的是三次剩余。为了方便，模数要求是大于3的素数。

即$x^3\equiv a(mod \ p)$给出a求x的一类问题

首先考虑假如不同的两个数x和y满足$x^3\equiv y^3$，那么有$(x-y)(x^2+xy+y^2)\equiv 0$显然$x-y$不会被p整除。

假如$p \not\equiv 1(mod \ 3)$那么考虑原根$a$，不妨假设$x=a^{i}$，$y=a^{j}$因为$p\not\equiv 1(mod \ 3)$所以$p-1$不是3的倍数，所以$i*3\not\equiv j*3(mod \ p-1)$得证$x^3\not\equiv y^3(mod \ p)(x\neq y)$

而对于$p\equiv 1(mod \ 3)$，可以通过枚举证明$x^3\not\equiv y^3(x \ mod \ 3=y \ mod \ 3)$。所以至多有三个数共享一个立方的位置。此时可以通过计算$a^{(p-1)/3}$来判断是否有解。

设原根为a那么此时p存在一个三次单位根$\epsilon\equiv a^{(p-1)/3}$，也就是说$x^{3}\equiv(x\epsilon )^{3}\equiv(x\epsilon ^{2})^{3}$。所以至少会有三个数共享一个立方的位置。

那么可以得出在1到p-1中的数只有三分之一存在三次剩余，因为三个数会共享一个立方的位置。

然后其实和二次剩余非常相似。随机出一个t，使得$t^3-a$是三次非剩余。随机的期望次数是9。我们定义一个三次单位根$\omega=\sqrt[3]{t^3-a}$然后定义一个域，域里的数都可以表示成$a*\omega ^{0}+b*\omega ^{1}+c*\omega ^{2}$的形式。

然后求出$(t+(p-1)\sqrt[3]{t^3-a})^{(p^2+p+1)/3}$就是答案。奥妙重重，其实和二次剩余的求法是类似的。

$\omega^{p}=\omega\epsilon$

因为$\omega^{p-1}=(\sqrt[3]{t^3-a})^{(p-1)/3}=\epsilon$

$(a+b)^{p}=a^{p}+b^{p}$

其实这些前面那个讲二次剩余里的都有，我这里简略提一下，具体去看那里。

$x^3=(t-\omega)^{p^2+p+1}$

$=(t-\omega)(t^{p^2+p}-t^{p^2}*\omega^{p}-t^{p}*\omega^{p^2}+\omega^{p^2+p})$

$=(t-\omega)(t^{2}-t\omega \epsilon-t\omega\epsilon^{2}+\omega^{2})$

$t\omega\epsilon+t\omega\epsilon^{2}=t\omega(\epsilon-\epsilon^{3})/(1-\epsilon)=-t\omega$

所以上面那个式子$=(t-\omega)(t^{2}+t\omega+\omega^{2})=t^3-\omega^{3}=a$

妙啊妙啊。

还有就是，这个东西貌似可以推广到k次剩余，先把k分解成若干个质因子然后一个个做，（貌似）对于$p%k!=1$解必定唯一而且可以用原根求解(这个可以同样方法证明)，假如$p%k=1$那么就可以用上面的方法构造$\omega=\sqrt[k]{t^k-a}$然后算$(t-\omega)^{(p^{k-1}+p^{k-2}+...+p+1)/k}$即可。虽然我并不会证，但是这个东西（好像）是对的，网上资料实在太少了_(:зゝ∠)_