О делителях чисел Мерсенна23.01.2024 15:15

Некоторые размышления о числах Мерсенна и их делителях.

Введение

Число Мерсенна — это число вида M_n = 2^n -1 для некоторого натурального числа . В этой статье я буду рассматривать только числа M_p, p — простое число, за исключением последнего размышления. Их делители имеют вид 2pk + 1 для некоторого

$0 ⩽ k ⩽ \frac{M_p - 1}{2p}$ .

Эти числа интересны тем, что при некоторых они дают простые числа. Например, некоторые простые числа Мерсенна: $M_2 , M_3 , M_5 , M_7 , M_{13}, M_{17} , M_{19} ,M_{31 }, M_{61}, .... , M_{82,589,933} , ....$

Для проверки простоты этих чисел используется полиномиальный (время работы полиномиально зависит от размера входных данных) , истинный (есть вероятностные) и безусловный (не зависит от недоказанных гипотез) тест Люка-Лемера. В тесте применяется возведение в квадрат.

Простые числа Мерсенна тесно связаны с совершенными числами , используются для построения вихря Мерсенна. В целом, про эти числа известно очень мало. Мы даже не знаем конечно или бесконечно количество простых чисел Мерсенна.

Более подробную информацию можно найти в интернете. Вот, например, отличная статья про 51-ое простое число Мерсенна, самое большое известное простое число на данный момент.

Существуют 2 вида чисел Мерсенна с простым показателем степени: p ≡ 3 (mod~4) и p ≡ 1 (mod~4) . Хорошо-хорошо, есть еще M_2 , но в данной статье будем как-то без него.

Давайте рассмотрим каждый случай подробнее.

Числа Мерсенна Mp, p ≡ 3 (mod 4)

Гипотеза 1

Любое число Мерсенна M_p , p ≡ 3 (mod~4) можно представить в виде:

(2p(4x + 1) + 1)(2p(4y) + 1) = M_p ~~~~~~~~~~~~~~~~(8px + 2p + 1)(8py + 1) = M_p~~~~~~~~~~~~~~~~~~~(1) $0 ⩽ x ⩽ \frac{M_p - 1 - 2p}{8p}$ $0 ⩽ y ⩽ \frac{\frac{M_p}{2p+1} - 1}{8p}$

Где и некоторые целые числа. Число может быть как больше, так и меньше числа .

Замечание. Если существует единственная пара решений x = (Mp - 1 - 2p)/8p, y = 0, то Mp — простое число.

Замечание. Может быть несколько делителей вида 8px + 2p + 1 или 8py + 1, но уравнение (1) все равно работает. Например, M47 имеет следующие делители:
8*47*6 + 2*47 + 1 ,
8*47*12 + 1 ,
8*47*35278 + 1

Из уравнения (1) получаем:

$8pxy + 2py + x + y = E_p ,~~~E_p = \frac{M_p -1 -2p}{8p}$

или

$x = \frac{E_p - 2py - y}{8py + 1} ,~~~~y = \frac{E_p - x}{8px + 2p + 1}$

Давайте рассмотрим уравнение $y = \frac{E_p - x}{8px + 2p + 1}.$

E_p ≡ x ~~(mod~~(8px + 2p + 1) ).

Представим E_p в виде k_1p + k_2 ,~~k_1 ≡ 0~(mod~2) . Мы получаем еще одно уравнение, так как E_p - x должно делиться на 8px + 2p + 1 :

$\frac{k_1 - 2m}{k_2 + 2pm -x} = 8x + 2$

или

$\frac{\frac{k_1}{2} - m}{k_2 + 2pm -x} = 4x + 1$

Откуда получаем квадратное уравнение:

$4x^2 + (1 - 4k_2 - 8pm )x -2pm - m + \frac{k_1}{2} - k_2 = 0~~~~~~~~~~~~~(2)$ $D = (8pm + 4k_2 + 1)^2 + 16(m - \frac{k_1}{2})~~~~~~~~~~~~~~~~(3)$

Дискриминант должен давать полный квадрат для некоторого целого $0⩽m < \frac{k_1}{2}$ .

Если D дает полный квадрат только при $m = \frac{k_1}{2}$ получается, что x = E_p , а это означает, что M_p — простое.

С другой стороны равняется:

D = (8pm + 4k_2 - 8x - 1)^2 =(4y - 4x -1)^2 = 9(4k + 1)^2 .

Таблица с примерами.

p	m	k	x	y
11	0	0	0	1
23	21	323	0	970
43	689,851	19,775,744	1	59,327,234
47	1,693,719	53,069,873	6	159,209,626
59	57,516,373	2,262,310,452	381	6,786,931,738
67	10,609,712	-473,659,546	1,421,340,032	361,395
71	128,128,789,384	6,064,762,697,247	402	18,194,288,092,144
79	2,252,826,913,357,820	118,648,884,103,511,865	4	355,946,652,310,535,600
83	525,408,387,585,967,207	29,072,597,446,423,518,618	0	87,217,792,339,270,555,855

Мы видим, что D ≡ 0~(mod~9) , а это значит можно представить в виде m = 9t + r .

Число находим из уравнения:

$(8p(9t + r) + 4k_2 + 1)^2 + 16(9t +r - \frac{k_1}{2}) ≡ 0~(mod~9) .$

Выбираем $r ≠ \frac{k_1}{2}~(mod~9)$ если p ≡ 1,2,5,7,8~(mod~9) и $r = \frac{k_1}{2}~(mod~9)$ если p ≡ 4~(mod~9) . C другой стороны из уравнения (2) мы видим, что:

$m = \frac{4x^2 + (1 - 4k_2)x + \frac{k_1}{2} - k_2}{8px + 2p + 1}$

или

$t = \frac{4x^2 + (1 - 4k_2 - 8pr)x + \frac{k_1}{2} - k_2 - 2pr - r}{9(8px + 2p + 1)}$

Получаем, что имеет форму x = 3l + r_x и так как y = 2pm +k_2 - x получаем y = 3j + r_y . Используя эти числа в уравнении (1), получаем:

(8p(3x + r_x) + 2p + 1)(8p(3y + r_y) + 1) = M_p (24px +8pr_x + 2p + 1)(24py + 8pr_y + 1) = M_p~~~~~~~~~(4)

Значит, любое число M_p,~p≡ 3~(mod~4) может быть представлено в таком виде.

Пример для p = 59.

$E_p = 1,221,315,153,185,219,\\k_2 = 105,\\\frac{k_1}{2} ≡ 8~(mod~9) ,\\m = 9t +1,\\x = 3l,\\y = 3j + 1$

Получается, что $M_{59}$ можно представить в виде:

$(24px + 2p + 1)(24py + 8p + 1) = M_{59}$

Числа Мерсенна Mp, p ≡ 1 (mod 4)

Гипотеза 2

Любое число Мерсенна можно представить в виде:

(2p(4x + 3) + 1)(2p(4y) + 1) = M_p ~~~~~~~~~~~~~~~~(8px + 6p + 1)(8py + 1) = M_p~~~~~~~~~~~~~~~~~~~(5) $0 ⩽ x ⩽ \frac{M_p - 1 - 6p}{8p}$ $0 ⩽ y ⩽ \frac{\frac{M_p}{6p+1} - 1}{8p}$

Где и некоторые целые числа. Число может быть как больше, так и меньше числа y.

Замечание. Если существует единственная пара решений x = (Mp - 1 - 6p)/8p, y = 0, то Mp — простое число.

Замечание. Может быть несколько делителей вида 8px + 6p + 1 или 8py + 1, но уравнение (5) все равно работает. Например, M113 имеет следующие делители:
8*113*3 +6*113 + 1 ,
8*113*25 + 6*113 + 1 ,
8*113*73 + 1 ,
8*113 *2067 + 1
8*113*1,180,108,554,057 + 6*113 + 1

Из уравнения (5) получаем:

$8pxy + 6py + x + y = E_p ,~~~E_p = \frac{M_p -1 -6p}{8p}$

или

$x = \frac{E_p - 6py - y}{8py + 1} ,~~~~y = \frac{E_p - x}{8px + 6p + 1}$

Давайте рассмотрим уравнение $y = \frac{E_p - x}{8px + 6p + 1}.$

E_p ≡ x ~~(mod~~(8px + 6p + 1) ).

Представим E_p в виде k_1p + k_2 ,~~k_1 ≡ 0~(mod~2) . Мы получаем еще одно уравнение, так как E_p - x должно делиться на 8px + 6p + 1 :

$\frac{k_1 - 2m}{k_2 + 2pm -x} = 8x + 6$

или

$\frac{\frac{k_1}{2} - m}{k_2 + 2pm -x} = 4x + 3$

Откуда получаем квадратное уравнение:

$4x^2 + (3 - 4k_2 - 8pm )x -6pm - m + \frac{k_1}{2} - 3k_2 = 0~~~~~~~~~~~~~(2)$ $D = (8pm + 4k_2 + 3)^2 + 16(m - \frac{k_1}{2})~~~~~~~~~~~~~~~~(3)$

Дискриминант должен давать полный квадрат для некоторого целого $0⩽m < \frac{k_1}{2}$ . Если D дает полный квадрат только при $m = \frac{k_1}{2}$ , то получается, что x = E_p , а это означает, что M_p — простое.

С другой стороны равняется:

D = (8pm + 4k_2 - 8x - 3)^2 =(4y - 4x -3)^2 = 9(4k + 3)^2 .

Таблица с примерами.

p	m	k	x	y
29	36	697	4	2098
37	28,137	694,051	0	2,082,156
41	6117	167,172	40	501,559
53	2,886,455	101,987,983	163	305,964,115
73	252,324,522,654,741	12,279,793,435,864,108	0	36,839,380,307,592,327
*5171993*	…	…	612	…

Мы видим, что D ≡ 0~(mod~9) , а это значит можно представить в виде m = 9t + r .

Число находим из уравнения:

$(8p(9t + r) + 4k_2 + 3)^2 + 16(9t +r - \frac{k_1}{2}) ≡ 0~(mod~9) .$

Выбираем $r ≠ \frac{k_1}{2}~(mod~9)$ если p ≡ 2, 4, 5,7,8~(mod~9) и $r = \frac{k_1}{2}~(mod~9)$ если p ≡ 1~(mod~9) . C другой стороны из уравнения (2) мы видим, что:

$m = \frac{4x^2 + (3 - 4k_2)x + \frac{k_1}{2} - 3k_2}{8px + 6p + 1}$

или

$t = \frac{4x^2 + (3 - 4k_2 - 8pr)x + \frac{k_1}{2} - 3k_2 - 6pr - r}{9(8px + 6p + 1)}$

Получаем, что имеет форму x = 3l + r_x и так как y = 2pm +k_2 - x получаем y = 3j + r_y . Используя эти числа в уравнении (1), получаем:

(8p(3x + r_x) + 6p + 1)(8p(3y + r_y) + 1) = M_p (24px +8pr_x + 6p + 1)(24py + 8pr_y + 1) = M_p~~~~~~~~~(4)

Значит, любое число M_p,~p≡ 1~(mod~4) может быть представлено в таком виде.

Пример для p = 53

$E_p =21,243,394,468,728 \\k_1 =400,818,763,560 \\k_2 = 48 \\\frac{k_1}{2} ≡ 6~(mod~9) \\m = 9t +2 \\x = 3l + 1 \\y = 3j + 1$

Из уравнения (5) получаем:

$(24px + 14p + 1)(24py + 8p + 1) = M_{53}.$

Другие мысли.

Теорема Вильсона. Натуральное число n > 1 простое тогда и только тогда, когда:

(n - 1)! ≡ -1~(mod~n)

Я не сумасшедший, но давайте попробуем использовать это для чисел Мерсенна:

(M_p - 1)! ≡ 1~*~2~*~3~*~....~*~(2^p -2)~~(mod~M_p)~~~~~~~~~~~~(9)

В уравнении (9) перемножим числа в правой части следующим образом: 1* (2^p - 2), 2 * (2^p - 3), 3 * (2^p - 4) ...

Получаем:

(M_p - 1)! ≡ (M_p -1^2) (M_p -2^2) (M_p -3^2) * ...~~(mod~Mp)~~~~~~~~~~(10)

В уравнении (10) первые $x = \sqrt{M_p}$ чисел имеют форму M_p - i^2 , остальные числа не могут быть представлены таким образом. Мы получаем

$s = \frac{M_p-1}{2}$

чисел и наблюдаем интересные вещи. Для составных чисел Мерсенна мы получаем некоторые (не все) повторяющиеся числа

$s_i , 1⩽ i ⩽ \frac{M_p-1}{2}$ .

Это означает, что для составных чисел Мерсенна (не только для простых показателей степени) мы получаем определенное количество квадратов, а для простых чисел Мерсенна все числа будут уникальными. Одно из самых интересных наблюдений то, что количество квадратов в правой части уравнения (10) равняется 4p^2y , где — это решение уравнения (1) или (5) (верно для простых показателей степени). Понятно, что использовать это никто не собирается, просто интересный факт.

Замечание. Эти размышления применимы для любых чисел, не только для чисел Мерсенна. Любое составное число всегда дает определенное количество квадратов в правой части (10). Если n в теореме Вильсонаявляется полным квадратом, в уравнении (10) мы получаем один или несколько нулей.

Теорема.

Нечетное натуральное число n > 1 является простым тогда и только тогда, когда последовательность:

$s_i = (i~*~(n - i))~(mod~n),~1⩽i⩽\frac{n-1}{2}$

не имеет повторяющихся элементов.

Пример 1.

$(2^4 -2)! ≡ 0~(mod~15) \\1~*~2~*~...~*~14 ≡ 0~(mod~15) \\14* 11 * 6* 14* 5* 9* 11 ≡ 0~(mod~15)\\5*6*9*11^2*14^2 ≡ 0~(mod~15).$

Здесь мы получили 2 квадрата и 3 уникальных числа. Причем 3 является делителем 15. Сумма квадратов и уникальных чисел 5 является делителем 15.

Пример 2.

$(2^5 -2)! ≡ -1~(mod~31)\\1~*~2~*~...~*~30 ≡ -1~(mod~31)\\30*27*22*15*6*26*13*29*12*24*3*11*17*21*23 ≡ -1~(mod~31)$

Все числа уникальны.

Пример 3.

$(2^{11} -2)! ≡ 0~(mod~2047)\\1~*~2~*~...~*~2046 ≡ 0~(mod~2047)\\2046~*~2043~*~2038~*~2031~*~... ≡ 0~(mod~2047)$

Мы получаем 484 квадрата и 55 уникальных чисел.

484 = 4~*~11^2~*~1, y = 1

Число (8*11*1 + 1) является делителем числа $M_{11}$

Следующая интересная деталь:

55 = 5 * 11 (3~*~11)^2 ≡ (5~*~11 +1)^2~(mod~2047) 3 = 4y -4x -1 5 = 4y + 4x + 1

Где числа x=0 и y = 1 являются решением уравнения (1).

Это верно для всех чисел M_p .

Другими словами:

Dp^2 ≡ ((8pm + 4k_2 + 1)p + 1)^2 ~(mod~M_p),~p ≡ 3~(mod~4) Dp^2 ≡ ((8pm + 4k_2 + 3)p + 1)^2~(mod~M_p),~p ≡ 1~(mod~4)

Заключение

Числа Мерсенна удивительны и изящны. Простые числа Мерсенна очень полезны в реальной жизни, особенно в криптографии. Лучшее понимание этих чисел привнесет очень много хорошего в нашу жизнь. Да, то что описано выше, является сложным для вычисления делителей при больших значениях , но в то же время это намного легче, чем просто искать делители в виде 2pk + 1 . Я верю в то, что есть более легкий способ проверки простоты этих чисел отличный от теста Люка-Лемера, возможно даже одной формулой.

Огромное спасибо, что прочитали эту статью.

P.S.

Является ли число $M_{433,494,767}$ простым?