数学研发论坛

 找回密码
 欢迎注册
查看: 488|回复: 11

[求助] 虚心请教一个小问题!

[复制链接]
发表于 2021-8-20 19:20:42 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

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

x
通过:x^2 mod n = 1,当指定一个n时,我想求出1~n之间的整数,能满足条件一共有几个,分别是什么,比如,n = 24,可以得到

(1,5,7,11,13,17,19,23)这几个数。我写了一个程序,指定一个n,能快速把满足条件的计算出来。

但是遇到一个问题,比如n很大的时候,太慢了。所以我想研究一下他的规律,我发现 其本上只要找到 1~n/2之间的数就可以了。他们

是有对称性的。这样就快了一半,但是数一大,还是很慢。比如我想计算:n = 62^9 这个数,有多少个数是满足条件的。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-8-21 09:06:20 | 显示全部楼层
这是一个数论问题,首先我们讨论$n=2^k$, 那么
  在k=1时,只有一个解$x -= 1(mod 2)$,
     k=2时,有两个解$x -= 1,3(mod 4)$,
     k=3时, 有四个解$x -= 1,3,5,7(mod 8)$
对于k>3时,也都是四个解,分别为$x -=1, 2^{k-1}-1, 2^{k-1}+1, 2^k-1 (mod 2^k)$。
对于$n=p^k$是奇素数时,有两个解$x -=1,p^k-1(mod p^k)$

对于普通的n,我们需要对其进行因子分解,然后对于每个不同的素数部分分别求解,最后使用中国剩余定理求得关于模n的解。
而解的数目比较容易计算,设$n=2^a p_1^{a_1}...p_t^{a_t}$,
其中$a\ge 0, a_1\gt 0,a_2\gt 0,..., a_t\gt 0, t\ge 0$
那么a=0或1时,解的数目为$2^t$; $a=2$时,解的数目为$2^{t+1}$;$a>2$时,解的数目为$2^{t+2}$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-8-21 09:14:08 | 显示全部楼层
对于$n=62^9=2^9\times 31^9$,根据上面结论有8个解
i) $x -=1 (mod 2^9), x -=1 (mod 31^9)$,得出$ x -=1 (mod n)$
ii) $x -= 1(mod 2^9), x -= -1(mod 31^9)$, 得出
? chinese(Mod(1,2^9),Mod(-1,31^9))
%17 = Mod(11792071483659265, 13537086546263552)
iii) $ x-= 2^8-1 (mod 2^9), x -= 1 (mod 31^9)$, 得出
? chinese(Mod(2^8-1,2^9), Mod(1,31^9))
%18 = Mod(8513558335736063, 13537086546263552)
。。。

中国剩余定理的计算需要使用广义辗转相除法
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-8-21 10:31:43 | 显示全部楼层
这个用数学软件去解,太快,秒杀
平方剩余.GIF
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2021-8-21 12:46:29 | 显示全部楼层
mathe 发表于 2021-8-21 09:14
对于$n=62^9=2^9\times 31^9$,根据上面结论有8个解
i) $x -=1 (mod 2^9), x -=1 (mod 31^9)$,得出$ x -=1  ...

感谢,我好好学习和理解一下!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2021-8-21 12:47:33 | 显示全部楼层
数论爱好者 发表于 2021-8-21 10:31
这个用数学软件去解,太快,秒杀

这数学软件叫什么名字?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-8-21 14:23:40 | 显示全部楼层
本帖最后由 数论爱好者 于 2021-8-21 14:29 编辑

这是一个老软件,本论坛有人提起过,和另外两大软件功能差不多,matlab,mathematica
https://bbs.emath.ac.cn/forum.ph ... amp;highlight=Maple

https://www.maplesoft.com/support/install/maple18_install.html

我的是[Maple.17].Maple17Windows.X64Installer安装包631MB,安装好后,1.8GB
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2021-8-21 19:37:52 | 显示全部楼层
数论爱好者 发表于 2021-8-21 14:23
这是一个老软件,本论坛有人提起过,和另外两大软件功能差不多,matlab,mathematica
https://bbs.emath.ac.cn ...

非常感谢,下载一个试试。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-8-22 10:04:52 | 显示全部楼层
https://oi-wiki.org/math/number-theory/quad-residue/
模二次剩余的Cipolla 算法  和 Tonelli-Shanks 算法
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2021-8-22 14:43:21 | 显示全部楼层
mathe 发表于 2021-8-21 09:06
这是一个数论问题,首先我们讨论$n=2^k$, 那么
  在k=1时,只有一个解$x -= 1(mod 2)$,
     k=2时,有 ...

对于普通的n,我们需要对其进行因子分解,然后对于每个不同的素数部分分别求解,最后使用中国剩余定理求得关于模n的解。
而解的数目比较容易计算,设n=2apa11...patt,
其中a≥0,a1>0,a2>0,...,at>0,t≥0
那么a=0或1时,解的数目为2t; a=2时,解的数目为2t+1;a>2时,解的数目为2t+2

mathe:您好
对于普通的 n 这里还是不太理解。比如您说需对其因子分解,比如n=120,对其因子分解是不是有几种方式?
能以120为例,手动计算一下过程,我这方面的知识比差,感谢
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2021-9-26 14:47 , Processed in 0.086712 second(s), 19 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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