Blargh why am I doing math at ~1:30 AM so often. One can easily check $3,-12$ are not $q^{th}$ power residues modulo $p$ because clearly $p$ does not divide either of $3^2, 12^2$ for $p > 13$ so it follows their orders are either $q$ or $2q$. Note that as $q > 3$ it follows $12$ is not a quadratic residue either so $-12$ is a primitive root modulo $p$. Furthermore note that $q \equiv 5 \pmod{6}$ so it follow $3$ is a quadratic residue and hence has order $q$. Similarly we can show $-4$ is a primitive root. Now, I claim there are $q-1$ solutions. Now: \[3^m + (-12)^m \equiv 3^n + (-12)^n \pmod{p} \] \[1 + (-4)^m \equiv 3^{n-m} + (-4)^n \cdot 3^{n-m} \pmod{p} \] \[ 1 - 3^{n-m} = (-4)^m((-12)^{n-m} - 1) \pmod{p} \] Note that for any value of $n-m < p-1$ which is not $q$, the value of $m$ for which above equation is satisfied is fixed because $-4$ is a primitive root modulo $p$ (and because the order of $-12$ is $p-1$ and order of $3$ is $q$). It immediately follows there are $\frac{p-2-1}{2} = q-1$ solutions (I left out the proof that $n-m = k$ and $n-m = -k$ give the same solutions but its trivial why...) For the Fermat Prime problem I feel like maybe something similar can be done... but its too late (early?) for me to say anything conclusive.

dinoboy wrote: For the Fermat Prime problem I feel like maybe something similar can be done... but its too late (early?) for me to say anything conclusive. It's basically the same idea (same algebraic manipulation), just slightly more technical IIRC. On a side note, Practice Problem 1 here can also be solved with similar manipulation.

Solution to original version: http://www.artofproblemsolving.com/Forum/viewtopic.php?f=56&t=548713&p=3181991#p3181991

The answer is $\boxed{q-1}$. We'll actually show that the number of solutions with $0\le m\ne n<p-1$ is $2(q-1)=p-3$. We claim that exactly of $3$ and $-12$ is a primitive root mod $p$. Note that the order of any residue $x$ must divide $p-1=2q$, so it must be one of $1,2,q,2q$. If it's $1$ or $2$, then the residue is $\pm 1$, which isn't the case here. Thus, the order of $x$ is either $\frac{p-1}{2}$ or $p-1$. Using the fact that \[\left(\frac{x}{p}\right)\equiv x^{\frac{p-1}{2}}\pmod{p},\]we see that $x\ne\pm 1$ is a primitive root if and only if $(\tfrac{x}{p})=-1$. Note that $p\equiv 3\pmod{4}$, so \[\left(\frac{3}{p}\right)\left(\frac{-12}{p}\right)=\left(\frac{-36}{p}\right)=\left(\frac{-1}{p}\right)=-1,\]so one of the Legendere symbols is $-1$ and the other is $1$, as desired. Let $g\in\{3,-12\}$ be the primitive root, and let $h$ be the other one. Since $h$ is a square, we must have $h=g^{2k}$ for some integer $1\le k<q$ and $2k-1\ne q$ (this condition is because $h\not\equiv -g\pmod{p}$). Thus, we wish to find the number of ordered pairs $(m,n)$ with $0\le m\ne n<p-1$ such that \[g^m+(g^m)^{2k}\equiv g^n+(g^n)^{2k}\pmod{p}.\]The key is that $g^m$ uniquely attains each value in the range $[1,p-1]$ mod $p$, so we're actually trying to find the number of pairs $(x,y)$ such that $1\le x,y\le p-1$ and \[x+x^{2k}\equiv y+y^{2k}\pmod{p}.\]We'll show that this restated problem has $p-3$ solutions. Note that this rearranges to \[x^{2k-1}\equiv\frac{(y/x)^{2k}-1}{1-(y/x)}\pmod{p}.\]The right side is defined since $x\ne y$. If $y/x\equiv -1\pmod{p}$, then we would need to have $x=0$, which is not allowed. Thus, $y/x\in\{2,\ldots,p-2\}\pmod{p}$. For each of these, it's not zero since $2k\ne q,2q$. For each value of $y/x$ then, $x$ is uniquely determined since we may raise both sides to the power $(2k-1)^{-1}\pmod{2q}$, and there are $p-3$ values of $y/x$, so there are $p-3$ solutions, as desired. $\blacksquare$

Note $q > 2$, so $p = 2(2k+1)+1 = 4k+3$. Modulo $p$, any number can have order only in $\{1, 2, q, 2q\}$. Note that $3, -12, -4$ don't have order in $\{1, 2\}$. As $-4 = 2^2*(-1)$, it isn't a quadratic residue modulo $p$, so it has order $2q = p-1$ i.e. it is a primitive root. As $-12 = (-4)*3$, exactly one of $-12, 3$ is a quadratic residue, so one of them has order $q$, the other $2q$. We claim that the answer is $q-1$. The required congruence is equivalent to $(3^{n-m}-1) \equiv (-4)^m*(1-12^{n-m})$. Let $d = n-m$. Note $d \neq q$ as that makes exactly one of the LHS or RHS zero. $d$ belongs to $\{1, ..., q-1, q+1, ..., 2q-1\}$. Note $(3^d-1)/(1-12^d) = (-4)^m$ has a unique solution $m$ in ${0, ..., p-2}$, so a fixed $d$ generates at most one solution. If $m+d < p-1$, this generates a unique valid solution $(m, m+d)$, otherwise we have a valid solution $(m+d-(p-1), m)$ which has $m - (m+d-(p-1)) = (p-1)-d$. So at least one of $d, ((p-1)-d)$ generates a solution. Suppose $d$ generates a valid solution $(m, n)$. We prove that $d' = (p-1)-d$ can't generate a valid solution. Suppose the contrary holds, with $(m', m'+d')$ being a valid pair. Then $(3^{(p-1)-d}-1) \equiv (-4)^{m'}(1-12^{(p-1)-d})$, which gives $(-4)^{m'-d} \equiv (-4)^m$, which gives $m' \equiv n$ modulo $(p-1)$. This gives $m' = n$, then $m'+d' = m+d+d' = m + p-1 \ge p-1$, a contradiction. So we're done.

Manipulate \begin{align*} &3^m + (-12^m) = 3^n + (-12)^n\\ \Longleftrightarrow\ & 3^m(1+(-4)^m) = 3^n(1+(-4)^n)\\ \Longleftrightarrow\ & 1+(-4)^m = 3^{n-m}+ 3^{n-m}(-4)^n\\ \Longleftrightarrow\ & 1-3^{n-m} = (-4)^m(-1 + 12^{n-m})\\ \Longleftrightarrow\ & (-4)^m = \frac{-1 + 12^{n-m}}{1-3^{n-m}}. \end{align*}We claim that $\text{ord}_{p}({-4})=p-1$, $\text{ord}_{p}({3}) = \text{ord}_{p}({12}) = \frac{p-1}{2}=q.$ Because $p\equiv 3\mod 4$ (otherwise $\frac{p-1}{2}$ is not prime), $$\bigg(\frac{-4}{p}\bigg) = \bigg(\frac{-1}{p}\bigg) = -1,$$so $\text{ord}_{p}({-4})=p-1$. Because $p\equiv 2\mod 3$ (otherwise $\frac{p-1}{2}$ is not prime), $$\bigg(\frac{12}{p}\bigg) = \bigg(\frac{3}{p}\bigg) = -\bigg(\frac{p}{3}\bigg) = 1,$$so $\text{ord}_{p}({3}) = \text{ord}_{p}({12}) = q.$ The above claim means that once we fix $n-m\neq 0$ (modulo $q$), $m$ is uniquely determined. Therefore there are $q-1$ ordered pairs of solutions.

Rewrite the equation $3^n+(-12)^n\equiv 3^m+(-12)^m\pmod{p}$ as \[3^m-3^n\equiv 3^m\left(1-3^{n-m}\right) \equiv 3^m \cdot (-4)^m ((-12)^{n-m}-1) \equiv (-12)^n-(-12)^m.\]Equivalently, we have \[1-3^{n-m}\equiv (-4)^m \cdot ((-12)^{n-m}-1).\]This formulation makes it clear that equality holds iff $(-12)^{n-m}\equiv 3^{n-m}\equiv 1\pmod{p}$ or \[(-4)^m\equiv \frac{1-3^{n-m}}{(-12)^{n-m}-1}\pmod{p}.\] Claim: We have that $-4$ is a primitive root modulo $p$. Solution: Note that $-4$ could have period $\{1,2,q,2q\}$. As it is not a quadratic residue, it has period in $\{1,2,2q\}$. Since neither $-4-1=-5$ nor $(-4)^2-1=15$ could be $0\pmod{p}$, we get that $-4$ has period $2q$ modulo $p$, so it is a primitive root as desired. $\fbox{}$ Note that this claim implies that we cannot have $(-12)^{n-m}\equiv 3^{n-m}$. Then, for any value of $n-m$ with $3^{n-m},(-12)^{n-m}\not\equiv 1\pmod{p}$, we get a unique value of $m$. Claim: Both $3$ and $-12$ have period $q$ or $2q$ modulo $p$. Solution: We prove this in two parts, first for $3$ then for $-12$. If $3$ had period $1$ or $2$ we would get $p\mid 3^2-1=8$, absurd. If $-12$ had period $1$ or $2$ we would get $p\mid 12^2-1=11\cdot 13$, absurd. $\fbox{}$ Note that in fact, exactly one of $\{3,-12\}$ has period $q$ while the other has period $2q$ because $3\cdot (-4)=-12$ and $-4$ is a primitive root. Thus, we have $(-12)^{n-m},3^{n-m}\not\equiv 1\pmod{p}$ precisely when $n-m\not\equiv 11,0\pmod{2q}$. Then, we get $2q-2$ distinct values of $n-m$ that generate a unique value of $m$. However, this does not guarantee that $n<m$, so by symmetry we can halve this value to get $q-1$ choices of $n$ and $m$ satisfying the desired criteria.

All equivalences are in $\pmod{p}$. The condition can be equivalently reduced as follows: \begin{align*} 3^m + (-12)^m \equiv 3^n + (-12)^n&\iff 3^n-3^m \equiv (-12)^m-(-12)^n \\ &\iff 3^{n-m}-1 \equiv (-4)^m\left(1-(-12)^{n-m}\right) \\ &\iff (-4)^m \equiv -\frac{1-3^d}{1-(-12)^d}, \qquad (\spadesuit) \end{align*}where $d=n-m\not = 0$. Call a pair $(m,d)$ valid if it satisfies $(\spadesuit)$. First note that $(m,d)$ being valid is equivalent to $(m',d')$ being valid for any $m'\equiv m \pmod{p-1}$ and $d'\equiv d\pmod{p-1}$. So assume $0\le m,d \le p-2$. Let $\ell$ be the order of $-4\pmod{p}$. Fix $d$. If $(m,d)$ is valid, then $(m+i\ell,d)$ is valid for any $i\ge 0$. In particular, the following are all valid \[ (m,d), \ (m+\ell,d), \ (m+2\ell,d), \ldots, (m+\left(\tfrac{p-1}{\ell}-1\right)\ell, d)\]and the first elements are pairwise distinct $\pmod{p-1}$. Create a graph with nodes $\{0,1,\ldots,p-2\}$ and an edge between $m$ and $d$ is $(m,d)$ is valid. For every solution $(m,n)$ to the original equation with $m<n$, there will be exactly one edge in the graph. Claim: In fact, $\ell=p-1$. Proof: We are given that $p-1=2q$ for some prime $q$. Since $\ell\mid p-1$, we must have $\ell \in \{1,2,\tfrac{p-1}{2},p-1\}$. The order cannot be 1 or 2 since $p>13$. Suppose $\ell = \tfrac{p-1}{2}$. Then \[ 1 \equiv (-4)^{\tfrac{p-1}{2}} \equiv \left(\frac{-4}{p}\right)=\left(\frac{-1}{p}\right). \]Since $-1$ is a QR $\pmod{p}$, we must have $p\equiv 1\pmod4$. But $p=2q+1\equiv 3\pmod4$ since $q$ is odd, contradiction. Hence $\ell=p-1$. $\blacksquare$ By the claim, we conclude the graph is a 1-regular graph, but since $d\not = 0$, two vertices are isolated. Therefore here are $\tfrac{p-3}{2}$ edges, and hence there are $\tfrac{p-3}{2}$ solutions.

Manipulating, \begin{align*} &3^m + (-12^m) = 3^n + (-12)^n\\ \Longleftrightarrow\ & 3^m(1+(-4)^m) = 3^n(1+(-4)^n)\\ \Longleftrightarrow\ & 1+(-4)^m = 3^{n-m}+ 3^{n-m}(-4)^n\\ \Longleftrightarrow\ & 1-3^{n-m} = (-4)^m(-1 + 12^{n-m})\\ \Longleftrightarrow\ & (-4)^m = \frac{-1 + 12^{n-m}}{1-3^{n-m}}. \end{align*}Claim: $(-4)$ is a quadratic non-residue $\pmod p$ Proof: It is pretty well know that $-4$ is a quadratic residue $\pmod p$ if and only if $p \equiv 0 \pmod 4$ but over here $p \equiv 3 \pmod 4$ hence $-4$ is a quadratic non residue modulo $p$ Claim:$-4$ is a primitive root modulo $p$ Proof:Let $\ell=\text{ord}_p(-4)$. Suppose $\ell = \tfrac{p-1}{2}$. Then\[ 1 \equiv (-4)^{\tfrac{p-1}{2}} \equiv \left(\frac{-4}{p}\right)=\left(\frac{-1}{p}\right). \]Since $-1$ is a QR $\pmod{p}$, we must have $p\equiv 1\pmod4$. But $p=2q+1\equiv 3\pmod4$ since $q$ is odd, contradiction. Hence $\ell=p-1$. $\blacksquare$ Clearly this implies $2q-2$ solutions to $m,n$ i.e $q-1$ solutions discounting repeated pairs.

The answer is $q-1$. Note that we must have $p \equiv 2 \pmod{3}$, otherwise $3 \mid q$, and $p \equiv 3 \pmod{4}$, otherwise $2 \mid q$. As such, $$-\left(\frac{3}{p}\right)=\left(\frac{3}{p}\right)\left(\frac{p}{3}\right)=-1,$$hence $3$ is a QR, so we have $\mathrm{ord}_p(3)=q$ since we obviously don't have $p \mid 3-1$. Further, $-1$ is an NQR, so $-4$ and $-12$ are both NQRs as well. This is enough to imply that $-4,-12$ are both primitive roots $\pmod{p}$, since we can't have $p \mid 4^2-1$ or $p \mid 12^2-1$. With all this in mind, first disregard the requirement that $m<n$ and let $m>n$ (but not $m=n$), and let $0 \neq a=m-n$, so \begin{align*} 3^m+(-12)^m &\equiv 3^n+(-12)^n & &\pmod{p}\\ 3^m(1-3^a) &\equiv (-12)^m((-12)^a-1) & &\pmod{p}\\ (-4)^m &\equiv \frac{1-3^a}{(-12)^a-1} & &\pmod{p}. \end{align*}Therefore, for any $0 < a < p-1$ with $a \neq q$, there exists a unique value for $0 \leq m < p-1$ that works, while no solution exists for $a=q$. Reducing the working value of $m$ modulo $p-1$, it follows that there are $p-3$ pairs $(m,n)$ that work where we can have $m<n$. By symmetry this means that there are $\frac{p-3}{2}=q-1$ solutions $(m,n)$ with $0 \leq m<n<p-1$, as desired. $\blacksquare$

Fairly clear and straightforward. Claim. $-4$ is a primitive root mod $p$. Proof. Note $\left(\frac{-4}p\right) = -\left(\frac 2p\right)^2$ is always negative as $p \equiv 3 \pmod 4$. This means that $(-4)^q \equiv -1 \pmod p$ by Euler's criterion, which is enough. $\blacksquare$ Now rewrite the congruence as $$3^k \equiv \frac{1+(-4)^m}{1+(-4)^n} \pmod p$$where $k = n-m$. Note that by the claim, for each $k \neq q$, there exists a solution $(m, n)$ to this congruence. On the other hand, by symmetry, half of those solutions satisfy $m < n$ for each $0 < k < p-1$, so there are $\frac{p-3}2 = q-1$ solutions.

Answer: $p-3$. Note that $p = 2q + 1$, so $p \equiv 3 (4)$ and $p \equiv 2 (3)$. Thus $\left( \frac{3}{p} \right) = 1$ and $\left( \frac{-12}{p} \right) = \left( \frac{-3}{p} \right) = -1$, so $-12$ is a primitive root of $p$. And since $\left( \frac{3}{p} \right) = 1$, so there exists $k$ such that $3 \equiv (-12)^{2k} (p)$. Thus the given congruence becomes $(-12)^{2km} + (-12)^{m} \equiv (-12)^{2kn} + (-12)^{n} (p)$. Since $(-12)$ is a primitive root of $p$, so $(-12)^{n}$ can take any value modulo $p$, except $0$, so we only have to find the ordered pairs of integers $(a, b)$ such that $0 < a < b \le p-1$ such that $a^{2k} + a \equiv b^{2k} + b (p)$. Note that the above congruence is equivalent to $\frac{(\frac{a}{b})^{2k} - 1}{(\frac{a}{b}) - 1} \equiv -\frac{1}{b^{2k - 1}} (p)$. It's not hard to see that $b^{2k-1}$ can take any value except $0$, and $(\frac{a}{b})$ can take any value except $1, p-1$, so $\frac{a}{b}$ can take $p-3$ value and every value of $\frac{(\frac{a}{b})^{2k} - 1}{(\frac{a}{b}) - 1}$, $-\frac{1}{b^{2k - 1}}$ is uniquely determined modulo $p$, so there are exactly $p-3$ solutions. This completes proof. $\blacksquare$

First notice that $p \equiv -1 \pmod{12}$, and $\operatorname{ord}_pa = 1,2,q,2q$ for any $a \not\equiv 0 \pmod p$. We now find specific orders: \begin{align*} &\left(\frac 3p\right) = - \left(\frac p3\right) = -\left(\frac 23\right) = 1 \implies \operatorname{ord}_p(3) = q \\ &\left(\frac{-4}{p}\right) = \left(\frac{-1}{p}\right) \left(\frac 4p\right) = -1 \implies \operatorname{ord}_p(-4) = 2q \\ &\left(\frac{-12}{p}\right) = \left(\frac 3p\right) \left(\frac{-4}{p}\right) = -1 \implies \operatorname{ord}_p(-12) = 2q. \end{align*} We can now rearrange our equation to \[3^{n-m}-1 \equiv (-4)^m \left(1-(-12)^{n-m}\right) \pmod p.\] We have no solutions for $q \mid m-n$ as we discovered that -12 is a primitive root while 3 is not. Otherwise, we have \[(-4)^m \equiv \frac{3^{n-m}-1}{1-(-12)^{n-m}} \pmod p.\] Since -4 is a primitive root, for each value of $n-m \not\equiv 0 \pmod q$, we have exactly one solution for $m$. Including the $m<n$ condition, this gives a total of $\tfrac{2q-2}{2} = \boxed{q-1}$ solutions. $\blacksquare$

The answer is $q-1$, which follows from the claim that each residue $\pmod{p-1}$ except $0,q$ occurs congruent to the difference $n-m$ exactly once, and each pair $m,n$ gives two differences unless they are $0,q$. Note that since $\left(\frac{-4}p\right)=\left(\frac{-1}p\right)=-1$, the order of $-4 \pmod p$ is even and divides $2q$. Since $p\ne 3,5$ the order must be $2q=p-1$ so $-4$ is a primitive root $\pmod p$. Next $3^m+(-12)^m\equiv 3^{m+k}+(-12)^{m+k}$ rearranges to $\frac{3^k-1}{1-(-12)^k}\equiv(-4)^m\pmod p$. Since $-4$ is a primitive root, there is exactly one solution when $3^k-1,1-(-12)^k\not\equiv0\pmod p$. Similar to above, we have $\left(\frac3p\right)=-\left(\frac p3\right)=1$ so $3$ has order $q$ and $-12$ has order $2q$. Thus for all $k\not\equiv0,q\pmod{p-1}$ we have exactly one solution. When $k\equiv q\pmod{p-1}$ we have $0\equiv(-4)^m\pmod p$, impossible. When $k\equiv 0\pmod{p-1}$ we have $m=n$, impossible. Thus we are done.

$ $

Note that a residue $\pmod{p}$ is a primitive root if and only if its order is not a factor of $2q$ other than $2q$, or if its order is not $1,2,$ or $q$, or if it is not $1$ or $-1$ and it is a quadratic nonresidue. Note that since $\tfrac{p-1}{2}=q$ is odd since $p\ne5$ meaning that $q\ne2$ we have that $p\equiv3\pmod{4}$, so $-1$ is a quadratic nonresidue $\pmod{p}$, so $\tfrac{-12}{3}=-4$ is a quadratic nonresidue $\pmod{p}$. This means that exactly one of $3$ and $-12$ is a primitive root $\pmod{p}$ and the other has order $\tfrac{p-1}{2}=q$ modulo $p$ since $3,-12\not\equiv1,-1\pmod{p}$. Let $c\in\{3,-12\}$ be a primitive root $\pmod{p}$ and let $d\in\{3,-12\}$ have order $q$ modulo $p$. Now, we will consider sequences $$f(a,b,n)\equiv{}a\cdot{}c^n-b\cdot{}d^n\pmod{p}$$for integers $n$, where $a$ and $b$ are not $0\pmod{p}$. Claim $1$. All such sequences have period $p-1$. Proof. Consider one such sequence and let it have period $P$. We see that $a\cdot{}c^n-b\cdot{}d^n\equiv{}a\cdot{}c^{n+P}+b\cdot{}d^{n+P}\pmod{p}$ for all integers $n$, or $$a\left(c^P-1\right)\equiv\frac{d^n}{c^n}\cdot{}b\left(d^P-1\right)\pmod{p}.$$Since $\tfrac{c}{d}\not\equiv1\pmod{p}$, by varying $n$ we see that we must have that $$a\left(c^P-1\right)\equiv{}b\left(d^P-1\right)\equiv0\pmod{p}.$$Since $a\not\equiv0\pmod{p}$ we must have that $c^P-1\equiv0\pmod{p}$, so $P\equiv0\pmod{p-1}$ since $c$ is a primitive root $\pmod{p}$. Now, we see that the equivalence holds for $P=p-1$ by Fermat's little theorem, proving the claim. Claim $2$. Over all choices of $a$ and $b\pmod{p}$, we get $p-1$ sequences up to translation, all overcounted exactly $p-1$ times, with any two sequences being multiples of each other up to translation $\pmod{p}$. Proof. Note that there is a bijection between choices of $a$ and $b\pmod{p}$ and choices of $f(a,b,0)\equiv{}a-b$ and $f(a,b,1)\equiv{}ac-bd\pmod{p}$. Then, note that $f$ satisfies the recursion $$f(a,b,n+2)\equiv-9f(a,b,n+1)+36f(a,b,n)\pmod{p},$$so there is a bijection between choices of $f(a,b,0)$ and $f(a,b,1)\pmod{p}$ and sequences $\cdots,f(a,b,-1),f(a,b,0),f(a,b,1),\cdots$, and as such sequences have period $p-1$ by claim $1$, there is a $p-1$ to $1$ correspondence between such sequences and such sequences up to translation. This implies that we have a $p-1$ to $1$ correspondence between choices of $a$ and $b\pmod{p}$ and sequences $\cdots,f(a,b,-1),f(a,b,0),f(a,b,1),\cdots$ up to translation, giving $\tfrac{(p-1)^2}{p-1}=p-1$ sequences up to translation. Now, note that these sequences are covered with the sequences corresponding to $a\equiv{}b\pmod{p}$, so any two such sequences are multiples of each other up to translation $\pmod{p}$. Now, we will find the number $N$ of ordered pairs $(m,n)$ with $m,n\in\left\{0,1,\cdots,p-2\right\}$ and $m\ne{}n$ such that $$f(a,b,m)\equiv{}f(a,b,n)\pmod{p}.$$Since all sequences $\cdots,f(a,b,-1),f(a,b,0),f(a,b,1),\cdots$ are multiples of each other up to translation, this number does not depend on $a$ and $b$. This means that $N$ is $\tfrac{1}{(p-1)^2}$ times the number of ordered tuples $(a,b,m,n)$ with $a$ and $b$ nonzero residues $\pmod{p}$ and $m,n\in\left\{0,1,\cdots,p-2\right\}$ with $m\ne{}n$ so that $$f(a,b,m)\equiv{}f(a,b,n)\pmod{p},$$or $$a\cdot{}c^m-b\cdot{}d^m\equiv{}a\cdot{}c^n-b\cdot{}d^n\pmod{p},$$or $$a\left(c^m-c^n\right)\equiv{}b\left(d^m-d^n\right)\pmod{p}.$$Now, since $m$ and $n$ are distinct, we see that since $c$ is a primitive root $\pmod{p}$ that $c^m-c^n\not\equiv0\pmod{p}$. This implies that there is a unique choice $b$ given $a$ for any $m$ and $n$ such that $d^m-d^n\not\equiv0\pmod{p}$, or $m\not\equiv{}n\pmod{q}$ since $d$ has order $q$ modulo $p$. There are then $p-1$ choices for $m$, then $p-3$ choices for $n$, then $p-1$ choices for $a$, giving $(p-1)^2(p-3)$ ordered tuples $(a,b,m,n)$. This means that $N=\tfrac{1}{(p-1)^2}\cdot(p-1)^2(p-3)=p-3$. Now, taking $a\equiv1\pmod{p}$ and $b\equiv-1\pmod{p}$, we get that there are $p-3$ ordered pairs $(m,n)$ with $m,n\in\left\{0,1,\cdots,p-2\right\}$ and $m\ne{}n$ such that $$3^m+(-12)^m\equiv3^n+(-12)^n\pmod{p},$$so there are $\tfrac{p-3}{2}=\boxed{q-1}$ ordered pairs $(m,n)$ with $m,n\in\left\{0,1,\cdots,p-2\right\}$ and $m<n$ satisfying this equivalence.