虚心请教一个小问题！

fsleo

通过：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 这个数，有多少个数是满足条件的。

mathe

这是一个数论问题，首先我们讨论$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}$

mathe

对于$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)
。。。

中国剩余定理的计算需要使用广义辗转相除法

数论爱好者

这个用数学软件去解,太快,秒杀

fsleo

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  ...

感谢，我好好学习和理解一下！

fsleo

数论爱好者 发表于 2021-8-21 10:31
这个用数学软件去解,太快,秒杀

这数学软件叫什么名字?

数论爱好者

这是一个老软件,本论坛有人提起过,和另外两大软件功能差不多,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

fsleo

数论爱好者 发表于 2021-8-21 14:23
这是一个老软件,本论坛有人提起过,和另外两大软件功能差不多,matlab,mathematica
https://bbs.emath.ac.cn ...

非常感谢，下载一个试试。

wayne

https://oi-wiki.org/math/number-theory/quad-residue/
模二次剩余的Cipolla 算法  和 Tonelli-Shanks 算法

fsleo

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为例，手动计算一下过程，我这方面的知识比差，感谢