增乘法在算法优化中的作用

Treenewbee

蔡家雄 发表于 2024-4-27 17:29
求：1, 9, 89, 881, ... 的通解公式，

\[a_n=\left\lceil \frac{1}{6} \left(3-\sqrt{6}\right) \left(2 \sqrt{6}+5\right)^n\right\rceil\]

ysr

，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，

ysr

蔡家雄 发表于 2025-7-27 12:48
求 \(x^2 - 2*13*y^2= -23\) 的正整数解，，

请输入一个数字：100000000
x= 9 y= 2
x= 61 y= 12
x= 979 y= 192
x= 6231 y= 1222
x= 99849 y= 19582
x= 635501 y= 124632
x= 10183619 y= 1997172
x= 64814871 y= 12711242
请输入一个数字：

ysr

蔡家雄 发表于 2025-7-27 12:48
求 \(x^2 - 2*13*y^2= 23\) 的正整数解，，

   
请输入一个数字：100000000
x= 7 y= 1
x= 97 y= 19
x= 617 y= 121
x= 9887 y= 1939
x= 62927 y= 12341
x= 1008377 y= 197759
x= 6417937 y= 1258661
请输入一个数字：

蔡家雄

平方剩余奇质数问题

设 \(4d+1\) 是奇质数，且 \(4d+1\) 不为 \(1+4^r*(2t+1)^2\) ，

设 \(n^2\)  \(mod\)  \((4d+1)=\)  \(p\) 是奇质数，

若 \(2*(4d+1)*k -p\) 是质数 或 \(2*(4d+1)*k+p\) 是质数，

则 \(x^2 - (4d+1)*y^2= ±p\) 必有正整数解，，

则 \(x^2 - (4d+1)*y^2= ±(2*(4d+1)*k -p)\) 必有正整数解，，

则 \(x^2 - (4d+1)*y^2= ±(2*(4d+1)*k+p)\) 必有正整数解，，



模 17 的平方剩余奇质数 p= 13 .

模 29 的平方剩余奇质数 p= 5, 7, 13, 23 .

模 41 的平方剩余奇质数 p= 5, 23, 31, 37 .

模 53 的平方剩余奇质数 p= 7, 11, 13, 17, 29, 37, 43, 47 .

模 61 的平方剩余奇质数 p= 3, 5, 13, 19, 41, 47 .

模 73 的平方剩余奇质数 p= 3, 19, 23, 37, 41, 61, 67, 71 .

模 89 的平方剩余奇质数 p= 5, 11, 17, 47, 53, 67, 71, 73, 79 .

模 97 的平方剩余奇质数 p= 3, 11, 31, 43, 47, 53, 61, 73, 79, 89 .



设 奇质数 D＝a^2＋4^r*(2t+1)^2，且 a 与 (2t+1) 都是 >=3 的奇数，

则 素数模 D 的平方剩余奇质数，必 含有奇数 a 与 (2t+1) 的素因子，，，

蔡家雄

设 D=1328910909092970836741990520764198285631252318308342346576156667496920489，

=((3*5*7*11*13*17*19*23*29*31*37*41*43*47*53*59*61*67*71*73*79*83*89*97)^2+4^3*151^2) 是质数，

则 素数模 D 的平方剩余奇质数，必 含有奇数 a 与 (2t+1) 的素因子，，，

则 素数模 D 的平方剩余奇质数，

必 含有 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 151,


设 D=85050298181950133551487393328908690280400148371733910180874026719709570841，

=(229^2+4^3*(3*5*7*11*13*17*19*23*29*31*37*41*43*47*53*59*61*67*71*73*79*83*89*97)^2) 是质数，

则 素数模 D 的平方剩余奇质数，必 含有奇数 a 与 (2t+1) 的素因子，，，

则 素数模 D 的平方剩余奇质数，

必 含有 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 229,

朱明君

蔡家雄 发表于 2025-8-24 00:58
设 D=1328910909092970836741990520764198285631252318308342346576156667496920489，

=((3*5*7*11*13*1 ...

你提出的核心结论是：当素数  D  具有特定的“平方项 + 常数项”结构时（如  D = M^2 + C ，其中  M  是多个小素数的乘积或单个素数， C  是固定形式的常数），所有模  D  的平方剩余奇素数，必包含  M  和  C  分解式中的全部奇素因子（即你列出的 3,5,...,97 及 151/229）。以下从“核心逻辑验证”和“数论原理关联”两方面拆解，明确其合理性与关键前提：

一、核心结论的逻辑验证（以两个  D  为例）

先明确两个  D  的结构本质，再验证“平方剩余必含指定素因子”的推导基础：

1. 第一个素数  D_1

- 结构拆解： D_1 = M_1^2 + C_1 ，其中
M_1 = 3×5×7×…×97 （24个连续奇素数的乘积，记为“小素数乘积项”），
C_1 = 4^3×151^2 = 64×151^2 （仅含素因子 2 和 151，151 为新增奇素数）。
- 关键关联：对  M_1  中的任意一个奇素数  p （如 3,5,...,97），由  D_1 = M_1^2 + C_1  可得：
D_1 ≡ 0^2 + C_1 \pmod{p} （因  M_1  是  p  的倍数， M_1^2 ≡ 0 \pmod{p} ），即  C_1 ≡ D_1 \pmod{p} 。
两边同乘  C_1^{-1} （ C_1  与  p  互素，逆元存在），得  1 ≡ D_1×C_1^{-1} \pmod{p} ，即  C_1^{-1} ≡ D_1^{-1} \pmod{p} 。
进一步， p  满足  p ≡ p×1 ≡ p×D_1×D_1^{-1} ≡ p×D_1×C_1^{-1} \pmod{D_1} ，结合  D_1  是素数，可推导  p  是模  D_1  的平方剩余（核心是  p  与  D_1  互素，且通过  D_1  的结构建立了平方剩余关系）。
同理，对  C_1  中的奇素数 151，由  D_1 = M_1^2 + 64×151^2  可得  D_1 ≡ M_1^2 \pmod{151} ，即  M_1^2 ≡ D_1 \pmod{151} ，两边同乘  M_1^{-2}  得  1 ≡ D_1×M_1^{-2} \pmod{151} ，进而推导 151 是模  D_1  的平方剩余。

2. 第二个素数  D_2

- 结构拆解： D_2 = M_2^2 + C_2 ，其中
M_2 = 229 （单个奇素数），
C_2 = 4^3×M_1^2 = 64×(3×5×…×97)^2 （含素因子 2 和  M_1  的全部奇素因子）。
- 关键关联：与  D_1  对称，对  M_2 = 229 ，由  D_2 = 229^2 + C_2  得  D_2 ≡ C_2 \pmod{229} ，进而推导 229 是模  D_2  的平方剩余；对  C_2  中的任意小素数  p （3,5,...,97），由  D_2 ≡ 229^2 \pmod{p}  得  229^2 ≡ D_2 \pmod{p} ，进而推导这些小素数是模  D_2  的平方剩余。

二、关联的数论核心原理：平方剩余的欧拉判别法与互素性

你的结论本质是基于平方剩余的基本性质和  D  的特殊结构，核心原理可归纳为两点：

1. 欧拉判别法（平方剩余的判定依据）
对素数  D  和与  D  互素的整数  a ， a  是模  D  的平方剩余，当且仅当  a^{\frac{D-1}{2}} ≡ 1 \pmod{D} 。
你的推导中， D  的结构（ M^2 + C ）恰好能让指定素数  p （如 3,5,...,97、151、229）满足“ p  与  D  互素”（因  D  是素数且大于所有这些  p ，故互素），且通过  D ≡ k^2 \pmod{p} （ k  是  M  或 151/229 相关项）的关系，间接满足欧拉判别法的条件，从而判定  p  是模  D  的平方剩余。
2. “结构决定剩余”的特殊性
你的  D  并非任意素数，而是刻意构造为“某平方项 + 含指定素因子的平方项”——这种结构保证了：对构造中用到的每一个奇素数  p ， D  要么是  p  的“平方剩余”（即存在整数  k  使  k^2 ≡ D \pmod{p} ），要么  D  与  p  的倍数相关，最终通过“互素性 + 同余变形”，反向推导  p  是  D  的平方剩余。

三、结论的关键前提（需明确的边界条件）

你的结论成立需满足一个核心前提： D  必须是素数，且构造  D  时用到的所有奇素数  p  都小于  D （保证  p  与  D  互素，否则若  p=D ，则  p  模  D  为 0，不属于“平方剩余奇素数”范畴）。
从你给出的  D_1  和  D_2  来看，两者均满足“素数”和“指定  p < D ”的前提，因此推导的“模  D  的平方剩余奇素数必含这些  p ”是合理的。

简言之，你的结论是**“特殊结构素数  D  的平方剩余，必包含其构造中用到的全部奇素因子”**，这一结论基于平方剩余的欧拉判别法和  D  的“平方项 + 含指定素因子平方项”结构，在  D  为素数且指定素因子小于  D  的前提下，推导逻辑是自洽的。

朱容仟

L4=18817=(2^5 -1)(2^5*19 -1)=31*607 = 两个梅森质数的乘积
607不是梅森素数

朱容仟

蔡家雄 发表于 2020-8-4 00:22
存在无穷个 x^2,  满足

从2开始，前 x^2 个连续素数的和，仍是素数！

2+3+5+7+11+13+17+19+23=100，3^2=9个连续素数和为100

蔡家雄

yangchuanju 发表于 2026-1-10 05:49
质疑：
蔡老师好！
已证：127 和 7897466719774591 都是素数，
已证：2^127 -1 是素数，据此 7897466719774591 是梅森素数，

众所周知，2^127-1是梅森素数，2^31-1=2147483647、2^61-1=2305843009213693951，
素数 7897466719774591 大于8号梅森素数2^31-1，小于9号梅森素数2^61-1，7897466719774591 怎么会是梅森素数呢？

答：素数 521 大于梅森素数2^7-1，小于梅森素数2^13-1，521 怎么会是梅森素数呢？
即：2^521-1 是素数，2^7897466719774591-1 是素数。