По определению числом Жермен считается простое число
$g$,
если число
$2g + 1$ так же простоe.
Вопрос. Как долго могут повторяться числа Жермен, следуя друг за другом?
Сколько таких чисел могут составлять последовательность:
$(g_1, g_2, g_3, .....g_n)$ где
$g_n = 2g_{n -1} + 1.$Например, (2, 5, 11, 23, 47) или (89, 179, 359, 719, 1439, 2879).
Последние члены такой последовательности по определению не относятся к числам Жермен.
т.к. на них обрывается цепочка этих чисел, но мы будем включать эти числа в последовательность.
Цепочки чисел Жемен изучал британский математик Каннингэм, которые носят его имя.
Первый приведенный пример уникален, т.к. в дальнейшем нам не встретятся последовательности,
у первых членов которых последняя цифра будет 2 или 5. Все другие последовательности,
у которых первый член 10n +1, второй 20n + 3 будут иметь только три элемента и на элементе 40n +7
эта последовательность закончится, т.к. следующее число 80n + 15.
Интересен второй пример. Здесь все элементы имеют вид 10х +9 и последовательность таких
чисел Жермен не ограничивается последней цифрой числа.
Вопрос. Чем ограничено число элементов
$g_n ,$ которые могут составлять последовательность чисел Жермен?
Определим нулевой вычет цепочки
$g_0 = (g_1 – 1) / 2$ , который находится перед первым вычетом.
Он должен быть составным. Если число
$g_0$ будет простым, то это означает, что оно является вычетом цепочки
У числа
$g_0$ есть минимальный нечетный простой делитель
$р_ x$ , т.е.
$g_0 = Kp_x$Для определения числа вычетов цепочек Каннингэма нужна
формула общего члена таких цепочек, которая легко определяется.
из определения числа Жермен, используя нулевой вычет
$g_0$.
$g_n = 2^ng_0 + 2^n – 1$При
$n = \varphi(p_x)$ будем иметь
$2^n \equiv 1(mod p_x),$ т .е.
$g_n \equiv g_0 (mod p_x)$ т.к.
$g_0 = Kp_x$Вычеты цепочек Каннингэма простые числа,.взаимно простые
с модулем
$р_х$., т.е. являются вычетами ПСВ (приведенная система вычетов) по модулю
$р_х$Так как число вычетов цепочки считаются попарно и последний вычет не имеет пары,
то число чисел цепочки равно
$\varphi(p_x).- 1 = \varphi_2(p_x) = р_х - 2,$, где
$\varphi_2(p_x)$ - функция Эйлера второго порядкаё
кроме случаев, когда число
$2^n – 1$ является квадратичным вычетом по модулю
$р_х$.,
например
$p_x = 7, \varphi(px) = 6$, но
$2^6 \equiv 2^3 \equiv1(mod 7)$.
Необходимо отметить, что некоторые числа цепочки, являясь вычетами ПСВ,могут оказаться
не простыми числами, но взаимно простыми с модулем
$р_х$ и цепочки могут прерываться
этими числами раньше, чем
$р_х - 2,$
