Задача 30681

Тема:    [ Малая теорема Ферма ]

Сложность: 4- Классы: 9,10

Условие

Пусть p и q – различные простые числа. Докажите, что
  а)  p^q + q^p ≡ p + q (mod pq);

  б)   – чётное число, если  p, q ≠ 2.

Подсказка

Докажите, что  p^q + q^p – p – q  делится и на p, и на q.

Решение

а) По малой теореме Ферма  p^q ≡ p (mod q),  q^p ≡ q (mod p).  Следовательно,  p^q + q^p – p – q  делится и на p, и на q.

б)  p + q < pq,  поэтому     Числитель полученной дроби чётен, а знаменатель нет, следовательно, частное чётно.

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

книга
Автор	Генкин С.А., Итенберг И.В., Фомин Д.В.
Год издания	1994
Название	Ленинградские математические кружки
Издательство	Киров: "АСА"
Издание	1
глава
Номер	10
Название	Делимость-2
Тема	Теория чисел. Делимость
задача
Номер	095