Count $(a,b)$ pairs such that $a^b\equiv 2 \pmod{p}$ I am working on a problem that requires to count the number of pairs $(a,b)$ such that $$a^b\equiv 2 \pmod{p}$$
Conditions being : 
$0<a,b<p$
($p$ is a known prime)
Of course I can check all $(a,b)$ pairs to count them but I am looking for some efficient way to count $(a,b)$ pairs.  
 A: As suggested, I compose my comments into an answer.
Given any prime number $p$, there is a theorem which says that there always exists a primitive root, i.e. an element $g$ mod $p$ whose multiplicative order is $p-1$. For example, if $p=7$ then a primitive root is $3$. In fact most of the elements mod $p$ will be primitive roots and it is very easy to find one in practice by trail and error. The existence of this element is very useful if you want to "take a logarithm", as I will now illustrate.
Since $g$ is of order $p-1$, and there are exactly $p-1$ element in the multiplicative group mod $p$, it follows that any nonzero element mod $p$ is a power of $g$. Thus in particular (unless $p=2$) there must be some $t$ such $g^t = 2$. Since you are imposing the condition $a\neq 0$, we can put $a =g^x$, and the equation you want to solve becomes $g^{xb}=g^t \mod p$, or equivalently, $g^{xb-t} = 1 \mod p$. Now the point is that since $g$ has order $p-1$, this is equivalent to the equation $xb\equiv t \mod p-1$, so it suffices to count the number of solutions in $x$ and $b$ to this equation. 
This is now just a linear equation mod $p-1$, so for a given $b$ let $d = \gcd(b,p-1)$, then there are no solutions if $d$ does not divide $t$, and if it does, there are $d$ solutions. Thus the number of solutions is $$\sum_{b=1}^{p-1} \gcd(b,p-1)\delta_{gcd(b,p-1)|t}$$ (here as usual, $\delta_{\gcd(b,p-1)|t}$ is $1$ if $\gcd(b,p-1)$ divides $t$ and $0$ otherwise).
For example, let us check this is consistent for what happens in the case $p=7$. As I have said, in this case one may take $3$ as a primitive root. Since $3^2 \equiv 2 \mod 7$, we take $t=2$. Hence the number of solutions should be $$\sum_{b=1}^{6} \gcd(b,6)\delta_{\gcd(b,6)|2} = 1\cdot1+2\cdot1+3\cdot0+2\cdot1+1\cdot1+6\cdot0=6,$$
and indeed, an easy search by computer or by hand validates that the solutions are $$(a,b) \in \{(2,1),(2,4),(3,2),(4,2),(4,5),(5,4)\}.$$
