теория-чисел - Вычислить в Z/37Z коэффициенты многочлена x(x+1)(x+2)...(x+36)

Если $%p$% -- простое число, то по модулю $%p$% (то есть в поле $%\mathbb Z/p\mathbb Z$%) выполнено тождество $%(x-1)(x-2)\ldots(x-(p-1))=x^{p-1}-1$%. Это следует из того, что в обеих частях равенства находятся многочлены степени $%p-1$% со старшим коэффициентом 1, и каждый из элементов $%1$%, $%2$%, ..., $%p-1$% будет корнем как одного многочлена, так и другого. Для левой части это ясно сразу, а для правой -- следует из малой теоремы Ферма: $%a^p-1$% делится на $%p$% при любом целом $%a$%, не делящемся на $%p$%.

Таким образом, разность двух рассматриваемых многочленов будет иметь степень строго меньше $%p-1$%, но при этом обладать $%p-1$% различными корнями. Такое бывает только для тождественно нулевого многочлена, откуда всё следует.

Осталось заметить, что $%x-1$% равно $%x+p-1$%, $%x-2$% равно $%x+p-2$% и так далее. После домножения обеих частей на $%x$% получится $%x^p-x$%, то есть мы знаем все коэффициенты.