Статья подготовлена для студентов курса «Алгоритмы для разработчиков» в образовательном проекте OTUS. Рассмотрим задачу вычисления формул, состоящих из дробей, где в числителе и в знаменателе присутствуют факториалы (например, биномиальные коэффициенты). Будем вычислять факториалы по некоторому небольшому простому модулю p, пропуская сами множители p, потому что в дробях множители p сократятся, и результат будет взят по модулю p. Видно, что формула делится на несколько блоков одинаковой длины,...

Если честно следуя определению, попытаться посчитать факториал от отрицательного числа, то ничего не получится: убывающий ряд целых чисел никогда не закончится и ни к какому результату мы не придëм. Однако в конечных арифметиках результат получится вполне определëнным. В предыдущей заметке мы упомянули теорему Уилсона которая говорит чему равен факториал наибольшего числа в модулярной арифметике с простым модулем: Но эта теорема ничего не говорит нам о том, как выглядят прочие факториалы, если вычислять их в конечном поле ℤ/pℤ...