Побудова простих великих чисел (стр. 2 из 4)

Доведення. Нехай

– простий дільник числа . Тоді з умови теореми
випливає, що й . Звідси отримуємо, що порядок елемента за модулем задовольняє умови: і не ділить . Тому . У силу малої теореми Ферма . Отже, . Теорему доведено.

Застосовуючи дану теорему для всіх дільників

числа , отримуємо наступну теорему, що є узагальненням теореми Люка на випадок .

Теорема 4. Нехай

, де . Якщо для будь-якого простого дільника числа існує ціле таке, що й , тоді число -просте.

Доведення. Нехай

– складене й – нетривіальний простий дільник числа . Зазначимо, що завжди можна вибрати дільник так, що . Тоді з умови теореми випливає, що для всіх простих дільників числа існує ціле таке, що й .

Міркуючи аналогічно зауваженню до теореми Люка, отримуємо, що має знайтися елемент, який має порядок рівний

за модулем . У силу малої теореми Ферма . Отже, справедливий ланцюжок нерівностей

.

Але

, протиріччя.

Дана теорема показує, що якщо вдалося частково факторизувати число

, причому факторизована частина задовольняє умову , то – просте.

Перш ніж переходити до подальшого, приведемо дві класичні частки випадку даної теореми.

Теорема 5. (Прот, 1878). Нехай

, де .

Якщо існує число

, для якого виконується умова

,

то

– просте.

Теорема 6. (Прот, 1878). Нехай

, де , і 3 не ділить . Тоді просте в тому і тільки в тому випадку, коли виконується умова

.

Доведення. У силу теореми Поклінгтона достатньо перевірити умову

при й . Оскільки за умовою , то умова рівносильна виконанню рівності

Зазаначимо, що якщо в теоремі Поклінгтона замінити рівність

на більш слабку умову , то можна отримати
наступний результат.

Лема 1. Нехай

, де – просте число, що не є дільником . Якщо існує ціле таке, що й , то знайдеться простий дільник числа виду при якомусь .

Доведення. Нехай

. Тоді за умовою теореми в силу китайської теореми про залишки випливає, що існує таке , що й . Звідси отримуємо, що порядок елемента за модулем задовольняє умови: і не ділить . Тому .

У силу леми Гаусса про циклічність мультиплікативної групи кільця

одержуємо . Зазначимо, що числа й взаємно прості як дільники сусідніх чисел. Тому . Отже, .