数学中国

 找回密码
 注册
搜索
热搜: 活动 交友 discuz
楼主: 蔡家雄

平方剩余与非剩余定理

[复制链接]
发表于 2020-3-6 12:17 | 显示全部楼层 |阅读模式
本帖最后由 蔡家雄 于 2020-3-22 18:50 编辑

平方剩余定理

设 x为任意正整数,

若 p为4k+1型素数,且 g是素数p的最小原根 ,

设 g^(2n)  mod  p = r(1<=n<=(p-1)/2)

则 y^2=p*x+r 与 y^2=p*x -r 都有整数解。

设 x为任意正整数,

若 p为4k-1型素数,且 g是素数p的最小原根 ,

设 g^(2n)  mod  p = r(1<=n<=(p-1)/2)

则 y^2=p*x+r 都有整数解,但 y^2=p*x -r 都无整数解。


平方非剩余定理

设 x为任意正整数,

若 p为4k+1型素数,且 g是素数p的最小原根 ,

设 g^(2n-1)  mod  p = r(1<=n<=(p-1)/2)

则 y^2=p*x+r 与 y^2=p*x -r 都无整数解。

设 x为任意正整数,

若 p为4k-1型素数,且 g是素数p的最小原根 ,

设 g^(2n-1)  mod  p = r(1<=n<=(p-1)/2)

则 y^2=p*x+r 都无整数解,但 y^2=p*x -r 都有整数解。

 楼主| 发表于 2020-3-6 12:20 | 显示全部楼层
所谓素数模p的原根g, 是指使同余式

g^e  mod  p =1 得以成立的最小指数e必须为p-1 .

若 g是4k+1型素数p的原根,则 (p-g)也是素数p的原根。

若 g是素数p的原根,则 g+p*n 也是素数p的(广义)原根。
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-3-6 12:22 | 显示全部楼层
05的原根g=2,3,

13的原根g=2,6,7,11,

17的原根g=3,5,6,7,10,11,12,14,

29的原根g=2,3,8,10,11,14,15,18,19,21,26,27,

37的原根g=2,5,13,15,17,18,19,20,22,24,32,35,

41的原根g=6,7,11,12,13,15,17,19,22,24,26,28,29,30,34,35,

53的原根g=2,3,5,8,12,14,18,19,20,21,22,26,27,31,32,33,34,35,39,41,45,48,50,51,

61的原根g=2,6,7,10,17,18,26,30,31,35,43,44,51,54,55,59,

73的原根g=5,11,13,14,15,20,26,28,29,31,33,34,39,40,42,44,45,47,53,58,59,60,62,68,

回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-3-6 20:56 | 显示全部楼层
本帖最后由 蔡家雄 于 2020-3-20 17:56 编辑

89的原根g=3,6,7,13,14,15,19,23,24,26,27,28,29,30,31,33,35,38,41,43,46,48,

51,54,56,58,59,60,61,62,63,65,66,70,74,75,76,82,83,86,


97的原根g=5,7,10,13,14,15,17,21,23,26,29,37,38,39,40,41,

56,57,58,59,60,68,71,74,76,80,82,83,84,87,90,92,
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-3-6 21:30 | 显示全部楼层


数学就是他的上帝:Euler 太伟大了!

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册

x
回复 支持 反对

使用道具 举报

发表于 2020-3-9 12:32 | 显示全部楼层
蔡家雄 发表于 2020-3-8 19:07
费尔马1的 3*x^3-7=a^2 无整数解,

可以转化为 3*x -7=a^2 无整数解,

非常感谢蔡老师关注学生的小题,老师的方法还是有些复杂啊!且老师的是观察法(猜想),最好是有一个证明的通法,将这类型的题一网打尽!
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则

Archiver|手机版|小黑屋|数学中国 ( 京ICP备05040119号 )

GMT+8, 2024-3-28 21:32 , Processed in 0.072266 second(s), 16 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表