Тест на простоту Поклінґтона: відмінності між версіями

'''Тест на простоту Поклінґтона''' ({{lang-en|Pocklington&ndash;Lehmer primality test}})&nbsp;— [[тест на простоту]] розроблений Генрі Кабурн Поклінґтоном і Деріком Генрі Лемером для визначення чи є число <math>n</math> [[просте число|простим]]. На виході тесту або доведення простоти, або неможливість доведення.

 

Нехай <math>n>1.</math> Якщо для кожного простого дільника <math>q</math> для <math>n-1</math> існує ціле таке, що

#<math>a^{n-1} \equiv 1 \pmod n,</math>

'''Доведення''': Для того, щоб показати, що <math>n</math> просте нам потрібно лише показати, що <math>\phi(n) = n - 1,</math> або простіше, що <math>(n - 1) | \phi(n).</math> Припустимо це не так, тоді існує просте <math>q</math> і показник <math>r > 0</math> такий, що <math>q^r | (n-1),</math> але не ділить <math>\phi(n).</math> Для цього цілого <math>q</math> ми маємо мати ціле, що задовольняє попереднім умовам. Тепер нехай <math>m</math> буде порядком <math>a</math> за модулем <math>n,</math> тоді <math>m | (n-1)</math> (перша умова), але не ділить <math>(n-1)/q</math> (друга умова). Отже <math>q^r</math> ділить <math>m,</math> яке ділить <math>\phi(n)</math>&nbsp;— протиріччя, яке доводить лему.

 

'''Теорема Поклінґтона''' ({{lang-en|Pocklington's Theorem}}) (1914): Нехай <math>n-1 = q^kR,</math> де <math>q</math>&nbsp;— просте, яке не ділить <math>R.</math> Якщо існує ціле таке, що <math>a^{n-1} \equiv 1 \pmod n</math> і <math>\gcd(a^{(n-1)/q}-1, n) = 1,</math> тоді кожен простий дільник <math>p</math> для <math>n</math> має вигляд <math>q^kr+1.</math>

 

'''Доведення''': Нехай <math>p</math> — довільний простий дільник <math>n,</math> і нехай <math>m</math> буде порядком <math>a</math> за модулем <math>p.</math> Як і в лемі, <math>m|(n-1)=q^kR</math> (перша умова для <math>a),</math> але не ділить <math>(n-1)/q=q^{k-1}R</math> (друга умова); отже <math>q^k|m.</math> Звісно, <math>m|(p-1)</math> і звідси висновок.

 

Вислідом застосування теореми Поклінґтона до кожного простого степеневого дільника <math>n</math> (плюс трошки роботи) є:

 

 

[[Категорія:Тести простоти]]

[[en:Pocklington primality test]]