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

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