二次互反律的证明

✍ dations ◷ 2025-03-04 13:24:11 #自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 }}

相关

  • 恋童癖恋童是一种精神障碍,16岁以上的青少年或者成年人患者会认为青春期前的儿童拥有主要的性吸引力,或只有儿童才有性吸引力。虽然在10-12岁(女孩:10-11岁;男孩:11岁-12岁)之间儿童会开
  • 肾脏疾病肾病变、肾脏病(英语:Nephropathy、kidney disease、renal disease),又称肾损伤,指肾脏的疾病或是功能损伤。又分成非发炎性的肾病(英语:Nephrosis),以及发炎性的肾炎(英语:Nephritis)。
  • 乙部,是为汉字索引中的部首之一,康熙字典214个部首中的第五个(一划的则为第五个)。就正体中文中,乙部归于一划部首。而简体部首称“乛部”,而乙为‘乛部’的附形部首。乙部通常从
  • Usub2/sub(SOsub4/sub)sub3/sub硫酸铀(III)是三价铀的硫酸盐,化学式为U2(SO4)3,具有放射性。它是第一个被发现的水合的三价铀盐。硫酸铀(III)于1967年被R. Barnard等人报道,通过硫酸铀酰的电化学还原法制备,向
  • 吴 淇吴淇,字伯其,睢州人,清朝政治人物。顺治十五年(1658年)戊戌进士,官至江苏镇江府同知。工诗,有《雨蕉斋诗集》。
  • 达达尼尔达达尼尔(Dardanelle)是美国阿肯色州耶尔县的一座城市,人口约4000人(2000年)。
  • 不让任何孩子落后法案有教无类法案(No Child Left Behind Act of 2001,Public Law 107-110),又译为不让任何孩子落后法案,简称为NCLB,是2002年1月8日由美国总统乔治·沃克·布希签署的一项美国联邦法律
  • 中美 (政治地理学)中美(英语:Middle America,法语:L'Amérique moyen)是一个政治地理学中的地理名词,它表示的是美洲的中部地区。它位于北美洲的南半部分,包括墨西哥、中美洲和加勒比地区三部分。按
  • 爱德华·铁钦纳爱德华·布拉德福德·铁钦纳(英语:Edward Bradford Titchener,1867年-1927年),英国籍美国心理学家,为二十世纪初期五大心理学派中的结构学派领导者,修正过威廉·冯特的感情三维论。
  • 松山庄松山庄(日语:松山庄/まつやましょう ),为1920-1938年间存在之行政区,辖属台北州七星郡。1938年4月1日废庄并入台北市。大致为今日台北市松山区及信义区,少部分位于大安区、中山区、