# Number of solutions to a modular congruence

What methods are there for determining the number of solutions to modular congruences of the form $a^m \equiv b^n k \pmod{p}$ with $1 \leq a,b \leq p-1$ where $p$ is a prime?

In the case $m,n$ are coprime we can do the following.

We see that the condition in question is equivalent to $a^m b^{-n} \equiv k \pmod{p}$ from which we obtain a bijective mapping $(a,b) \mapsto (a,b^{-1})$ and so an equivalent number of solutions to $a^m b^n \equiv k \pmod{p}$.

Lemma. For any prime $p$ and integers $k,m,n$ with $k \nmid p$ and $(m,n)=1$, the number of solutions to $a^mb^n \equiv k \pmod p$ with $1 \le a,b \le p-1$ is equal to $p-1$.

Proof. Let $s_k$ be the number of solutions to this equation. We have $\sum_{k} s_k=(p-1)^2$ and since $m,n$ are coprime we obtain using Bézout's Identity that there exist integers $x,y$ such that $mx+ny = 1$. Now letting $k,k'$ be arbitrary integers with $q \equiv \dfrac{k'}{k} \pmod{p}$ and $1 \leq k' \leq p-1$, we see that for any solution $(a,b)$ to $X^m Y^m \equiv k \pmod{p}$, $(aq^x, bq^y)$ is a solution to $X^m Y^n \equiv k' \pmod{p}$. Since the mapping $(a,b) \mapsto (aq^x,bq^y)$ is bijective we conclude that $s_k = s_k'$. Thus, all the number solutions for $k$ are equal and we have $(p-1)s_k = (p-1)^2$ and thus $s_k = p-1$. $\square$

Question: What can we do in the case $m,n$ aren't coprime?

• What is fixed, and what is moving? Are $m,n,k,p$ all given, and the question is how many pairs $(a,b)$? – Gerry Myerson May 25 '16 at 23:24
• @GerryMyerson That's right. Also, I made a typo and meant $m,n$ to be coprime. – user19405892 May 25 '16 at 23:28

If $m=m'd, n=n'd$ with $(m',n')=1$ then $a^{m'}b^{-n'}$ is equidistributed on $\{1,...,p-1\}$. So, $a^mb^{-n} = (a^{m'}b^{-n'})^d$ is equidistributed on the nonzero $d$th powers.
• How can you conclude $(a^{m'}b^{-n'})^d$ is equidistributed on the nonzero $d$th powers? – user19405892 May 26 '16 at 17:50
• Units that are $d$th powers are $d$th powers in exactly $(d,p-1)$ ways. Since this is constant on the nonzero $d$th powers, equidistribution on $\{1,...,p-1\}$ pushes forward to equidistribution on nonzero $d$th powers. – Douglas Zare May 26 '16 at 17:57