5. Let $p>13$ be a prime of the the form $2 q+1$, where $q$ is prime. Find the number of ordered pairs of integers $(m, n)$ such that $0 \leq m<n<p-1$ and
$$
3^{m}+(-12)^{m} \equiv 3^{n}+(-12)^{n} \quad(\bmod p)
$$
Solution:
Lemma 1: -4 is a primitive root modulo $p$.
Proof of Lemma 1: Note that $\operatorname{ord}_{p}(-4) \mid p-1=2 q$, so ord ${ }_{p}(-4)$ is one of $1,2, q, 2 q$. Because $-4 \not \equiv 1(\bmod p)$ we have $\left.\operatorname{ord}_{p}(-4) \neq q\right)$. As $16=4^{n} \not \equiv 1(\bmod p)$, we have $\operatorname{ord}_{p}(-4) \neq 2$.

Also, we have
$$
\left(\frac{-4}{p}\right)=\left(\frac{-1}{p}\right) \cdot\left(\frac{4}{p}\right)=-1 \cdot 1 \cdot-1,
$$
since $\left(\frac{-1}{p}\right)=1$ follows from $p>13 \Rightarrow \frac{p-1}{2}=q$ being odd.
Thus, following from the fact that -4 is not a quadratic residue modulo $p$, we have that
$$
\begin{array}{c}
2 \times \frac{p-1}{\operatorname{ord}_{p}(-4)}=\frac{2 q}{\operatorname{ord}_{p}(-4)} \\
\Rightarrow 2 \cdot \operatorname{ord}_{p}(-4) \nmid 2 q \\
\Rightarrow \operatorname{ord}_{p}(-4) \nmid \chi
\end{array}
$$

Consequently, ord ${ }_{p}(-4)=2 q$, as desired.
Lemma 2: The order of 3 modulo $p$ is exactly $q$.
Proof of Lemma 2: Note that $\operatorname{ord}_{p}(3) \mid p-1=2 q$, so ord $(3)$ is one of $1,2, q, 2 q$. Because $3 \not \equiv 1(\bmod p)$, we have $\operatorname{ord}_{p}(3) \neq 1$. As $3^{2}=9 \not \equiv 1(\bmod p)$, we have $\operatorname{ord}_{p}(3) \neq 2$. Then, we have
$$
\begin{aligned}
p & =2 q+1 \\
& \equiv 2 \cdot 1+1 \text { or } 2 \cdot 2+1 \quad(\bmod 3) \\
& \equiv 0 \text { or } 2 \quad(\bmod 3)
\end{aligned}
$$

Because $p>13$, we know that $q \neq 3$ and $p \neq 3$, giving
$$
\left(\frac{p}{3}\right)=\left(\frac{2}{3}\right)=1
$$

Also, by quadratic reciprocity, we have
$$
\begin{aligned}
\left(\frac{3}{p}\right) \cdot\left(\frac{p}{3}\right) & =(-1)^{\frac{(3-1)(p-1)}{4}} \\
\left(\frac{3}{p}\right)(-1) & =(-1)^{q} \\
& =-1 \\
\Rightarrow\left(\frac{3}{p}\right) & =1 .
\end{aligned}
$$

We now know that 3 is a quadratic residue modulo $p$, so ord $(3) \neq 2 q$, giving us ord $_{p}(3)=q$, as desired.
Lemma 3: -12 is a primitive root modulo $p$.
Proof of Lemma 3: Note that $\operatorname{ord}_{p}(-12) \mid p-1=2 q$, so ord $(-12)$ is one of $1,2, q, 2 q$. Because $-12 \not \equiv 1(\bmod p)$, we have $\operatorname{ord}_{p}(-12) \neq 1$. As $(-12)^{2}=144 \not \equiv 1(\bmod p)$, we have $\operatorname{ord}_{p}(-12) \neq 2$. Then, after substituting for the values found in Lemma 1 and Lemma 2, we obtain
$$
\begin{aligned}
\left(\frac{-12}{p}\right) & =\left(\frac{-1}{p}\right) \cdot\left(\frac{4}{p}\right) \cdot\left(\frac{3}{p}\right) \\
& =(-1) \cdot(1) \cdot(1) \\
& =-1
\end{aligned}
$$

Thus, -12 is not a quadratic residue modulo $p$, giving us
$$
\begin{array}{c}
2 \times \frac{p-1}{\operatorname{ord}_{p}(-12)}=\frac{2 q}{\operatorname{ord}_{p}(-12)} \\
\Rightarrow \operatorname{ord}_{p}(-12) \nless q
\end{array}
$$

It follows that ord ${ }_{p}(-12)=2 q$, as desired.
Main Proof: We now simplify the given equation:
$$
\begin{aligned}
3^{m}+(-12)^{m} & \equiv 3^{n}+(-12)^{n} & (\bmod p) \\
& \equiv 3^{n-m} \cdot 3^{m}+3^{n-m} \cdot 3^{m} \cdot(-4)^{n} & (\bmod p) \\
1+(-4)^{m} & \equiv 3^{n-m}+3^{n-m} \cdot(-1)^{n} & (\bmod p) \\
1-3^{n-m} & \equiv 3^{n-m} \cdot(-4)^{n}-(-4)^{m} & (\bmod p) \\
& \equiv(-4)^{m} \cdot\left((-12)^{n-m}-1\right) & (\bmod p) .
\end{aligned}
$$

We ignore for the moment the condition that $m<n$ and count all pairs $m, n \in \mathbb{Z}_{p-1}=\mathbb{Z}_{2 q}$. So, if $n \neq \equiv m(\bmod 2 q)$, then $(-12)^{n-m}-1 \not \equiv 0(\bmod p)$, giving us
$$
(-4)^{m} \equiv\left(1-3^{n-m}\right)\left((-12)^{n-m}-1\right)^{-1} \quad(\bmod p) .
$$

Because -4 is primitive modulo $p$, we have that any non-zero residue of $(-4)^{m}(\bmod p)$ uniquely determines the residue of $m(\bmod 2 q)$. So each non-zero residue of $n-m(\bmod 2 q)$ uniquely determines $m(\bmod 2 q)$, so long as
$$
3^{n-m}-1 \not \equiv 0 \quad(\bmod p) \Leftrightarrow q \backslash h n-m .
$$

Consequently, for each $(n-m) \in\{1,2, \ldots, q-1, q+1, q+2, \ldots, 2 q-1\}(\bmod 2 q)$, we unitely determine the ordered pair $(m, n) \in \mathbb{Z}_{2 q}^{2}$. However, on taking remainders on divison by $2 q$ of $m, n$, we must have $m<n$. Thus, for each $x \not \equiv q, 0$, the solutions for $n-m \equiv x(\bmod 2 q)$ and $n-m \equiv-1(\bmod 2 q)$ give exactly 1 solution $(m, n)$ with $m<n$.
Thus, we have a total of $\frac{2 q-2}{2}=q-1$ solutions.
This problem was proposed by Alex Zhu.