大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全家桶1年46，售后保障稳定
初等数论–二次剩余与二次同余方程–二次互反律
博主是初学初等数论（整除+同余+原根），本意是想整理一些较难理解的定理、算法，加深记忆也方便日后查找；如果有错，欢迎指正。
我整理成一个系列：初等数论，方便检索。
- 设 p , q p,q p,q是两个不同的奇素数，则 ( q p ) ( p q ) = ( − 1 ) ( p − 1 2 ) ⋅ ( q − 1 2 ) (\frac{q}{p})(\frac{p}{q})=(-1)^{(\frac{p-1}{2})·(\frac{q-1}{2})} (pq)(qp)=(−1)(2p−1)⋅(2q−1)
证明：高斯引理+巧妙发现规律
上一章证明了高斯引理 ( a p ) = ( − 1 ) m (\frac{a}{p})=(-1)^m (pa)=(−1)m，同理，我们考虑 ( q p ) = ( − 1 ) m , (\frac{q}{p})=(-1)^m, (pq)=(−1)m,即 p − 1 2 \frac{p-1}{2} 2p−1个数 : q , 2 q , … … p − 1 2 q :q,2q,……\frac{p-1}{2}q :q,2q,……2p−1q中有 m m m个最小正因数 > p 2 , >\frac{p}{2}, >2p,我们假设这 m m m个 > p 2 >\frac{p}{2} >2p的最小正因数分别为: α 1 , α 2 , … … α m , < p 2 \alpha_1,\alpha_2,……\alpha_m,<\frac{p}{2} α1,α2,……αm,<2p的最小正因数为: β 1 , β 2 , … … β n , \beta_1,\beta_2,……\beta_n, β1,β2,……βn,上一章我们已经证过 p − α 1 , p − α 2 … … p − α m , β 1 , β 2 , … … β n , p-\alpha_1,p-\alpha_2……p-\alpha_m,\beta_1,\beta_2,……\beta_n, p−α1,p−α2……p−αm,β1,β2,……βn,共 p − 1 2 \frac{p-1}{2} 2p−1个数，大小在 1 ∼ p − 1 2 1\sim\frac{p-1}{2} 1∼2p−1之间，且两两模 p p p不同余。
-
对于 p − 1 2 \frac{p-1}{2} 2p−1个数 : q , 2 q , … … p − 1 2 q , :q,2q,……\frac{p-1}{2}q, :q,2q,……2p−1q,有带余除法： k q = [ k q p ] ⋅ p + r k , 0 ≤ r k < p 。 kq=[\frac{kq}{p}]·p+r_k,0\le r_k<p。 kq=[pkq]⋅p+rk,0≤rk<p。(这里 [ ] [] []是取下整数的意思)
-
计算 ∑ k = 1 p − 1 2 k \sum_{k=1}^{\frac{p-1}{2}}k ∑k=12p−1k(我个人觉得能想到计算这个是需要一定的数学基础的，还挺难的，我目前也不明白为什么会想到要计算这个，虽然后面可以通过这个找到m的某种表达形式，但是在这一步真的想不明白)
∑ k = 1 p − 1 2 k = ∑ i = 1 m ( p − α i ) + ∑ j = 1 n β j = ∑ i = 1 m p − ∑ i = 1 m α i + ∑ j = 1 n β j = m p − 2 ∑ i = 1 m α i + ∑ i = 1 m α i + ∑ j = 1 n β j = m p − 2 ∑ i = 1 m a i + ∑ k = 1 p − 1 2 r k \sum_{k=1}^{\frac{p-1}{2}}k\\ =\sum_{i=1}^{m}(p-\alpha_i)+\sum_{j=1}^{n}\beta_j\\=\sum_{i=1}^{m}p-\sum_{i=1}^{m}\alpha_i+\sum_{j=1}^{n}\beta_j\\=mp-2\sum_{i=1}^{m}\alpha_i+\sum_{i=1}^{m}\alpha_i+\sum_{j=1}^{n}\beta_j\\=mp-2\sum_{i=1}^{m}a_i+\sum_{k=1}^{\frac{p-1}{2}}r_k ∑k=12p−1k=∑i=1m(p−αi)+∑j=1nβj=∑i=1mp−∑i=1mαi+∑j=1nβj=mp−2∑i=1mαi+∑i=1mαi+∑j=1nβj=mp−2∑i=1mai+∑k=12p−1rk (1)
-
乘以 q q q，计算带余除法 k q = [ k q p ] ⋅ p + r k , 0 ≤ r k < p 。 kq=[\frac{kq}{p}]·p+r_k,0\le r_k<p。 kq=[pkq]⋅p+rk,0≤rk<p。
∑ k = 1 p − 1 2 k ⋅ q = ∑ k = 1 p − 1 2 [ k q p ] ⋅ p + ∑ k = 1 p − 1 2 r k \sum_{k=1}^{\frac{p-1}{2}}k·q\\=\sum_{k=1}^{\frac{p-1}{2}}[\frac{kq}{p}]·p+\sum_{k=1}^{\frac{p-1}{2}}r_k ∑k=12p−1k⋅q=∑k=12p−1[pkq]⋅p+∑k=12p−1rk (2) -
(2)-(1)：
∑ k = 1 p − 1 2 k ⋅ ( q − 1 ) = ( ∑ k = 1 p − 1 2 [ k q p ] − m ) ⋅ p + 2 ∑ i = 1 m a i \sum_{k=1}^{\frac{p-1}{2}}k·(q-1)=(\sum_{k=1}^{\frac{p-1}{2}}[\frac{kq}{p}]-m)·p+2\sum_{i=1}^{m}a_i ∑k=12p−1k⋅(q−1)=(∑k=12p−1[pkq]−m)⋅p+2∑i=1mai -
同时mod 2:(这一步也挺神奇的)
m = ∑ k = 1 p − 1 2 [ k q p ] m=\sum_{k=1}^{\frac{p-1}{2}}[\frac{kq}{p}] m=∑k=12p−1[pkq]
同理， n = ∑ l = 1 q − 1 2 [ l p q ] n=\sum_{l=1}^{\frac{q-1}{2}}[\frac{lp}{q}] n=∑l=12q−1[qlp]
- 我们要计算的 ( q p ) ( p q ) = ( − 1 ) m ⋅ ( − 1 ) n = ( − 1 ) m + n , (\frac{q}{p})(\frac{p}{q})=(-1)^m·(-1)^n=(-1)^{m+n}, (pq)(qp)=(−1)m⋅(−1)n=(−1)m+n,即我们现在要计算的是 m + n = ∑ k = 1 p − 1 2 [ k q p ] + ∑ l = 1 q − 1 2 [ l p q ] m+n=\sum_{k=1}^{\frac{p-1}{2}}[\frac{kq}{p}]+\sum_{l=1}^{\frac{q-1}{2}}[\frac{lp}{q}] m+n=∑k=12p−1[pkq]+∑l=12q−1[qlp]
这一步计算我觉得也有点难，用图形化来思考这个问题：
- 整体计算：这个矩形里的整数点共有 ( p − 1 2 ) ⋅ ( q − 1 2 ) (\frac{p-1}{2})·(\frac{q-1}{2}) (2p−1)⋅(2q−1)个
- 分开上下三角形计算：把变化中的纵坐标 y y y用 L L L表示：
上三角形： x L ≤ p q , 1 ≤ L ≤ q − 1 2 , \frac{x}{L}\le\frac{p}{q},1\le L\le \frac{q-1}{2}, Lx≤qp,1≤L≤2q−1,即 x ≤ L p q , x\le\frac{Lp}{q}, x≤qLp,点个数一共有 ∑ l = 1 q − 1 2 [ L p q ] \sum_{l=1}^{\frac{q-1}{2}}[\frac{Lp}{q}] ∑l=12q−1[qLp]
下三角形：同理，点个数一共有 ∑ k = 1 p − 1 2 [ k q p ] \sum_{k=1}^{\frac{p-1}{2}}[\frac{kq}{p}] ∑k=12p−1[pkq] - 即 ( p − 1 2 ) ⋅ ( q − 1 2 ) = ∑ k = 1 p − 1 2 [ k q p ] + ∑ l = 1 q − 1 2 [ L p q ] (\frac{p-1}{2})·(\frac{q-1}{2})=\sum_{k=1}^{\frac{p-1}{2}}[\frac{kq}{p}]+\sum_{l=1}^{\frac{q-1}{2}}[\frac{Lp}{q}] (2p−1)⋅(2q−1)=∑k=12p−1[pkq]+∑l=12q−1[qLp]
证毕。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/215559.html原文链接：https://javaforall.net
