Достаточность в тесте Ферма

[cantMath]

Здравствуйте, меня интересует следущее: на днях я наткнулся на вот эту теорему http://pmpu.ru/vf4/modular/index#%D0%BA%D1%80%D0%B8%D1%82%D0%B5%D1%80%D0%B8%D0%B9_%D0%BF%D1%80%D0%BE%D1%81%D1%82%D0%BE%D1%82%D1%8B_%D1%87%D0%B8%D1%81%D0%BB%D0%B0 , до этого момента считал тест Ферма пригодным только для опровержения простоты (как и написано на WIKI). Если все изложенное по ссылке имеет место быть, то прошу популярным языком объяснить условие достаточности в описанном методе. Спасибо.

[nnosipov]

Эта теорема Люка (E. Lucas). Что именно непонятно в доказательстве достаточности?

[VAL]

cantMath в сообщении #734090 писал(а):

Здравствуйте, меня интересует следущее: на днях я наткнулся на вот эту теорему http://pmpu.ru/vf4/modular/index#%D0%BA%D1%80%D0%B8%D1%82%D0%B5%D1%80%D0%B8%D0%B9_%D0%BF%D1%80%D0%BE%D1%81%D1%82%D0%BE%D1%82%D1%8B_%D1%87%D0%B8%D1%81%D0%BB%D0%B0 , до этого момента считал тест Ферма пригодным только для опровержения простоты (как и написано на WIKI). Если все изложенное по ссылке имеет место быть, то прошу популярным языком объяснить условие достаточности в описанном методе.

Никакого противоречия с тем,что написано в Википедии тут нет. Для применения МТФ нужно знать только $p$. А для применения данного теста нужно знать простые множители числа $p-1$, т.е. этот тест позволяет эффективно проверить $p$ на простоту, если для $p-1$ мы умеем решать гораздо более трудоемкую задачу.