0
$\begingroup$

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?

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

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.

$\endgroup$
  • $\begingroup$ How can you conclude $(a^{m'}b^{-n'})^d$ is equidistributed on the nonzero $d$th powers? $\endgroup$ – user19405892 May 26 '16 at 17:50
  • $\begingroup$ 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. $\endgroup$ – Douglas Zare May 26 '16 at 17:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.