Prove that $A^3\equiv I\mod p$. 
Let $p$ be a prime. Let $A$ be a $p\times p$ matrix whose $(i,j)$th-coordinate is ${i+j-2\choose i-1}$. Prove that $A^3\equiv I\mod p$.


Source: problem 10 from this problem set.

We need to show that in $\mathbb{Z}_p, A^3 -I $ is the zero matrix, or equivalently that the minimal polynomial of $A$ in $M_p(\mathbb{Z}_p)$ divides $x^3-1=(x-1)(x^2+x+1).$ Clearly $A$ is not the identity matrix (e.g. $A_{1,2} = 1\neq 0$). I'm not sure if it's necessary to determine the eigenvalues or the characteristic polynomial of $A$ (in $\mathbb{Z}_p$ of course, since it doesn't seem necessary to consider other fields). I know the formula for the Vandermonde determinant, but I'm not sure if it's useful for this problem. Clearly modular arithmetic properties would be useful (e.g. $a^x\equiv b^x\mod n$ whenever $a\equiv b\mod n$ and if $f$ is a polynomial with integer coefficients, then $f(n)\equiv f(m)\mod a$ whenever $n\equiv m\mod a$), but they're not enough to make some progress on this problem. I'm not sure if it's useful to find the inverse of $A$.
 A: Here is how I would approach the problem.

*

*The form of $\binom{i + j - 2}{i - 1}$ looks really suspicious. It reminds me of the Vandermonde formula
$$\binom{i + j - 2}{i - 1} = \sum_{k = 1}^{p} \binom{i - 1}{k - 1}\binom{j - 1}{k - 1}.$$
Thus, if we let $M$ be the matrix given by $M_{ij} = \binom{i - 1}{j - 1}$, then $A = MM^T$.


*Computing $M^TM$ tells me nothing. However, I observe that
$$A^3 = MM^TMM^TMM^T.$$
Therefore, if we let $B = MM^TM$, then $A^3 = BB^T$. So it suffices to prove $B$ is orthonormal, which is a more tractable claim.


*Now let's find out what $B$ is. Note that
$$B_{ik} = \sum_{j = 1}^p A_{ij}M_{jk}.$$
Or
$$B_{ik} = \sum_{j = 0}^{p - 1} \binom{i + j - 1}{j}\binom{j}{k - 1}.$$


*The RHS is also a known identity. I'll derive it here. Note
$$\binom{i + j - 1}{j}\binom{j}{k - 1} = \frac{(i + j - 1)!}{(i - 1)!(j - k + 1)!(k - 1)!} = \binom{i + j - 1}{i + k - 2}\binom{i + k - 2}{i - 1}.$$
So we have
$$\sum_{j = 0}^{p - 1} \binom{i + j - 1}{j}\binom{j}{k - 1} = \binom{i + k - 2}{i - 1}\sum_{j = 0}^{p - 1} \binom{i + j - 1}{i + k - 2}.$$
The last sum is familiar
$$\sum_{j = 0}^{p - 1} \binom{i + j - 1}{i + k - 2} = \binom{i + p - 1}{i + k - 1}.$$
So we conclude that
$$\sum_{j = 0}^{p - 1} \binom{i + j - 1}{j}\binom{j}{k - 1} = \binom{i + k - 2}{i - 1}\binom{i + p - 1}{i + k - 1} = \frac{(i + p - 1)!}{(i + k - 1)(p - k)!(i - 1)!(k - 1)!}.$$


*Note that the numerator is always divisible by $p$, while $(p - k)!(i - 1)!(k - 1)!$ is never divisible by $p$. Therefore, this sum is nonzero modulo $p$ if and only if
$$(i + k - 1) = p.$$
In this case, it is now simple to show that modulo $p$,
$$\frac{(i + p - 1)!}{(i + k - 1)(p - k)!(i - 1)!(k - 1)!} \in \{\pm 1\}$$
This is because modulo $p$,
$$(k - 1)!(p - k)! \equiv (-1)^{k}$$
and
$$\frac{(i + p - 1)!}{p} \equiv (p - 1)!(i - 1)! \equiv -(i - 1)!.$$


*We conclude that $B$ is anti-diagonal with elements in $\{-1, 0, 1\}$, so $BB^T = I$.
