二元一次方程判断梅森素数

太阳

\(例2:方程\left( 71x+1\right)\times\left( 72y+1\right)-2^{71}-1＝0\)
\(试除法，y＞x，找到一组正整数解\begin{cases}
x=2998392\\
y＝156215665098
\end{cases}，素数71\times2998392+1\)
按照这样方法找到1亿位大素数

太阳

\(方程:\left( ax+1\right)\times\left( ay+1\right)-\frac{2^a-1}{2}＝0，\left( 素数a＞0，未知数x和y\right)\)
\(如果方程有n组正整数解\left( 整数n＞2\right)，那么2^a-1分成n个素数的乘积\)

太阳

\(方程:\left( ax+1\right)\times\left( ay+1\right)-\frac{2^a-1}{2}＝0，\left( 素数a＞0，未知数x和y\right)\)
\(找到一组正整数解，x＞y，素数ax+1，结论:2^a-1分成两个素数的乘积\)

yangchuanju

二元一次方程判断梅森素数
已知：素数a>0，未知数x和y，(ax+1)×(ay+1)-2^a+1=0，方程没有正整数解
结论：2^a-1必定是素数。

解：
(ax+1)×(ay+1)-2^a+1=0不是二元一次方程，而是二元二次方程。
如果给定x(或y)，则对于y(或x)方程变成一元一次方程。

梅森数2^a-1不论是不是素数，都可表示成2ki*a+1或2ki*a+1的乘积；
式中a是素数，ki是≥1的正整数，i是有限数，等于1,2，……i。
如果该梅森数不是梅森素数，不论它有几个素因子，都可表示成(2k1*a+1)×(2k2*a+1)=(ax+1)×(ay+1)的形式，式中x=2*k1, y=2*k2都是非0正整数；
如果该梅森数是梅森素数，硬它表示成(2k1*a+1)×(2k2*a+1)=(ax+1)×(ay+1)的形式，式中x=2*k1, y=2*k2必有一个等于0。

如果方程有正整数解，即有正整数x和y使得方程成立，2^a-1便不是素数；
反之如果方程没有正整数解，即没有正整数x和y使得方程成立，2^a-1便是素数；
即找到了一个梅森素数。

yangchuanju

下一步是如何找到这个方程没有正整数解的问题了。
令a=31，
y=[(2^a-1)÷(ax+1)-1]÷a=[(2^31-1)/(31x+1)-1)/31
=(2147483647/(31x+1)-1)/31
x的取值范围是1-1494，即需1494次试除都不是方程的正整数解，才能确定2^31-1是素数。
式中1494等于2147483647^0.5/31=1494.869向下取整值。

又令a=7897466719774591（16位素数）
y=[(2^a-1)÷(ax+1)-1]÷a
x的取值要达到(2^a-1)的平方根除以a，约等于10^48758326-10^16，
计算量：
1次求幂数，1次减1；
10^48758326-10^16次除法，10^48758326-10^16次减1；
再加10^48758326-10^16次除法，判断每一次除法的商是不是整数；
总计约需4*10^48758326次计算。

yangchuanju

改令a=100000007（最小的过亿素数）
y=[(2^a-1)÷(ax+1)-1]÷a
x的取值要达到(2^a-1)的平方根除以a，约等于10^30103002-10^8，
计算量：
1次求幂数，1次减1；
10^301030002-10^8次除法，10^30103002-10^8次减1；
再加10^301030002-10^8次除法，判断每一次除法的商是不是整数；
总计约需4*10^30103002次计算。
尚若100万个梅森数中有一个梅森素数，试除总次数平均为400*10^300000000次。
如此看来要找到第52号素数也确实不是一件容易事呀！
（现用的Lucas Lehmer判定法肯定比太阳试除法简单快捷的多）

太阳

\(例1:方程\left( 29x+1\right)\times\left( 29y+1\right)-2^{29}-1＝0\)
\(正整数解:\begin{cases}
x=8\\
y=79454
\end{cases}，\begin{cases}
x=38\\
y＝16784
\end{cases}，\begin{cases}
x＝72\\
y＝8862
\end{cases}，\begin{cases}
x＝79454\\
y＝8
\end{cases}，\begin{cases}
x＝16784\\
y＝38
\end{cases}，\begin{cases}
x＝8862\\
y＝72
\end{cases}\)
\(2^{29}-1=233\times1103\times2089\)
\(估计2^{29}-1含有最少两个素数因子大于1000，\frac{1000}{29}\approx34.4827，取x\ge34\)
\(方程\left( 29x+1\right)\times\left( 29y+1\right)-2^{29}-1＝0，y＞x，x\ge34，试除法，x＝38\)
\(按照这样做法找到2^{29}-1含有素数因子1103\)
试除法:找到1亿位大素数

太阳

太阳 发表于 2022-1-31 10:05
\(例2:方程\left( 71x+1\right)\times\left( 72y+1\right)-2^{71}-1＝0\)
\(试除法，y＞x，找到一组正整数 ...

估计2^71-1含有最少两个素数因子大于100000，100000/71≈1408.45，取x≥1408
试除法，x＝3218，找到2^71-1含有素数因子228479

yangchuanju

改进的试除法
令a=100000007（最小的过亿素数）
y=[(2^a-1)÷(ax+1)-1]÷a
x的取值要达到(2^a-1)的平方根除以a，约等于10^30103002-10^8，
计算量：
取不同的x值，计算ax+1，约需10^30103002-10^8次；
判定并找出ax+1中的素数，约需10^30103002-10^8次；
设其中的素数只有万分之1，
下面的试除约需10^30103002-10^8-10^4，判断每一次除法的商是不是整数；
总计算次数有所减少，但总计算次数仍然是天文数字。

yangchuanju

太阳试除法再改进
令a=43，
y=[(2^a-1)÷(ax+1)-1]÷a=[(2^43-1)/(43x+1)-1)/43
=(8796093022207/(43x+1)-1)/43
x的取值范围是1-68972，最多要68972次试除才能找到方程的所有正整数解，进而确定2^43-1的分解式；
式中68972等于8796093022207^0.5/43=68972.58向下取整值。
实际操作中，x是从小到大取值的，当x等于10时整除出现，y等于474617872，43*10+1=431是素数，第1个素因子被找到。

43y+1=20408568497，经查证它不是素数；
继续接着试除（或将被除数改为20408568497试除），当x=226时又出现整除，43*226+1=9719是素数，第2个素因子被找到。
8796093022207除以431再除以9719等于2099863，经查证2099863是素数，不再继续试除；
亦可继续试除下去，至x=48834时，第3次再次出现，43*48834+1=2099863。
从而得到：8796093022207<13>=431×9719×2099863
2^43-1=        8796093022207        
x        y        整除性
1        4649097792        0
2        2351267849        0
3        1573540791        0
4        1182429496        0
5        947038439.1        0
6        789808119.1        0
7        677351996.1        0
8        592928414        0
9        527217275.3        0
10        474617872        20408568497
11        431561820.3        0
12        395667897.2        0
226        21047464        905040953
227        20954753.39        0
228        20862855.95        0
48834        97416        4188889