Найти остаток 67! , когда оно поделено на 71.

Предыдущий
вопрос Следующий
вопрос

По теореме Вильсона, если p простое, то (p-1)! + 1 = 0 mod p .

71 простое, тогда

70! = -1 = 70 mod 71 => [сокращаем на 70]

69! = 1 mod 71 => [отделяем искомую величину]

67! * 68 * 69 = 67! * (-3) * (-2) = 67! * 6 = 1 mod 71 => [умножаем на 12, обратное к 6 по модулю 71]

67! *6 * 12 = 12 mod 71 =>

67! = 12 mod 71.

Ответ: 12