произведение матриц по модулю простого числа.

[Руст]

Рассмотрим произведение матриц по модулю простого числа $p$ (матрицы над $Z_p$):

$$\binom{a \ b}{c \ d}=\binom{1 \ \ p-1}{1 \ \ \ \ \ \ 0}\binom{1 \ \ p-2}{1 \ \ \ \ \ \ \ 0}...\binom{1 \ 1}{1 \ 0}.$$

Доказать, что $p\not |a+b$ при $p>2.$

[Хорхе]

(Оффтоп)

Хорошо, что есть OEIS:
$ \begin{pmatrix}1 & n\\1& 0\end{pmatrix} \cdots\begin{pmatrix}1 &2\\1& 0\end{pmatrix} \begin{pmatrix}1& 1\\1 &0\end{pmatrix}= $
A000932(n) A059480(n-1)
A000932 (n-1) A059480(n-2)

Теперь об этом забыли

По индукции легко убедиться, что в сумме будет A000085(n+1).

То есть надо показать, что количество инволюций на $p$ элементах не делится на $p$, если $p$ простое. На самом деле, очень легко показать, что остаток единица: циклическая группа порядка $p$ действует естественным образом на таких инволюциях, у этого действия несколько орбит порядка $p$ и одна орбита порядка $1$ (тождественная перестановка).

[Руст]

Надо же, на все есть последовательности и все уже изучено.

Несколько слов откуда я пришел к этой задаче.
Пусть определена последовательность $x_1=1,x_{n+1}=1+\frac{n}{x_n}$. Ясно, что все члены рациональны и можно представить в виде $x_n=\frac{a_n}{a_{n-1}}$, где последовательность натуральных чисел $a_n$ определяется по формуле:
$a_0=1=a_1, a_{n+1}=a_n+na_{n-1}$ (целочисленные дробно-линейные преобразования).
Если обозначить через $d_n=(a_n,a_n-1)$. То предложенная мною задача эквивалентно тому (можете сами доказать), что $p\not |d_n$ при всех $n$. Т.е. числитель и знаменатель $x_n$ растет примерно как $\sqrt{n!}$ если не учесть сокращение на степень двойки.
Кстати интересно узнать, чему равно $v_2(d_n)$.