Задача 111044

Темы:    [ Простые числа и их свойства ] [ Арифметика остатков (прочее) ] [ Разложение на множители ] [ Малая теорема Ферма ]

Сложность: 5+ Классы: 9,10,11

Условие

Автор: Канель-Белов А.Я.

Пусть p – простое число. Докажите, что при некотором простом q все числа вида  n^p – p  не делятся на q.

Решение

  Заметим, что     Значит, у этого числа есть простой множитель  q ≠ 1 (mod p²).  При этом   p^p – 1  делится на q.
  Предположим, что  n^p ≡ p (mod q).  Тогда  n^p2 ≡ p^p ≡ 1 (mod q).  С другой стороны, n, очевидно, не кратно q, и по малой теореме Ферма (см. задачу 60736)
n^q–1 ≡ 1 (mod q).  Так как  q – 1  не делится на p², наибольший общий делитель чисел p² и  q – 1  равен p или 1. В любом случае  p ≡ n^p ≡ 1 (mod q).
  Отсюда следует, что  0 ≡ p^p–1 + ... + p + 1 ≡ p (mod q).  Противоречие.

Источники и прецеденты использования

олимпиада
Название	Международная Математическая Олимпиада
год
Год	2003
задача
Номер	6