How to prove that a quaternion algebra over ℤₚ is isomorphic to Mat₂(ℤₚ) for p prime? How to prove without using advanced theorems that quaternions algebra $H = \genfrac(){}{}{-1,-1}{\mathbb{Z}_p}$, where $p$ is prime that $H \cong\operatorname{Mat}_2({\mathbb{Z}_p})$?
My ideas: I tried to build an explicit isomorphism, but as I think it is only possible when $p = 1 \pmod 4$, and for $p = 1 \pmod 4$ it get it.
In my second attempt, I tried to look at them as vector spaces of the same dimension.
 A: A quaternion algebra with center $F$ that is not a division ring is isomorphic to ${\rm M}_2(F)$. See Theorem 4.21 and Corollary 4.24 here.  Let's show when $F = \mathbf F_p$ (field of order $p$) for $p > 2$ that
there is a zero divisor
in the Hamilton quaternion over $\mathbf F_p$, so it is not a division ring. (I avoid $p=2$ because the Hamilton quaternions over a field of characteristic $2$ are not a central simple algebra. The formula-based definition of quaternion algebras in characteristic $2$ is not the same as outside characteristic $2$, just like comparing formulas for Kummer theory in and not in characteristic $2$.)
We want to find a nonzero element $a + bi + cj+  dk$ where $a^2 + b^2 + c^2 + d^2 = 0$.  Well, it turns out in $\mathbf F_p$ that we can always solve $a^2 + b^2 + 1 = 0$ by rewriting the equation as $a^2 = -1-b^2$ and seeing that each side has $(p+1)/2$ possible values (there are $(p+1)/2$ total squares mod $p$, including $0$) so there is an overlap in values on both sides by the pigeonhole principle. For such $a$ and $b$, $a + bi + j$ is a nonzero zero divisor in the quaternions over $\mathbf F_p$.
A: At the risk of being redundant and repeating earlier answers, let me mention that this is explicitly contained in the book "Elementary number theory, group theory and Ramanujan graphs" by Davidoff, Sarnak and Valette, as Proposition 2.5.2:

A: Yes, you can do this without any advanced theorems.
Does $\mathbb{Z}\mathbb{p}$ mean the ring $\mathbb{Z}_p$ of $p$-adic integers or the finite field $\mathbb{Z}/p\mathbb{Z}=\mathbb{F}_p$ with $p$ elements?
I think it's the latter, because then you can still talk about quaternion algebras without any advanced theorems--you want the base to be a field!
Recall that the quaternion algebra $(-1,-1\,|\,\mathbb{F}_p)$ is the algebra with basis $1,i,j,ij$ satisfying $i^2=j^2=-1$ and $ji=-ij$.  To make an isomorphism to $\mathrm{M}_2(\mathbb{F}_p)$, you basically need to send $i,j$ to matrices whose squares are $1$ and that skew commute.  Play around a bit and I think you'll see the way.
If you're stuck, check out the proof of Lemma 11.2.1 in my book (http://quatalg.org).
A: As Keith Conrad says, use the pigeonhole principle to find $a$ and $b$ satisfying $a^2+b^2+1 \equiv 0 \bmod p$. Set
$$I = \begin{bmatrix} 0&-1 \\ 1&0 \end{bmatrix} \qquad J = \begin{bmatrix} a&b \\ b&-a \end{bmatrix} \qquad K = \begin{bmatrix} -b&a \\ a&b  \end{bmatrix}.$$
Then $I$, $J$ and $K$ obey the quanternion relations. So we have a map from $\mathbb{H}/p \mathbb{H}$ to $\text{Mat}_{2 \times 2}(\mathbb{F}_p)$ sending $i \mapsto I$, $j \mapsto J$ and $k \mapsto K$.
Assuming that $p \neq 2$, the four matrices $\text{Id}_2$, $I$, $J$ and $K$ are a basis for the vector space of $2 \times 2$ matrices, so this map is an isomorphism.

Remark: I assumed that your $\mathbb{Z}_p$ meant $\mathbb{Z}/p \mathbb{Z}$. If you meant the $p$-adics, this solution also works: You can find a solution to $a^2+b^2+1=0$ modulo $p$ by the pigeonhole principle and then lift it to the $p$-adics by Hensel's lemma.
Remark: When $p \equiv 1 \bmod 4$, you can take $a$ to be a square root of $-1$ and $b=0$, and thus recover the standard the standard description of the quaternions in terms of Pauli matrices.
