Legendre 符号（数论）

                     

贡献者： int256

预备知识　二次剩余

1. 定义

定义 1　Legendre 符号

　　 对于一个奇素数 p 与一个不被 p 整除的数 a，定义 勒让德符号（Legendre 符号） (ap) 是：

  • 若 aRp 则 (ap)=+1；
  • 若 aNp 则 (ap)=−1。

推论 1　

　　 由定义，立刻有

(1)(ap)2=1 .

推论 2　

　　 若 a≡b(modp)，而 a 为不被奇素数 p 整除的数，则

(2)(ap)=(bp) .

　　 当 p=2 时，不考虑其 Legendre 符号。

2. 应用

定理 1　

　　 对于奇素数 p，若 a 不是 p 的倍数，则

(3)(p−1)!≡−(ap)a(p−1)/2(modp) .

　　 证明：若 aRp 且有 x12≡a(modp)，则显然

(4)x2=p−x1≡−x1(modp)  
也是 x2≡a(modp) 的解，此外若还有其他解 x′2≡a(modp)，则
(5)x2≡a(modp),x′2≡a(modp) ,
这就指出，
(6)x2−x′2=(x+x′)(x−x′)≡a−a=0(modp) ,
从而 (x+x′)≡0(modp) 或 (x−x′)≡0(modp)，这就指出了仅有 x1 与 p−x1 两个代表对应的模 p 的剩余类是解。这就指出，仅有 x1 与 p−x1 的伴随数是自己。

　　 此时可以立刻得出，各数 1,2,…,(p−1) 可以分成 x1,p−x1 以及 (p−3)/2 对不相等的伴随数对1，其中

(7)x1(p−x1)≡−x12≡−a(modp) ,
而对任意一对伴随数 x,x′ 都有 xx′≡a(modp)，故
(8)(p−1)!=∏x≡−a⋅a(p−3)/2≡−a(p−1)/2(modp) .
可以发现当 aRp 时，原定理成立。

　　 若 aNp，则 x2≡a(modp) 无解，故各数 1,2,…,(p−1) 可以分成 (p−1)/2 对不相等的伴随数对2，从而

(9)(p−1)!=∏x≡a(p−1)/2(modp) .
故当 aNp 时，原定理也成立。证毕！

1. ^ 可以证明这些数一定可以配对，可以利用费马小定理或定理 2 证明总可以构造，而由于 1 至 p−1 都与 p 互素，故必定不重复。
2. ^ 一样的，可以证明一定可以两两配对。


致读者： 小时百科一直以来坚持所有内容免费无广告，这导致我们处于严重的亏损状态。 长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。 因此，我们请求广大读者热心打赏 ，使网站得以健康发展。 如果看到这条信息的每位读者能慷慨打赏 20 元，我们一周就能脱离亏损， 并在接下来的一年里向所有读者继续免费提供优质内容。 但遗憾的是只有不到 1% 的读者愿意捐款， 他们的付出帮助了 99% 的读者免费获取知识， 我们在此表示感谢。

                     

友情链接： 超理论坛　|　©小时科技 保留一切权利