Задача 60754

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

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

Условие

Докажите, что для простого числа p вида  4k + 1  числа x = ± (2k)!  являются решениями сравнения  x² + 1 ≡ 0 (mod p).

Решение

((2k)!)² = (2k)!·1·2·...·(2k) ≡ (2k)!·(–1)^2k·4k(4k – 1)...(2k + 1) = (4k)! ≡ – 1 (mod p)  по теореме Вильсона (см. задачу 60719).

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

книга
Автор	Алфутова Н.Б., Устинов А.В.
Год издания	2002
Название	Алгебра и теория чисел
Издательство	МЦНМО
Издание	1
глава
Номер	4
Название	Арифметика остатков
Тема	Деление с остатком. Арифметика остатков
параграф
Номер	4
Название	Теоремы Ферма и Эйлера
Тема	Малая теорема Ферма
задача
Номер	04.128