二次互反律的证明

✍ dations ◷ 2025-03-07 10:32:22 #自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 }}

相关

  • 编码编码是信息从一种形式或格式转换为另一种形式的过程;解码则是编码的逆过程。对于特定的上下文,编码有一些更具体的意义。
  • 核子在化学和物理学里,核子(nucleon)是组成原子核的粒子。每个原子核都拥有至少一个核子,每个原子又是由原子核与围绕原子核的一个或多个电子所组成。核子共有两种:中子和质子。任意
  • 阿瑟·肖洛阿瑟·肖洛(英语:Arthur Schawlow,1921年5月5日-1999年4月28日),出生于纽约州弗农山 ,美国物理学家,1981年获诺贝尔物理学奖。1999年4月28日,逝世于加利福尼亚州帕洛阿尔托。1901年:伦
  • 罗伯特·威廉·本生阿道夫·冯·拜尔 弗里茨·哈伯 菲利普·莱纳德 Georg Ludwig Carius(英语:Georg Ludwig Carius) 阿道夫·威廉·赫尔曼·科尔贝 Adolf Lieben(英语:Adolf Lieben) Carl Friedr
  • 鸟类肝去氧核糖核酸病毒属禽肝病毒属(Avihepadnavirus)又译作鸟类肝去氧核糖核酸病毒属,是肝病毒科的一个属,主要感染对像是鸟类。代表种:
  • 肯特·贝克肯特·贝克(英语:Kent Beck,1961年-),美国著名软件工程师与作家,在软件工程方面有很大的贡献。他是Smalltalk软件的开发者,设计模式的先驱,测试驱动开发的支持者,也是极限编程的创始者
  • 育幼袋育幼袋(英语:pouch,又译育儿囊)是有袋类雌性个体身上的一个特殊构造。“有袋类”一辞源自拉丁文中的marsupium,意思就是“囊袋”。与其他哺乳类相比之下,有袋类的幼仔在发育相当早
  • KOI-1686.01KOI-1686.01是一颗待确认的太阳系外行星候选天体,名称来自开普勒星表(英语:Kepler Object of Interest)(KOI),距离地球约1033.8光年。已在2015年被NASA证实是误报。KOI-1686.01是一
  • 张柏林张柏林(1942年-),辽宁营口人,中华人民共和国政治人物。1972年8月,张柏林加入中国共产党,毕业于吉林大学历史系。曾任渤海造船厂中学教研组长、政治部干部、厂党委秘书;六机部办公厅
  • 福克兰群岛行政长官福克兰群岛行政长官(Chief Executive of the Falkland Islands),为福克兰群岛(马尔维纳斯群岛)的政府首脑。福克兰群岛行政长官的职权由福克兰群岛宪法所规定。阿根廷总统 · 安