Мифы о звукоизоляции Как построить дом из пеноблоков Как построить лестницы на садовом участке Подбираем краску для ремонта Каркасные дома из дерева |
Главная » Свойства псевдопростых чиселтрофимов Свойства псевдопростых чисел Трофимов Е.А. 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 с. |
© 2024 РубинГудс.
Копирование запрещено. |