An integer square matrix of prime order has size at least $(p-1)\times (p-1)$ There's$\let\geq\geqslant\DeclareMathOperator{\GL}{GL}$ this exercise in my algebra course book:

Let $p$ be a prime and $A\neq I$ an $n\times n$ matrix over $\mathbb Z$ such that $A^p=I$. Prove that $n\geq p-1$.

It's in a section about reducibility of polynomials over $\mathbb Z$. (Gauss' lemma, Eisenstein's criterion etc.) We are also allowed to use some basic properties of UFD's, PID's or Euclidean Domains. The only solution (if it is correct(?)) I could think of is the following:
Let $q$ be a prime which is a primitive root modulo $p$ (which exists by Dirichlet's theorem on AP's). Reducing modulo $q$, $A$ has order $p$ in $\GL(n,q)$. Since $\GL(n,q)$ has order $(q^n-1)(q^n-q)(q^n-q^2)\cdots(q^n-q^{n-1})$, we should have $p\mid q^k-1$ for some $k\in\{1,\ldots,n\}$. Since $q$ is a primitive root modulo $p$, we have $n\geq p-1$.
I don't think this is the intended approach. This has hardly anything to do with polynomials, and Dirichlet's theorem has never been mentioned in our course.
Is there a more elementary way of proving this?
 A: The polynomial $$p(x) = x^{p-1} +x^{p-2} + \ldots +1 $$ is irreducible over $\mathbb{Q}$ ( see cyclotomic polynomials ).
Thus $p(x)$ is the minimal polynomial of $A$ over $\mathbb{Q}$, because $$x^p-1 = (x-1)( x^{p-1} +x^{p-2} + \ldots +1)$$ and $A \neq I $ by hypotheses. 
The roots of $p(x)$ are all differents, the minimal and the characteristic polynomial have the same roots, the degree of the characteristic polyomial is $n$ and thus $n \geq p-1$.
A: Suppose $A$ is such a matrix. Since $A\neq I$ satisfies $A^p-I=0$, the minimal polynomial of $A$ is either $x^{p-1}+\cdots+x+1$ or $x^p-1$ as
\begin{equation}
x^p-1=(x-1)(x^{p-1}+\cdots+x+1)
\end{equation}
with the two polynomials in the right being irreducible. 
(Note that both possibilities may occur. Indeed, if $A^{p-1}+\cdots+A+I=0$, then the matrix $B=\begin{bmatrix}A&0\\0&1\end{bmatrix}$ still satisfies $B^p=I$ while it's minimal polynomial is $x^p-1$ since 
\begin{equation}
B^{p-1}+\cdots+B+I=\begin{bmatrix}O&0\\0&p\end{bmatrix}\neq0.)
\end{equation}
Now the characteristic polynomial of $A$ of degree $n$ is a multiple of the minimal polynomial of $A$, which is of degree $p-1$ or $p$. This shows that $n\geq p-1$ and that $n\geq p$ if $1$ is an eigenvalue of $A$.
