Size constraints on reduced solutions to $x^p\equiv 1\mod q$

166 Views Asked by At

Are there any size constraints on the reduced solutions $x$, $(0<x<q)$, to $x^p\equiv 1\mod q$, for $p$ and $q$ specific primes? (Considering the primitive $p$-th roots of unity modulo $q$).

I can see that $x>q^{1/p}$ as $x^p>q$. Also for $p=2$, the solutions are simply $\pm 1$. Besides these, can anything be said so far about the lower or upper bounds?

1

There are 1 best solutions below

0
On BEST ANSWER

A very partial answer. As has been pointed out, for $p\nmid q-1$ the only such $x$ is $1$, and the problem is not very interesting. So, assume $p\mid q-1$.

Let $1<x_1<q$ be a non-unit solution to $x^p\equiv 1\pmod q$, and define $$x_n=x_1^n\operatorname{rem}q$$ ($\operatorname{rem}$ denotes remainder), so that $\{1=x_0,x_1,\dots,x_{p-1}\}$ are the unique values of $x$ between $0$ and $q$ satisfying $x^p\equiv 1\pmod q$. We have $$1+x_1+x_2+\cdots+x_{p-1}\equiv 0\pmod q.$$ This implies that $$\max_{1\leq i\leq p-1}x_i\geq \frac{q-1}{p-1}\qquad \min_{1\leq i\leq p-1}x_i\leq q-1-\frac{q-2}{p-1}.$$ This isn't a particularly strong bound, but it's better than $q^{1/p}$. (Ifyou want, by using that the $x_i$ are distinct, you can improve it by about $p/2$, which does nothing for large $q$ and fixed $p$ but might be interesting if $p$ grows with $q$.)

In the special case of $p=3$, the values $x_1$ and $x_2$ satisfy $x_2=p-1-x_1$, and so we can study the distribution of all $x_i$ by simply studying the roots of the quadratic $x^2+x+1$. By a result of Duke, Friedlander, and Iwaniec, such roots have $x_i/q$ uniformly distributed in $(0,1)$ as $q$ grows, and so the roots can be arbitrarily closely clustered to $p/2$, or arbitrarily close to $0$ and $1$ (as constants times $q$).