Solutions to the equation $x^y \equiv y^x$ in $\mathbb Z / p \mathbb Z$, $p$ prime.

Question

I am looking for the number of integer solutions $(x, y)$ to the equation $$x^y \equiv y^x \mod p, \qquad 0 < x, y < p,$$ where $p$ is a prime number. However, even for small prime, I am having trouble finding all solutions.

In general, I know that $(2k, p - 1)$ and $(p - 1, 2k)$ are solutions due to Fermet's Little Theorem. I also know that $(k, k)$, $(2, 4)$, and $(4, 2)$ are solutions since they are also integers solutions to the equation $x^y = y^x$. But I'm having trouble characterising the other solutions.

For example, for $p = 13$, how would I be able to determine that $(7, 11)$ and $(3, 9)$ (and $(11, 7)$ and $(9, 3)$) are also solutions?

Answer 1

This is more complicated than it looks because solutions to $x^y\equiv y^x\bmod p$ (with $p$ prime) are actually not defined $\bmod p$. They are defined $\bmod p(p-1)$ because the power varies with the residue of the exponent $\bmod p-1$, not $\bmod p$. For instance with $p=13$, $2^5\not\equiv5^2$ but $2^{18}\equiv18^2\bmod13$; so instead of determining whether $\{2,5\}\bmod13$ is a solution we say that $\{2,5\}\bmod156$ is not a solution whereas $\{2,18\}\bmod156$ is one.

This means even with a prime modulus seemingly as small as $13$, the solution process gets a bit unwieldy. I shall explore the solution with a smaller prime, $p=5$, to illustrate what is involved and give an idea of the multitude of solutions that emerge. The discussion here is limited to nonzero residues $\bmod 5$ because zero residue gives problems with the peculiar behavior of $0$ as both a base and an exponent. If we require strictly positive bases and exponents, then all pairs where both elements are zero $\bmod 5$, such as $\{5,10\}\bmod 20$, are added to the solution set derived below for the other residues.

We start by considering solutions for the case $x=1$, meaning $x\equiv1\bmod20$. We set up the equation

$1^y\equiv y^1\bmod5$

and try each nonzero residue $\bmod 5$ for $y$ on the right side. This may be paired with appropriate residues $\bmod4$ for $y$ on the left side to give solutions for $y\bmod20$. Thus $y\equiv1\bmod5$ on the right turns out to work with any residue $\bmod 4$ on the left, and we identify four solutions for $\{x,y\}$:

$\{x,y\}\in\{\{1,1\},\{1,6\},\{1,11\},\{1,16\}\}\bmod 20.$

The other possible residues $\bmod 5$ on the right side can give no more solutions because the left side is forced to $1\bmod 5$.

For $x\equiv2\bmod20$ the equation becomes:

$2^y\equiv y^2\bmod5.$

Now for $y\equiv1\bmod5$ we specifically need $y\equiv0\bmod4$, so we get the single solution $\{x,y\}\equiv\{2,16\}\bmod 20$. Similarly $y\equiv2,3,4\bmod5$ yield respectively $\{2,2\},\{2,18\},\{2,4\}$.

We go through all the residues for $x\bmod 20$ in this way, getting all the pairs indicated in blue for residues that are nonzero $\bmod 5$:

There is no mistake with residue $16\bmod 20$: every natural number $y$ other than multiples of $5$ satisfies $16^y\equiv y^{16}\bmod5$ (all the numbers end with $1$ or $6$ when we represent them in base $10$). Try it with the solution method I give above!