二次互反律的证明

✍ dations ◷ 2025-06-06 07:12:42 #自2019年12月需要数学专家关注的页面

这个条目给出了二次互反律的证明。

对于两个奇素数 p , q {\displaystyle p,q} ( p q ) ( q p ) = ( 1 ) ( p 1 ) ( q 1 ) 4 {\displaystyle \left({\frac {p}{q}}\right)\cdot \left({\frac {q}{p}}\right)=(-1)^{\frac {(p-1)(q-1)}{4}}} 。其中, ( p q ) {\displaystyle \left({\frac {p}{q}}\right)} 是勒让德符号。

p {\displaystyle p} 是一个奇素数并且 a 0 mod p {\displaystyle a\not \equiv 0\mod p} 。对于每个 k = 1 , 2 , . . . , p 1 2 {\displaystyle k=1,2,...,{\frac {p-1}{2}}} ,这样定义 ϵ k {\displaystyle \epsilon _{k}} r k {\displaystyle r_{k}}

a k ϵ k r k mod p {\displaystyle ak\equiv \epsilon _{k}r_{k}\mod p} ,其中 0 < r k < p 2 {\displaystyle 0<r_{k}<{\frac {p}{2}}} ϵ k = ± 1 {\displaystyle \epsilon _{k}=\pm 1} 。通过分别考虑 ϵ k = 1 {\displaystyle \epsilon _{k}=1} ϵ k = 1 {\displaystyle \epsilon _{k}=-1} 的情况,易证每个 r k {\displaystyle r_{k}} 都两两不等。

现在考虑 k = 1 ( p 1 ) / 2 a k k = 1 ( p 1 ) / 2 ϵ k k = 1 ( p 1 ) / 2 r k mod p {\displaystyle \prod _{k=1}^{(p-1)/2}ak\equiv \prod _{k=1}^{(p-1)/2}\epsilon _{k}\prod _{k=1}^{(p-1)/2}r_{k}\mod p} 。因为每个 r k {\displaystyle r_{k}} 都两两不等,所以 { r 1 , r 2 , . . . , r p 1 2 } {\displaystyle \{r_{1},r_{2},...,r_{\frac {p-1}{2}}\}} 就是 { 1 , 2 , . . . , p 1 2 } {\displaystyle \{1,2,...,{\frac {p-1}{2}}\}} 的一个重排列。所以我们得到 a p 1 2 k = 1 ( p 1 ) / 2 k k = 1 ( p 1 ) / 2 ϵ k k = 1 ( p 1 ) / 2 k mod p {\displaystyle a^{\frac {p-1}{2}}\prod _{k=1}^{(p-1)/2}k\equiv \prod _{k=1}^{(p-1)/2}\epsilon _{k}\prod _{k=1}^{(p-1)/2}k\mod p} ,因此 a p 1 2 k = 1 ( p 1 ) / 2 ϵ k mod p {\displaystyle a^{\frac {p-1}{2}}\equiv \prod _{k=1}^{(p-1)/2}\epsilon _{k}\mod p}

现在考虑 ϵ k {\displaystyle \epsilon _{k}} 的正负情况。 a k ϵ k r k mod p {\displaystyle ak\equiv \epsilon _{k}r_{k}\mod p} 等价于 a k = ϵ k r k + b p , b Z {\displaystyle ak=\epsilon _{k}r_{k}+bp,b\in \mathbb {Z} } 。若 ϵ k = 1 {\displaystyle \epsilon _{k}=1} ,则有 a k = r k + b p {\displaystyle ak=r_{k}+bp} 。注意到 0 < r k < p 2 {\displaystyle 0<r_{k}<{\frac {p}{2}}} ,将等式两边同时乘2得到 2 a k = R k + B k p {\displaystyle 2ak=R_{k}+B_{k}p} ,其中 R k = 2 r k , 0 < R k < p , B k = 2 b {\displaystyle R_{k}=2r_{k},0<R_{k}<p,B_{k}=2b} ,可以发现 B k {\displaystyle B_{k}} 是偶数,而 2 a k p = R k p + B k = B k {\displaystyle \lfloor {\frac {2ak}{p}}\rfloor =\lfloor {\frac {R_{k}}{p}}+B_{k}\rfloor =B_{k}} 也是偶数。同理可证若 ϵ k = 1 {\displaystyle \epsilon _{k}=-1} B k = 2 b + 1 {\displaystyle B_{k}=2b+1} ,而 2 a k p {\displaystyle \lfloor {\frac {2ak}{p}}\rfloor } 是奇数。据此,可以知道 sgn ( r k ) = 2 a k p {\displaystyle \operatorname {sgn}(r_{k})=\lfloor {\frac {2ak}{p}}\rfloor } ,其中 sgn ( r k ) {\displaystyle \operatorname {sgn}(r_{k})} r k {\displaystyle r_{k}} 的符号,也就是 ϵ k = 1 {\displaystyle \epsilon _{k}=1} 还是 ϵ k = 1 {\displaystyle \epsilon _{k}=-1}

所以 a p 1 2 ( 1 ) k = 1 ( p 1 ) / 2 2 a k / p mod p {\displaystyle a^{\frac {p-1}{2}}\equiv (-1)^{\sum _{k=1}^{(p-1)/2}\lfloor 2ak/p\rfloor }\mod p} 。又由欧拉准则知 ( a p ) a p 1 2 mod p {\displaystyle \left({\frac {a}{p}}\right)\equiv a^{\frac {p-1}{2}}\mod p} ,所以 ( a p ) = ( 1 ) k = 1 ( p 1 ) / 2 2 a k / p {\displaystyle \left({\frac {a}{p}}\right)=(-1)^{\sum _{k=1}^{(p-1)/2}\lfloor 2ak/p\rfloor }}

如果 a {\displaystyle a} 是奇数,同时考虑勒让德符号的性质 ( a p ) ( b p ) = ( a b p ) {\displaystyle \left({\frac {a}{p}}\right)\left({\frac {b}{p}}\right)=\left({\frac {ab}{p}}\right)} ,可知 ( a p ) ( 2 p ) = ( 2 a + 2 p p ) = ( 4 ( a + p 2 ) p ) = ( 1 ) k = 1 ( p 1 ) / 2 2 ( a + p 2 ) k p = ( 1 ) k = 1 ( p 1 ) / 2 a k p ( 1 ) k = 1 ( p 1 ) / 2 k = ( 1 ) k = 1 ( p 1 ) / 2 a k p ( 1 ) p 2 1 8 {\displaystyle \left({\frac {a}{p}}\right)\left({\frac {2}{p}}\right)=\left({\frac {2a+2p}{p}}\right)=\left({\frac {4\left({\frac {a+p}{2}}\right)}{p}}\right)=(-1)^{\sum _{k=1}^{(p-1)/2}\lfloor {\frac {2\left({\frac {a+p}{2}}\right)k}{p}}\rfloor }=(-1)^{\sum _{k=1}^{(p-1)/2}\lfloor {\frac {ak}{p}}\rfloor }(-1)^{\sum _{k=1}^{(p-1)/2}k}=(-1)^{\sum _{k=1}^{(p-1)/2}\lfloor {\frac {ak}{p}}\rfloor }(-1)^{\frac {p^{2}-1}{8}}} ,其中最后一步利用了等差数列的求和公式。

但是,当 a = 1 {\displaystyle a=1} 时,由上式可得 ( 2 p ) = ( 1 p ) ( 2 p ) = ( 1 ) k = 1 ( p 1 ) / 2 k p ( 1 ) p 2 1 8 = ( 1 ) p 2 1 8 {\displaystyle \left({\frac {2}{p}}\right)=\left({\frac {1}{p}}\right)\left({\frac {2}{p}}\right)=(-1)^{\sum _{k=1}^{(p-1)/2}\lfloor {\frac {k}{p}}\rfloor }(-1)^{\frac {p^{2}-1}{8}}=(-1)^{\frac {p^{2}-1}{8}}} ,所以 ( a p ) = ( 1 ) k = 1 ( p 1 ) / 2 a k p {\displaystyle \left({\frac {a}{p}}\right)=(-1)^{\sum _{k=1}^{(p-1)/2}\lfloor {\frac {ak}{p}}\rfloor }}

相关

  • 戴克里先戴克里先(244年-312年,拉丁语:Gaius Aurelius Valerius Diocletianus),原名为狄奥克莱斯(Diocles),罗马帝国皇帝,于284年11月20日至305年5月1日在位。其结束罗马帝国的三世纪危机(235年
  • 昭和昭和(日语:昭和/しょうわ Shōwa */?)是日本昭和天皇在位时所使用的年号,使用时间为1926年12月25日至1989年1月7日,是日本各年号中使用时间最长的,合共64年;但由于开始时是年底、
  • 应用心理学异常心理学 行为遗传学 生物心理学 心理药物学 认知心理学 比较心理学 跨文化心理学 文化心理学 差异心理学(英语:Differential psychology) 发展心理学 演化心理学 实验心理学
  • 色氨酸羟化酶色氨酸羟化酶(英语:Tryptophan hydroxylase,EC 1.14.16.4)也称为色氨酸5-单加氧酶,简称TPH,是合成神经递质5-羟色胺的过程中重要的酶。色氨酸羟化酶可催化如下酶促反应:以上反应还
  • 马尔科姆三世马尔科姆·麦克邓肯(中世纪盖尔语:Máel Coluim mac Donnchada,现代盖尔语:Maol Chaluim mac Dhonnchaidh,意为邓肯之子马尔科姆。 ?—1093年11月13日)是苏格兰国王(1058年–1093年1
  • 东京奥运会除特别注明外,本文所有时间均以东九区时间(UTC+9)为准。本条目记叙2019冠状病毒病疫情对第32届夏季奥林匹克运动会的影响。受疫情影响,众多东京奥运会预选赛延期或被取消。2020
  • C38.0/D15.1ICD-10 第二章:肿瘤,为WHO规定的各类已发现的肿瘤。恶性肿瘤(C00-C97)淋巴、造血和有关组织的恶性肿瘤 (C81-C96)原位肿瘤 (D00-D09)良性肿瘤 (D10-D36)动态未定或动态未知的肿瘤(D37
  • 瓶尔小草属见文中瓶尔小草属(学名:Ophioglossum)是一种陆生小型植物。它的名字来源于希腊语。 其直立,根壮茎短,有1-2片营养叶。有柄,通常为单叶,全缘,为披针形或卵形,叶脉网状,网眼内没有内藏
  • 有栖川宫威仁亲王有栖川宫威仁亲王(ありすがわのみや たけひとしんのう、文久2年旧暦1月13日(1862年2月11日) - 大正2年(1913年)7月5日),日本的皇族和军人。祖上是后阳成天皇的第7皇子,被封为高松宫,
  • 斯坦福·摩尔斯坦福·摩尔(Stanford Moore,1913年9月4日-1982年8月23日),美国生物化学家,1972年获诺贝尔化学奖。1901年:范托夫 |1902年:费歇尔 |1903年:阿伦尼乌斯 |1904年:拉姆齐 |1905年:拜尔 |1