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$
2
  • $\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$ May 25, 2016 at 23:24
  • $\begingroup$ @GerryMyerson That's right. Also, I made a typo and meant $m,n$ to be coprime. $\endgroup$ May 25, 2016 at 23:28

1 Answer 1

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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