二次互反律的证明

✍ dations ◷ 2025-09-07 03:20:16 #自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 }}

相关

  • 造血干细胞移植骨髓移植(学名:hematopoietic stem cell transplantation,缩写:HSCT)是透过静脉注射正常骨髓细胞至白血病或再生不良性贫血等血液难病患者的治疗。骨髓移植所使用的造血干细胞,除
  • Hsub2/subCrOsub4/sub铬酸,化学式为H2CrO4,是三氧化铬溶于硫酸以及铬酸盐/重铬酸盐酸化时生成的化合物之一。重铬酸是二分子铬酸脱水形成的多酸,化学式为H2Cr2O7。三氧化铬是铬酸的酸酐,室温下为橘红
  • 李廷栋李廷栋(1930年10月7日-),中国地质学家。出生于河北栾城。1950年考入北京大学地质系,1953年毕业于北京地质学院。1993年当选为中国科学院院士。中国科学院学部主席团成员,国土资源
  • 膜攻击复合物膜攻击复合物(MAC),是一种通常生成于致病细菌表面的结构。人体补体系统的替代补体途径、经典补体途径、凝集素途径均可产生这种复合物。该复合物是免疫系统的效应蛋白之一,它可
  • 开普勒186f开普勒186f(英语:Kepler-186f)是一颗环绕红矮星开普勒186的太阳系外行星,距离地球约492光年。该行星是第一颗在太阳以外恒星旁发现的适居带内半径与地球相若的系外行星。NASA 的
  • 重复基因重复或称复制基因(英语:Gene duplication (or chromosomal duplication or gene amplification))是指含有基因的DNA片段发生重复,可能因同源重组作用出错而发生,或是因为反转
  • 塔巴萨兰人塔巴萨兰人(俄语:Табасараны)是俄罗斯联邦达吉斯坦共和国境内的一个民族,2002年人口约13.2万。其语言塔巴萨兰语属于东北高加索语系。主要信仰逊尼派伊斯兰教。
  • 南开大学出版社有限公司南开大学出版社是位于中国天津市的出版社,是隶属于南开大学的大学出版社。南开大学出版社初创于1929年,1936年10月日军侵略华北时停办。1983年,经中华人民共和国国家教育委员会
  • 足底筋膜炎足底筋膜炎(英语:Plantar fasciitis),又称跑者足(英语:jogger's heel),是一种发生在支撑足弓的结缔组织著骨点(肌腱和韧带附着于骨头处)病变。患者会有脚跟或脚底疼痛,每天起床或是休息
  • 100米赛跑100米是最短的奥运户外田径短跑项目。奥林匹克100米冠军通常被称为“世界上最快的男人/女人”,大部分短跑选手100米平均速率比200米更快一些。过去,运动员通常进行100码赛跑比