Популярное

Мифы о звукоизоляции



Как построить дом из пеноблоков



Как построить лестницы на садовом участке



Подбираем краску для ремонта



Каркасные дома из дерева


Главная » Свойства псевдопростых чиселтрофимов

Свойства псевдопростых чисел

Трофимов Е.А. featrofimov@mail.ru)

Научно исследовательский институт информационных технологий

Практически в каждой монографии по теории чисел имеется ссылка на псевдопростые числа, однако более или менее детального исследования этого предмета не встречается. Напомним, что псевдопростые числа - это составные натуральные числа, удовлетворяющие малой теореме Ферма [1 ]. Согласно этой теореме для любого простого числа р и любого натурального числа а е N взаимно простого с р, (а,р)=1 справедливо сравнение

ap -1 = 1(modp) . (1)

Другими словами, частное от деления (ap-1 - 1) на р всегда является целым числом. Известно, что это утверждение верно не только для простых чисел р. Существуют составные натуральные числа b е N, проявляющие себя как простые для малой теоремы Ферма, для которых так же верно сравнение

ab -1 = 1(modb) . (2)

Если в качестве основания в этом сравнении взять число а = 2, то составные числа b называются псевдопростыми, если же сравнение верно для любого а, (а^)=1, то числа называются абсолютно псевдопростыми (далее по тексту b-числа).

Следует отметить, что b-числа обладают многими интересными свойствами. Для них, например, так же как и для простых чисел можно указать закон распределения в натуральном ряде N. Распределение простых чисел р описывается, как известно [ 2 ] асимптотической формулой Чебышева (количество простых чисел не превышающих x е N):

n(x) -таточ n(x) -

Ln (x)

Аналогично распределение b-чисел достаточно точно описывается формулой:

3 Ln (x)

Эта формула справедлива для сравнительно больших x, поскольку минимальное абсолютно псевдопростое число равно bmin = 561. Его каноническое разложение

представляет произведение трех простых чисел bmin = 3 11 17 .

В общем виде каноническое разложение b-числа будем записывать bn = Р1 P2 Pn , где n - его порядок (число простых сомножителей). При записи

будем иметь в виду, что Pi > Pi 1, i = 2,n. Такое нормирование структуры

канонического разложения вполне допустимо, поскольку до настоящего времени не найдено b-чисел, для которых хотя бы один сомножитель Pi имеет степень больше

единицы.

Одним из самых существенных свойств b-чисел является ограничение максимального сомножителя Pn канонического разложения:

Pn -1 < Pn * P1 P2 2Pn +1 . (3)

Из этой формулы легко получить алгоритм расчета b-чисел. Если мы произвольно зададим набор первых n-1 простых чисел в каноническом разложении, то



простым перебором всех pn из диапазона (3) получим ограниченное число возможных

вариантов Ъ-чисел. Достаточно провести проверку, все ли варианты удовлетворяют

малой теореме Ферма (2)?

Был составлен каталог всех Ъ-чисел не привышающих x = 1010 (каталог

размещен на сайте http: www.rema.44.ru). Минимальным и максимальным числом в

каталоге являются соответственно числа:

Ъ . = 3 11 17 , шш

bmax = 9999109081 = 13 19 61- 73 9091.

Вывод неравенства (3) достаточно прост. Сначала покажем, что одним из необходимых условий существования Ъ-чисел является кратность числа (Ъ - 1) обобщенной функции Эйлера L (Ъ), то есть выполняется условие

Ъ -1 = 0(modL0>)) (4).

Как известно [ 2 ], для обобщенной функции Эйлера справедливо сравнение

aL(l)) = ЦтосШ).

Поскольку мы предположили, что для Ъ-чисел частное (Ъ - 1)/L(tj) является целым числом, то, используя свойства сравнений, получим

Ъ -1 Ъ -1 (аЦЪ))ЦЪ) = (шосСЪ), или

аЪ-1 = ЦтосСЪ), из чего следует, что Ъ - абсолютно псевдопростое число.

Учитывая, что каноническое разложение Ъ-чисел не имеет степеней сомножителей p j, функция Эйлера L(fr) представляет собой наименьшее общее

кратное всех (p. -1) . Таким образом, из условия (4) следует

Ъ -1 = 0(mod(pj -1)) , i = 2,n (5). Отсюда следует, что при i = n

= k, k е N, k > 0 , или

pn -1

p1 p2...pn -1 = kpn -k , или pn

k - p1 p2 pn -1

Так как pn положительное число, то k > p1 p2-pn-1. Проведем замену k-p1 p2...pn-1 -1 = c. Тогда

p, p2...pn-1 + с

pn = -1-21 + С 1-, причем c 0, так как pn - простое число.

Отсюда следует, что pn ограничено сверху и принимает максимальное значение при c = 1, то есть

p < p < p1 p2-pn-1 +1

Таким образом, наличие простого числа в указанном выше диапазоне является одним из необходимых условий существования Ъ-чисел. Оно может быть представлено в виде следующей теоремы, устанавливающей зависимость между сомножителями р1 .

Теорема 1. Для того чтобы составное число Ъп = p1 p2-pn , где p. > p. 1

являлось абсолютно псевдопростым, необходимо выполнение следующего сравнения:



P1 p2 pn-1 = Pn(mod(Pn - 1)) . (6)

Другими словами, число P2-Pn-1 - Pn) должно делиться без остатка на (Pn - 1) , или частное

P1 P2 Pn-1 - Pn = c Pn - 1

должно принадлежать натуральному ряду чисел се N. При минимальном с=1 мы получаем условие (3) с максимальной оценкой рп.

Можно показать, что одним из свойств b-чисел является условие, определяющее их минимальный порядок.

Теорема 2. Минимальный порядок канонического разложения b-чисел равен 3.

Доказательство: Пусть n=2, тогда из условия ( 3 ) следует, что P1 < P2 < P1 , или < P1 +1, чего не может быть. Таким образом, если b является абсолютно

псевдопростым числом, то в каноническом разложении его должно быть не менее трех сомножителей.

Следующим свойством b-чисел является теорема об их

четности.

Теорема 3. Четных b-чисел не существует. Доказательство: Рассмотрим сравнение (5)

b -1 = 0(mod(Pi -1)).

Пусть p1 = 2, тогда (b - 1) является нечетным числом. В этом случае, сравнение (5) справедливо для i=1. Для других же i = 2,n оно не выполняется, поскольку величина (Pi -1) = 2t является четной, а значит (Pi - 1) не делит (b - 1), а это

противоречит условию существования b-чисел. Таким образом, P1 Ф 2. Приведем здесь еще две теоремы о свойствах b-чисел.

Теорема 4 . Если для какого либо Pi в каноническом разложении b -числа выполняется сравнение

Pi = 1(mod10k), где ке N, то

обязательно должно выполняться сравнение

b = 1(mod10k).

Доказательство: Условие p. = 1(mod10k) означает, что 10k(P. -1) . То есть

(pi - 1) кратно 10k, или (p. -1) = 10kt. Тогда, из сравнения (5) получим

b -1 = 0(mod(10kt) . В силу транзитивности отношения делимости, из последнего сравнения следует b = 1(mod10k), что и требовалось доказать.

Теорема 5 . Если bn является абсолютно псевдопростым числом с каноническим разложением bn = P1 P2...pn , то любая пара сомножителей p. и p j,

где j > i, i = 1,(n -1), j = 2,n , удовлетворяет неравенству

p j Ф 2kp. +1, где k е N любое число из натурального ряда.



Доказательство: Пусть pj = 2kp. +1. Тогда из сравнения (5) следует

Ъ - 1 = 0(mod2kpj) .

В силу транзитивности отношения делимости, из последнего сравнения следует

Ъ -1 = 0(modpj) .

Последнее сравнение не верно, поскольку Ъ-число сравнимо не с 1, а с 0 по любому сомножителю p. в качестве модуля. Таким образом, наше допущение не верно и

p j Ф 2kp. +1, что и требовалось доказать.

В соответствии с приведенными выше теоремами 4 и 5 можно сделать ряд частных заключений относительно структуры Ъ-чисел, например:

-если в каноническом разложении p1 = 3, то обязательно p2 Ф 7;

-если в каноническом разложении p, или p2 равняется 5, то ни одно p. (где

i > 2 ) не оканчивается на 1;

-если любой сомножитель pi канонического разложения Ъ-числа оканчивается

на 1 или на 01, 001 и т.д., то и само число оканчивается на те же числа, например:

561=31117 252601=41 61 101 2313774001=7 11 17 19-31-3001.

Обратное утверждение не верно, например:

9167487781=499 997 18427 9948941101=11 19 71 109 6151.

Мы не знаем, любое ли простое число может быть первым сомножителем Ъ-чисел? Если будем рассматривать множество Ъ-чисел одного порядка, например, трехзначные Ъ-числа, то можно утверждать, что для p1 = 11 и p1 = 197 трехзначных

Ъ-чисел не существует.

Мы знаем, что существуют Ъ-числа равные произведению меньшего Ъ-числа на простое. Но мы не знаем бесконечно ли много таких чисел, например:

Ъ'=5 17 53 353 937 Ъ' = Ъ' 3994849.

До сих пор не доказано, что Ъ-чисел бесконечно много. Мы также не знаем, бесконечно ли много Ъ-чисел одного порядка и существуют ли вообще Ъ-числа любого порядка?

Литература

1. Серпинский В. Что мы знаем и чего не знаем о простых числах / перевод с польского. - М.: - Л.: Изд-во физико-математической литературы , 1963 . - 92 с., ил

2. Бухштаб А.А. Теория чисел. - М.: Просвещение , 1966 . - 384 с.



© 2017 РубинГудс.
Копирование запрещено.