Покрывающее множество (теория чисел)

В математике покрывающим множеством для последовательности целых чисел называется множество простых чисел, таких, что каждый член последовательности делится по меньшей мере на одно число множества. Термин «покрывающее множество» используется только для экспоненциально растущих последовательностей.

Числа Серпинского и Ризеля[править | править код]

Использование термина «покрывающее множество» связано с числами Серпинского и Ризеля. Это нечётные натуральные числа $k$ , для которых $k2^{n}+1$ (число Серпинского) или $k2^{n}-1$ (число Ризеля) составные.

С 1960 года известно, что существует бесконечно много как чисел Серпинского, так и Ризеля, но поскольку имеется бесконечно много чисел вида $k2^{n}+1$ или $k2^{n}-1$ для любого $k$ , то для доказательства принадлежности $k$ числам Серпинского и Ризеля необходимо проверить, что любой член последовательности $k2^{n}+1$ или $k2^{n}-1$ делится на простые числа покрывающего множества.

Эти покрывающие множества формируются из простых чисел, которые в двоичном представлении имеют короткий период. Можно показать, что для получения полного покрывающего множества период должен быть не менее 24 чисел.^{[прояснить]} Период длиной 24 даёт покрывающее множество $\{\,3,5,7,13,17,241\,\}$ , а период длины 36 дает покрывающие множества: $\{\,3,5,7,13,19,37,73,\}$ ; $\{\,3,5,7,13,19,37,109\,\}$ ; $\{\,3,5,7,13,19,73,109\,\}$ и $\{\,3,5,7,13,37,73,109\,\}$ . Числа Ризеля имеют те же покрывающие множества, что и числа Серпинского.

Другие покрывающие множества[править | править код]

Покрывающие множества применяются также для доказательства существования составных последовательностей Фибоначчи (свободная от простых последовательность).

Концепцию покрывающих множеств легко обобщить на другие последовательности. В следующих примерах + используется так же, как в регулярных выражениях – означает 1 и больше. Например 91⁺3 означает множество {913, 9113, 91113, 911113…}

В качестве примера можно привести последовательность:

$(82\cdot 10^{n}+17)/9$ или $91^{+}3$
$(85\cdot 10^{n}+41)/9$ или $94^{+}9$
$(86\cdot 10^{n}+31)/9$ или $95^{+}9$

В каждом случае, каждый член делится на одно из простых чисел {3,7,11,13}. Эти простые формируют покрывающее множество в точности как для чисел Серпинского и Ризеля.

Ещё более простой случай — такая последовательность:

$(76\cdot 10^{n}-67)/99$ (n должен быть нечетным) или $(76)^{+}7$ [Последовательность: 7, 767, 76767, 7676767, 767676767 и т.д.]

Можно показать, что:

Если $n=6k+1$ , то $(76)^{+}7$ (с соответствующим количеством повторений) делится на 7.
Если $n=6k+3$ , то $(76)^{+}7$ делится на 13.
Если $n=6k+5$ , то $(76)^{+}7$ делится на 3.

Таким образом, мы имеем покрывающее множество всего из трех простых чисел {3,7,13}. Это стало возможным только потому, что мы наложили условие, что n должен быть нечетным.

Покрывающее множество также обнаруживается в последовательности:

$(343\cdot 10^{n}-1)/9$ или $381^{+}$ .

Можно показать, что:

Если $n=3^{k}+1$ , то $(343\cdot 10^{n}-1)/9$ делится на 3.
Если $n=3^{k}+2$ , то $(343\cdot 10^{n}-1)/9$ делится на 3.
Если $n=3^{k}$ , то $(343\cdot 10^{n}-1)/9$ разлагается на $((7\cdot 10^{k}-1)/3)\cdot ((49\cdot 10^{2}k+7\cdot 10^{k}+1)/3)$ .

Поскольку $(7\cdot 10^{k}-1)/3$ можно записать как $23^{+}$ , для последовательности $381^{+}$ мы имеем покрывающее множество $\{\,3,37,23^{+}\,\}$ — покрывающее множество с бесконечным числом членов.