课程目录
本页目录
定理 4(二次互反律 / Gauss)
设 p,q 是互不相同的奇素数,则
(qp)(pq)=(−1)2p−1⋅2q−1.
等价地:
(qp)=⎩⎨⎧ (pq)−(pq)若 p≡1(mod4) 或 q≡1(mod4)若 p≡q≡3(mod4)
二次互反律被誉为”数论之钻”。它是计算勒让德符号的核心工具——结合补充律(p−1 和 p2),可以将任意 (pn) 的计算不断”翻转”到更小的模数,直至可以直接判断。
证明(高斯引理法概要)
高斯引理:设 p 是奇素数,gcd(a,p)=1。考虑 2p−1 个数
a, 2a, 3a, …, 2p−1a
将它们模 p 化为最小正剩余,设其中有 m 个大于 2p,则
(pa)=(−1)m
有了高斯引理后,考察 (qp) 和 (pq) 各自的 m 值。通过计算格点数目可得:
(qp)(pq)=(−1)2p−1⋅2q−1□
勒让德符号计算示例
例 1:判断 x2≡14(mod31) 是否有解。
(3114)(312)(317)=(312)(317)=1(∵ 31≡−1(mod8))=(731)(∵ 7≡3, 31≡3(mod4), 两个 3 翻转为 −)=−(731mod7)=−(73)=−(37)=−(31)=−1
故 (3114)=1⋅(−1)=−1,14 是模 31 的二次非剩余,无解。
例 2:判断 x2≡15(mod31) 是否有解。
(3115)(313)(315)=(313)(315)=−(331)=−(31)=−1=(531)=(51)=1
故 (3115)=−1,15 是模 31 的二次非剩余,无解。