Exercise on elementary number theory Let $a,b,c,d$ integers, $c\not=0$ such that $ad-bc=1$ and $c\equiv 0 \pmod p$ for some prime $p>3$.

Show that if $a+d=\pm1$ then $p\equiv 1\pmod 3$

I don't know how to approach this problem because when I take the expression $ad-bc$ modulo $p$ we have that either $d-d^2\equiv 1\pmod p$ or $d+d^2\equiv 1\pmod p$.
 A: Let's consider:
$ad-bc\equiv1 \pmod p\implies ad=1-bc \equiv 1\pmod p$
$(a+d)^2 \equiv a^2+d^2+2ad\equiv a^2+d^2+2\equiv1\pmod p$
$\implies a^2+d^2+1\equiv 0\pmod p$
$\implies (a^2+d^2+1)^2\equiv 0\pmod p$
Since:
$a+d=\pm1 \implies a\cdot d=(k+1)\cdot(-k)=-k^2-k$
Consider the following table $\pmod 3$
$$\begin{array}{ l | c | r }
  k  &  a  &  d  &  a^2 & d^2 & p \\
 -1  &  0  &  1  &  0   &  1  & 1 \\
  0  &  1  &  0  &  1   &  0  & 1 \\
  1  &  -1 &  -1 &  1   &  1  & 0 \\
\end{array}$$
$\implies p \equiv1 \pmod 3 \quad \square$
A: Given $ad-bc=1$ with $c\equiv 0 \pmod p$ for $p$ a prime exceeding $3$.  If in addition we have $a+d = \pm 1$ then using $a = \pm 1 - d$ in $ad-bc=1$
$$
1 \equiv ad - bc \equiv (\pm 1 - d)d - 0 \equiv \pm d -d^2
\quad \text{or}\quad d^2 \equiv \pm d -1 \pmod p
$$
$$
d^3 \equiv \pm d^2-d \equiv \pm (\pm d - 1)-d \equiv \mp 1 \implies d^6 \equiv 1 \pmod p.
$$
The order of $d \pmod p$ is $1$, $2$, $3$, or $6$.  The above also applies to $a$ so the order of $a$ is also restricted to those four possibilities.  If we knew that there was an element of order $3$ (or $6$) we would be done because then $3 | (p-1)$.  
We need to exclude the cases where the order of $d$ is $1$ or $2$.
If the order of $d$ is $1$ then $d\equiv 1\pmod p$.
Using this together with $a+d = \pm 1$ and the observation that $a\not\equiv 0$ gives that $a\equiv -2$.  So if the order of $d \pmod p$ is $1$ then the order of $a$ is not $1$ or $2$ so $3 | (p-1)$.
Similarly if the order of $d$ is $2$ then $d\equiv -1$ and $a\equiv 2$ and again $3 | (p-1)$.
An all cases $3|(p-1)$ and $p\equiv 1\pmod 3$.
A: Here is an advanced solution based on linear algebra, for fun.
Consider the matrix $A=\pmatrix{ a & b \\ c & d}$ over $\mathbb F_p$.
This matrix is upper-triangular, has trace $\pm1$ and determinant $1$. Moreover, $a$ and $d$ are eigenvalues of $A$. Therefore, they are roots of the characteristic polynomial of $A$, which is $X^2\pm X+1$. Thus, its discriminant $-3$ is a square.
Now, $-3$ is a quadratic residue mod $p$ with $p>3$ iff $p \equiv 1 \bmod 6$. See a proof here.
