Если честно следуя определению, попытаться посчитать факториал от отрицательного числа, то ничего не получится: убывающий ряд целых чисел никогда не закончится и ни к какому результату мы не придëм. Однако в конечных арифметиках результат получится вполне определëнным.
В предыдущей заметке мы упомянули теорему Уилсона которая говорит чему равен факториал наибольшего числа в модулярной арифметике с простым модулем:
Но эта теорема ничего не говорит нам о том, как выглядят прочие факториалы, если вычислять их в конечном поле ℤ/pℤ. Об этом я и предлагаю поразмыслить.
Напомню, что полем называется числовая система, в которой определены операции сложения и умножения с обычными законами: сочетательным, распределительным и переместительным для сложения. У каждого ненулевого элемента a в поле есть противоположный −a и обратный 1/a. В полях вычетов (кольцах с простыми модулями) для умножения переместительный закон тоже выполняется. Арифметика остатков от целочисленного деления на число p будет полем, если p — простое число.
В поле ℤ/pℤ число p – 1 = –1, так что утверждение теоремы Уилсона в нём можно записать так:
Выглядит, согласитесь, достаточно просто. А что можно сказать о величине (–2)! в конечном поле? Это легко вычислить:
Тоже неплохое значение, причем, в отличие от (–1)! = p –1≡ –1 mod p, оно выглядит одинаково во всех полях вычетов, не зависимо от их модуля!
Такое простое значение позволяет легко вычислить (–3)!
Конкретное значение числа, противоположного обратному двойке, зависит от модуля, так что имеет смысл оставить этот ответ в такой форме. Сделаем ещё пару шагов назад:
Теперь можно сказать, что мы нащупали общую картину:
Получается, что факториалы в поле вычетов ведут себя достаточно симметрично:
Число 0 не входит в мультипликативную группу поля, поэтому мы искусственно положили 0! = 1. Это, во-первых, хорошо вписывается в найденную нами схему:
а во-вторых, соответствует духу алгебры: "пустое" произведение (без множителей) должно, всё-таки, быть произведением, то есть, элементом мультипликативной группы, а поскольку оно незримо входит в любое произведение и не меняет его, то оно должно быть равно нейтральному элементу этой группы — единице.
* * *
Дополнение для тех, кто знаком с гамма-функцией и элементами комплексного анализа. Как известно, вещественным аналогом факториала является гамма-функция, при этом Г(n + 1) = n! для целых n > 0.
В целых отрицательных точках гамма функция терпит разрыв. Так что и наивное определение факториала и более изощрëнное не дают определëнного ответа на вопрос чему равен, например, факториал от –2?
При этом в окрестности точки –n гамма-функция ведет себя, как гипербола:
Коэффициент (–1)ⁿ /n! называется вычетом функции, и вычисляется методами теории функций комплексной переменной. Для гамма-функции он в точности совпадает с полученным нами выражением для факториала в конечном поле. Действительно, если формально записать, что (–n)! = Г(1–n), подставить (1 – n) в выражение для вычета, и привести знаки, то получится:
Вот так красиво согласуются между собой комплексный анализ и теория чисел.