, что й. Звідсі отрімуємо, что порядок елемента за модулем задовольняє умови: і НЕ діліть. Тому. У силу малої теореми Ферма. Отже,. Теорему доведено. p> Застосовуючі Дану теорему для всіх дільніків числа, отрімуємо Наступний теорему, что є узагальнення теореми Люка на випадок.
Теорема 4. Нехай, де. Если для будь-якого простого дільніка числа існує ціле таке, что ї, тоді число-просте. p> Доведення. Нехай - Складення й - нетрівіальній Простий дільнік числа. Зазначімо, что всегда можна вібрато дільнік так, що. Тоді з умови теореми віпліває, что для всіх простих дільніків числа існує ціле таке, что й. p> Міркуючі аналогічно зауваження до теореми Люка, отрімуємо, что має знайте елемент, Який має порядок Рівний за модулем. У силу малої теореми Ферма. Отже, справедливий ланцюжок нерівностей
.
Альо, протіріччя.
Дана теорема показує, что ЯКЩО удалось частково факторізуваті число, Причому факторізовать частина задовольняє умову, то - просте.
Перш чем переходіті до подалі, пріведемо Дві Класичні Частки випадка даної теореми.
Теорема 5. (Прот, 1878). Нехай, де.
Если існує число, для Якого віконується Умова
,
то - просте.
Теорема 6. (Прот, 1878). Нехай, де, и 3 НЕ діліть. Тоді просте в тому и Тільки в того випадка, коли віконується Умова
.
В
Доведення. У силу теореми Поклінгтона Достатньо перевіріті умову при й. Оскількі за умів, то Умова рівносільна Виконання рівності
В
Зазаначімо, что ЯКЩО в теоремі Поклінгтона замініті Рівність на більш Слабко умову, то можна отріматі
Наступний результат.
Лема 1. Нехай, де - просте число, что НЕ є дільніком. Если існує ціле таке, что й, то знайдеться Простий дільнік числа увазі при якомусь. p> Доведення. Нехай. Тоді за умів теореми чинності китайської теореми про Залишки віпліває, что існує таке, что й. Звідсі отрімуємо, что порядок елемента за модулем задовольняє умови: і НЕ діліть. Тому. p> У силу Лемі Гаусса про ціклічність мультіплікатівної групи кільця одержуємо. Зазначімо, что числа ї взаємно Прості як дільнікі сусідніх чисел. Тому. Отже,. p> хочай цею результат слабкіше, чем теорема Поклінгтона, Данії підхід, як показавши Н. Дієметко в 1988 р., такоже может буті Ефективно Використання для доведення простота чисел.
Теорема (Дієметко). Нехай, де - просте, - хлопцеві ї Если існує ціле таке, что й, то - просте.
Доведення. Нехай - НЕ ПРОСТО й. Тоді за лемою отрімуємо, что існує таке, що. p> Позначімо Тоді, де й. Звідсі. Отже,, де - не может дорівнюваті 0, інакше - просто, або 1, того що - непарна. Аналогічно,. Таким чином,
.
Протіріччя. Теорему доведено. p> Зазаначімо, что за умів теореми числа ї могут буті НЕ взаємно Прості. Ця теорема лежить в Основі алгоритмом генерації простих чисел у вітчізняному стандарті на цифровий підпис Р 34.10-94. p> У ньом як обіраються НЕ Дуже Високі степені числа 2, а перебуває перебором. (З 1 липня 2002 р. цею стандарт БУВ чинний на новий Р 34.10-2001).
Метод Маурера
У 1995 р. У. Маурер опублікував швидкий алгоритм генерації доведених простих чисел, близьким до Випадкове. У его Основі лежить Посилення теореми Поклінгтона на випадок, коли факторізовать частина числа задовольняє нерівності. Крім того, Йому удалось оцініті ймовірність успіху при Випадкове поиска числа в умові теореми Поклінгтона.
Следующая лема є спеціальнім випадка теореми Поклінгтона.
Лема 2. Нехай Если існує ціле таке, что для будь-якого простого дільніка числа віконані умови І, ті КОЖЕН Простий дільнік числа має вигляд при Деяк цілому Если, крім того, або - хлопця й, то - просте.
Доведення. Нехай - Складення й - нетрівіальній Простий дільнік числа. Тоді за умови теореми віпліває, что й. Міркуючі аналогічно зауваження до теореми Люка, отрімуємо, что має знайте елемент, Який має порядок Рівний за модулем. У силу малої теореми Ферма. p> Для доведення іншого Твердження, Припустиме, що. Тоді.
Если, то Если - непарний й, то й
В
просте число поклінгтон мауер люк
Протіріччя.
Следующая лема доведена Д. Коувером и Дж. Куіскуотером в 1992 р. p> Лема 3. Нехай и задовольняють умову Лемі 1. Візначімо числа ї рівністю. Если ї числа не дорівнює нулю й Не є ПОВНЕ квадратом, то - Прості. p> Доведення. Відповідно до Лемі 1 для шкірного простого дільніка числа віконується нерівність За умів. Тому, ЯКЩО число
- Складення, то воно НЕ может мати больше двох простих дільніків. Нехай
і. . br/>
Маємо інакше.
Если, то
Звідсі, проте у цьом випадка Тому. p> Отже, і. За теоремою Вієта є корінь ква...
