Казахстанского инженерно-педагогического университета дружбы народов серия «инженерно-техническая»
жүктеу/скачать 2,39 Mb.
|
- Бұл бет үшін навигация:
- О Б ОДНОМ КРИТЕРИИ ДЕЛИМОСТИ ЧИСЕЛ М ЕРСЕННА
- Критерии простоты чисел Мерсенна.
- Нахождение делителя числа Мерсенна.
| Әдебиеттер тізімі:
1.Иванова Н.И. Технология программирования. СПб: БХВ-Питер, 2006. - 324 с. 2.Новые педагогические и информационные технологии в системе образования. // Под ред. Полат Е. С. / М.: "Академия", - 2001. 3.Бабушкина И.А., Окулов С.М. Практикум по объектно-ориентированному программированию. - М.: БИНОМ, 2004 УДК 51.001.5.511 ОБ ОДНОМ КРИТЕРИИ ДЕЛИМОСТИ ЧИСЕЛ МЕРСЕННА Уштенов Е. Р.старший преподаватель Абдухаликова С. -студент 2-курса группы Т-109-14 Казахстанский инженерно-педагогический университет Дружбы народов, г. Шымкент Түйіндеме Бұл мақалада баламалы Мерсенн санының жай сан екенің тексеру әдісі Люка-Лемер әдісімен салыстырмасы беріледі, сонымен қатар осы тәсілдердің қойылған міндеттерін талдап шешуі корсетіледі. Введение.Простыечисла Мерсенна относятся к специальным числам и играют важную роль в Теории чисел и имеют прикладное значение. Числа вида  , (1), гдеn – 1, 2, 3…, называются числами Мерсенна.Марен Мерсенн (1588-1648г.г.) – французский математик, физик, философ и богослов. Если число - простое, то это число называется простое число Мерсенна, а числоn обязательно будет простым числом и записывается оно так:
 ,(2) , где p – простое число. [1, 234].В настоящее время известно 48 простых чисел Мерсенна. Это числа с показателями p: 2, 3, 5, 7, 13, 17, 19, 31, 61, и т. д., и записываются они так: =3,  =7, …,  =8191, …(3). Первые 7 простых чисел были вычислены Мерсенном, простота числа была доказана Л. Эйлером, а число  было вычислено русским математиком-самоучкой, священником И. М. Первушиным. Простые числа Мерсенна начиная с показателяp=521 были вычислены электронными вычислительными машинами и суперсовременными компьютерами. [1, 234-235; 2, 77-79].Хотя простые числа Мерсенна удерживают лидерство среди всех известных простых чисел по размерности вопрос бесконечности простых чисел Мерсенна остается открытым. [3, 7-8;4, 9-10].
Критерии простоты чисел Мерсенна.В 1878 году французский математик Э.Люка нашел метод определения простоты чисел Мерсенна, а позже, в 1932году американский математик Д.Х.Лемер упростил этот метод и поэтому он носит название Метода Люка-Лемера: Число  = , где p– простое число, является простым тогда и только тогда, когда  -й член реккурентной последовательности
 =4, = , = =194,…,  (4) делится на , т. е. когда  . [3, 234-235] (5)
Этот метод является очень трудоемким, т.к. число Нахождение делителя числа Мерсенна. На основании теоремы Ферма  т.е.  , имеем  ,[3, 44-46].
Поэтому первый и второй сомножители этого числа будут иметь вид 2pk+1, где - k=1, 2, 3, …,. Итак, мы установили, что если число Мерсенна составное, то оно представимо в виде: =(2p +1)(2p +1). (6)
Примем, что < , и , соответственно будет 2p+1<2p+1, а вследствие этого
2p +1< , 2p+1> . (7)
Равенство ( 3.1 ) преобразуем: = (2p+1)(2p+1)= 4 +2p+2p+1 , (8)
далее,  =2p(2p++) , (9)
или  = 2p ++, (10)
или 2p Вернемся к первому неравенству в выражении (9) и преобразуем его: 2p +1< , т.е. 1 ≤ < ,(14) и, пренебрегая единицами в последней формуле, получаем:
1≤ < (15)
Теперь подставляя значения  (16)
получим первый наименьший простой делитель числа Мерсенна. В противном случае, т.е. если при всех возможных значениях по формуле ( 3.9 ) получим
 , (17), то число – простое.
жүктеу/скачать 2,39 Mb. Достарыңызбен бөлісу:
|
при больших значениях p вырастают до гигантских численных значений и вследствие этого выполнение всех математических действий становится сложным.