3
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ If $p$ is coprime with $q-1$ you can get a very good one. $\endgroup$
    – Asinomás
    Jul 22, 2021 at 2:51
  • 1
    $\begingroup$ That is true, I guess I was considering mainly cases where p can divide the order of elements. $\endgroup$
    – Tejas Rao
    Jul 22, 2021 at 3:31

1 Answer 1

1
+50
$\begingroup$

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$).

$\endgroup$

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.