2
20
2017
1

二次剩余和三次剩余相关

我又来存档了。

二次剩余问题是求$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}$即可。虽然我并不会证,但是这个东西(好像)是对的,网上资料实在太少了_(:зゝ∠)_

Category: 存档 | Tags: 数论 存档 剩余系 | Read Count: 839
Avatar_small
Brooke Zelman 说:
2018年7月15日 14:25

This is quite helpful share for students that provide sufficient knowledge with proper discussion on solution. Students of college classes like to buy custom essay paper online that is written by qualified writer.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com