Числа Мерсенна и Ферма
Isaeva (обсуждение | вклад) (Новая страница: «При рассмотрении отдельных классов простых чисел значительный интерес представляет во…») |
Isaeva (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
При рассмотрении отдельных классов простых чисел значительный интерес представляет вопрос о простых числах специального вида, например, числа Мерсенна или числа Ферма. | При рассмотрении отдельных классов простых чисел значительный интерес представляет вопрос о простых числах специального вида, например, числа Мерсенна или числа Ферма. | ||
| + | |||
'''Определение''' | '''Определение''' | ||
| Строка 13: | Строка 14: | ||
Например, при <math>p = 2, 3, 5, 7, 13, 17, 19</math> мы получаем простые числа Мерсенна: <math>3, 7, 31, 127, 8191, 131071</math>, а при <math>p = 11, 23, 29</math> числа <math>2^p - 1</math> - составные. | Например, при <math>p = 2, 3, 5, 7, 13, 17, 19</math> мы получаем простые числа Мерсенна: <math>3, 7, 31, 127, 8191, 131071</math>, а при <math>p = 11, 23, 29</math> числа <math>2^p - 1</math> - составные. | ||
| − | + | '''Свойства чисел Мерсенна''' | |
* Если <math>M_n</math> является простым, то число ''n'' также простое. Обратное в общем случае неверно, наименьшим контрпримером является <math>M_{11} = 2047 = 23\cdot 89</math>. | * Если <math>M_n</math> является простым, то число ''n'' также простое. Обратное в общем случае неверно, наименьшим контрпримером является <math>M_{11} = 2047 = 23\cdot 89</math>. | ||
| Строка 20: | Строка 21: | ||
| − | + | Числа Мерсенна получили известность в связи с эффективным тестом простоты Люка — Лемера, благодаря которому простые числа Мерсенна давно удерживают лидерство как самые большие известные простые числа. | |
| Строка 30: | Строка 31: | ||
Все числа Мерсенна и Ферма – взаимно простые. | Все числа Мерсенна и Ферма – взаимно простые. | ||
| + | |||
| + | Необходимо отметить, что значения чисел Мерсенна и Ферма быстро растут. Это не позволяет использовать лишь их в качестве модуле СОК. | ||
Версия 12:27, 10 сентября 2014
При рассмотрении отдельных классов простых чисел значительный интерес представляет вопрос о простых числах специального вида, например, числа Мерсенна или числа Ферма.
Определение
Числа Мерсенна — числа вида 
, где 
— натуральное число.
Названы в честь французского математика Марена Мерсенна.
Иногда числами Мерсенна называют только числа 
с нечетными или простыми индексами n.
Множества простых чисел в этих последовательностях совпадают, а потому понятие простого числа Мерсенна не зависит от того, как именно определяются числа Мерсенна.
При простых значениях n = p число может оказаться простым, но может быть составным.
Например, при 
мы получаем простые числа Мерсенна: 
, а при 
числа 
- составные.
Свойства чисел Мерсенна
- Если является простым, то число n также простое. Обратное в общем случае неверно, наименьшим контрпримером является
.
- Любой делитель числа
для простого p имеет вид 2pk+1, где k — натуральное число (следствие малой теоремы Ферма).
Числа Мерсенна получили известность в связи с эффективным тестом простоты Люка — Лемера, благодаря которому простые числа Мерсенна давно удерживают лидерство как самые большие известные простые числа.
Определение
Числа Ферма — числа вида 
, где n — неотрицательное целое число.
При 
числа Ферма простые: 
.
Все числа Мерсенна и Ферма – взаимно простые.
Необходимо отметить, что значения чисел Мерсенна и Ферма быстро растут. Это не позволяет использовать лишь их в качестве модуле СОК.
