初等数论–二次剩余与二次同余方程–二次互反律「建议收藏」

初等数论–二次剩余与二次同余方程–二次互反律「建议收藏」信息安全数学基础–二次剩余与二次同余方程–雅可比符号Jacobisymbol博主是初学信息安全数学基础(整除+同余+原根+群环域),本意是想整理一些较难理解的定理、算法,加深记忆也方便日后查找;如果有错,欢迎指正。…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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)(2p1)(2q1)

证明:高斯引理+巧妙发现规律
上一章证明了高斯引理 ( 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} 2p1个数 : q , 2 q , … … p − 1 2 q :q,2q,……\frac{p-1}{2}q :q,2q,2p1q中有 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α2pαm,β1,β2,βn, p − 1 2 \frac{p-1}{2} 2p1个数,大小在 1 ∼ p − 1 2 1\sim\frac{p-1}{2} 12p1之间,且两两模 p p p不同余。

  • 对于 p − 1 2 \frac{p-1}{2} 2p1个数 : q , 2 q , … … p − 1 2 q , :q,2q,……\frac{p-1}{2}q, :q,2q,2p1q,带余除法 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,0rk<p(这里 [ ] [] []是取下整数的意思)

  • 计算 ∑ k = 1 p − 1 2 k \sum_{k=1}^{\frac{p-1}{2}}k k=12p1k(我个人觉得能想到计算这个是需要一定的数学基础的,还挺难的,我目前也不明白为什么会想到要计算这个,虽然后面可以通过这个找到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=12p1k=i=1m(pαi)+j=1nβj=i=1mpi=1mαi+j=1nβj=mp2i=1mαi+i=1mαi+j=1nβj=mp2i=1mai+k=12p1rk (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,0rk<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=12p1kq=k=12p1[pkq]p+k=12p1rk (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=12p1k(q1)=(k=12p1[pkq]m)p+2i=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=12p1[pkq]

同理, n = ∑ l = 1 q − 1 2 [ l p q ] n=\sum_{l=1}^{\frac{q-1}{2}}[\frac{lp}{q}] n=l=12q1[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=12p1[pkq]+l=12q1[qlp]

这一步计算我觉得也有点难,用图形化来思考这个问题:在这里插入图片描述

  • 整体计算:这个矩形里的整数点共有 ( p − 1 2 ) ⋅ ( q − 1 2 ) (\frac{p-1}{2})·(\frac{q-1}{2}) (2p1)(2q1)
  • 分开上下三角形计算:把变化中的纵坐标 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}, Lxqp,1L2q1, x ≤ L p q , x\le\frac{Lp}{q}, xqLp,点个数一共有 ∑ l = 1 q − 1 2 [ L p q ] \sum_{l=1}^{\frac{q-1}{2}}[\frac{Lp}{q}] l=12q1[qLp]
    下三角形:同理,点个数一共有 ∑ k = 1 p − 1 2 [ k q p ] \sum_{k=1}^{\frac{p-1}{2}}[\frac{kq}{p}] k=12p1[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}] (2p1)(2q1)=k=12p1[pkq]+l=12q1[qLp]

证毕。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/215559.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • platform_driver_register( )过程追踪

    platform_driver_register( )过程追踪以下代码源于linux3.1.9。platform_driver_register()是内核中非常著名的函数。platform_driver_register()负责注册平台驱动程序,如果在内核中找到了使用驱动程序的设备,调用probe()。刨去参数检查、错误处理,platform_driver_register的主要过程如下:。。。{。。。retur…

  • POJ 3159 Candies(SPFA+栈)差分约束[通俗易懂]

    POJ 3159 Candies(SPFA+栈)差分约束

  • 电脑蓝屏0X000000ED_0X000000ED

    电脑蓝屏0X000000ED_0X000000ED说到电脑问题,就不得不提蓝屏的问题。最近有位朋友的电脑开机的时候,并没有进入正常的启动程序,反而进入了蓝色界面,显示代码0x000000ed,不知道为什么会这样,也不知道如何去解决。下面就来看看蓝屏0x000000ed的原因和解决方法详解吧!蓝屏代码0x000000ed的原因详解!蓝屏现象,是我们在使用电脑中最常见的一种启动问题,而蓝屏显示的代码就是帮助我们去了解蓝屏的原因以及解决方法的主要依据。…

  • 微信公众号高质量技术贴-提炼总结

    微信公众号高质量技术贴-提炼总结微信公众号高质量技术贴过滤掉对自己感觉没有技术相关性的,或者是那种水贴对内容进行归类整理阅读完写下自己的读后感LINUX从无盘启动看Linux启动原理“只读内存”(ROM)—-“基本输入输出系统”(BIOS)—-“硬件自检”(POST)—-“启动顺序”(BootSequence)上电自检—-UEFI固件被加载—-加载UEFI应用—-启动内核及initramfs/sbin/init—-/etc/inittab—-etc/rcN.dLi

  • ubuntu性能优化_ubuntu系统安装教程

    ubuntu性能优化_ubuntu系统安装教程有两个工具可以帮助减少电脑过热问题,提升系统性能。特别是比较慢的笔记本。TLP开始后自动在后台运行。sudoadd-apt-repositoryppa:linrunner/tlpsudoapt-getupdatesudoapt-getinstalltlptlp-rdwsudotlpstartindicator-cpufreqsudoapt-getinstallindi

  • acwing-2326. 王者之剑(最小割之最大点权独立集)「建议收藏」

    acwing-2326. 王者之剑(最小割之最大点权独立集)「建议收藏」给出一个 n×m 网格,每个格子上有一个价值 vi,j 的宝石。Amber 可以自己决定起点,开始时刻为第 0 秒。以下操作,在每秒内按顺序执行。若第 i 秒开始时,Amber 在 (x,y),则 Amber 可以拿走 (x,y) 上的宝石。在偶数秒时(i 为偶数),则 Amber 周围 4 格的宝石将会消失。若第 i 秒开始时,Amber 在 (x,y),则在第 (i+1) 秒开始前,Amber 可以马上移动到相邻的格子 (x+1,y),(x−1,y),(x,y+1),(x,y−1) 或原地不动

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号