2

I am trying to compute the number of solutions of the following system of equations over a finite field $\mathbb{F}_q$ ($q$ may be considered odd prime power or just odd prime if needed): $$ x^m \neq y^m,\\ z^n = w^n = t^n, $$ where all $x$, $y$, $z$, $w$ and $t$ are distinct, $1\le m,n\le q-1$ are two given integers. My idea was to split this into three cases:

1) $x^m \neq z^n$ and $y^m = z^n = w^n = t^n$;

2) $x^m \neq z^n$ and $y^m \neq z^n = w^n = t^n$;

1) $x^m = z^n$ and $y^m \neq z^n = w^n = t^n$.

So, in case 1) we have $y^m = z^n$. The idea is to fix some element $a\in\mathbb{F}_q$ which is simultaneously an $m$-th and an $n$-th power (of possibly two different field elements). The number of such $a$'s is easy to compute. Then we need to count in how many ways, for a fixed $a$, we can choose $y$ and $z$ such that $y^m = a = z^n$. The problem here is that I don't quite understand how to figure out the number of ways in which $x$ may be chosen. So it seems necessary to know the cardinality of the set $\{u\in\mathbb{F}_q\colon u^m = u^n = a \}$.

To compute this latter quantity, assume $g$ is any fixed generator of $\mathbb{F}_q^*$, and write $a = g^i$, $u = g^k$, where the number of possible values of $1\le k\le q-1$ is to be found. Then having $u^m = u^n = a$ is equivalent to the following system of congruences: $$ mk\equiv i\mod q-1,\\ nk\equiv i\mod q-1. $$ One necessary condition for a solution to exist follows immediately: we must have that $lcm((q-1,m),(q-1,n))$ divides $i$. At this point things become increasingly messier. We first divide the two congruences by $(q-1,m)$ and $(q-1,n)$ respectively: $$ m'k\equiv i_1\mod \frac{q-1}{(q-1,m)},\\ n'k\equiv i_2\mod \frac{q-1}{(q-1,n)}, $$ where $m' = \frac{m}{(q-1,m)}$, $n' = \frac{n}{(q-1,n)}$, $i_1 = \frac{i}{(q-1,m)}$, $i_2 = \frac{i}{(q-1,n)}$. As $m'$ and $n'$ are coprime with $\frac{q-1}{(q-1,m)}$ and $\frac{q-1}{(q-1,n)}$, respectively, we can write $$ k \equiv i_1 [m']^{-1}_{\frac{q-1}{(q-1,m)}} \mod \frac{q-1}{(q-1,m)}\\ k \equiv i_2 [n']^{-1}_{\frac{q-1}{(q-1,n)}} \mod \frac{q-1}{(q-1,n)}, $$ where $[x]^{-1}_n$ denotes the inverse modulo $n$ of $x$. A solution of the last system exists if and only if $$ i_1 [m']^{-1}_{\frac{q-1}{(q-1,m)}} \equiv i_2 [n']^{-1}_{\frac{q-1}{(q-1,n)}} \mod (\frac{q-1}{(q-1,m)},\frac{q-1}{(q-1,n)}). $$ It is unique modulo $lcm(\frac{q-1}{(q-1,m)},\frac{q-1}{(q-1,n)})$. So, it is not quite clear how to count the exact number of them.

If anyone knows of any paper where the number of solutions of $x^m = x^n = a$ in a finite field is obtained, please let me know. If anyone sees a quicker more optimal way of counting the number of solutions to the initial problem, please share your thoughts.

azazello
  • 21
  • If $(k,q-1)=1$, then $x\mapsto x^k$ is a bijection, as you have observed. I think that this means that you can reduce to a case, where both $m$ and $n$ are factors of $q-1$. Apart from the possibility of zero being a solution we are essentially working inside a cyclic group here - you only work with the multiplicative structure of the field in an equation that does not involve sums. – Jyrki Lahtonen Nov 28 '13 at 19:58
  • Thank you for you comment, Jyrki. Would you please elaborate on it though? Even if $(q-1,m) = (q-1,n) = 1$ we can have $u^m = u^n$ for nontrivial values of $u$ (that is, different from -1, 0 or 1). – azazello Nov 28 '13 at 21:56
  • Sure we can. But if $d=(m,q-1)$, then $m\equiv dm_1\pmod{q-1}$ for a suitable integer $m_10$ such that $(m_1,q-1)=1$. Then $x\mapsto x^{m_1}$ is a bijection. Consequently $x^m\neq y^m$, iff $x^d\neq y^d$. Similarly, if $e=(n,q-1)$, then $z^n=w^n=t^n$ iff $z^e=w^e=t^e$. Counting the number of solutions of this latter system should not be too difficult. Ignoring the solution $z=w=t=0$ for a moment, we see that we only need $w/z$ and $t/z$ to be $e$th roots of unity, and there are $e$ of those in $\Bbb{F}_q^*$. Thus $q-1$ choices for $z$ and for a fixed $z$ $e$ choices for both $w$ and $t$. – Jyrki Lahtonen Nov 28 '13 at 22:29
  • (cont'd) So the total number of solutions of $z^n=w^n=t^n$ would be $1+(q-1)e^2$. Similarly for the inequality $x^d\neq y^d$ there are $q-1$ choices for $y$, when $x=0$. But if $x\neq0$ we only need to exclude that possibility that $y/x$ is a $d$th root of unity leaving us $q-d$ choices for $y$. So the inequality has $(q-1)+(q-1)(q-d)=(q-1)(q-d+1)$ solutions. The pairs $(x,y)$ are independent from $(w,z,t)$, so this suggests $$(q-1)(q-d+1)[1+(q-1)e^2]$$ as the total. Does that match with any of the numerical data you have? – Jyrki Lahtonen Nov 28 '13 at 22:32
  • Oops! Rereading your question shows that we need all of them to be distinct. I missed that somehow. Now I see why it is trickier. Sorry. Need to hit the sack now. Will check this tomorrow. Need to think about it more. – Jyrki Lahtonen Nov 28 '13 at 22:36
  • I think I've computed the number of solutions to $u^n = u^m = a$ for a fixed $a$. It's either 0, or $|I_m\cap I_n|$, where $I_k$ is the set of roots of 1 of degree $k$. This latter quantity is equal to $\frac{q-1}{(q-1,lcm(\frac{q-1}{(q-1,m)},\frac{q-1}{(q-1,n)})}$. (follows from the fact that $I_k$ is a group, and if $x$ is an element of a group, then $\langle x^n \rangle \cap \langle x^m \rangle = \langle x^{lcm(m,n)} \rangle$). – azazello Nov 29 '13 at 04:50

0 Answers0