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

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

Числа Серпинского и Ризеля Править

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ссылки Править

• Plateau and Depression Primes Архивная копия от 26 июля 2013 на Wayback Machine
• Sierpinski-like numbers Архивная копия от 17 июля 2012 на Wayback Machine
• Yves Gallot, A search for some small brier numbers Архивная копия от 9 апреля 2016 на Wayback Machine
• Louis Helm lhelm. Phil Moore, Payam Samidoost, George Woltman. Resolution of the mixed Sierpiński problem Архивная копия от 12 марта 2016 на Wayback Machine, INTEGERS: Electronic journal of combinatorial number theory 8 (2008), #A61