Solving $n^{15} \equiv p - 1 \space \pmod p$ for $n \in [1 , L]$ For a given prime $p$, and an upper limit $L$ of integers that I am interested in, I am trying to find all values of $n$ in the range $[1,L]$ for which the following equation holds:
$$n^{15} \equiv p - 1 \space \pmod p $$
I am trying to come up with a method to systematically find all the solutions, perhaps a parametrization to a family of solutions (or families). I was thinking of something along the lines of Euler phi function $\varphi (n)$ and the Carmichael function $\lambda (n)$ as possible directions since the term $p-1$ appears, but I can't attach those to the equation in any way yet.
Note: there are probably more $n \gt L$ for which the equation holds, but I am not interested in them. Also, it is important to clarify that $L$ may be far larger than $p$. So $L$ can be regarded as arbitrary, although too large to search in using manual methods.
Perhaps another function exists which relates to this, or a direction that I miss. I am looking for an insight or a point in the right direction/reference to the field I should study. Thank you!
 A: If I understand the question:
$n^{15}\equiv p-1\equiv -1 \pmod{p}$
means
$n^{30}\equiv 1\pmod{p}$
That is that the order of $n\pmod{p}$ must divide $30$.
Using Fermat's little theorem you can say that if $\gcd(p-1,30)=1$ then there are no solutions.
For the remaining $p$ you only need to check if $n^{\gcd(p-1,30)}=1\pmod{p}$ because otherwise either the order will not divide $30$ or it will not divide $p-1$.
A: If $p=2$, this is trivial, so assume that $p$ is odd.
Setting $m=-n$, you want to solve $m^{15}-1\equiv 0 \pmod p$, that is you want to to find the solutions of $m^{15}-1=0$ in $\mathbb{F}_p$.
This may be rewritten as $(m-1)(m^2+m+1)(m^4+m^3+m^2+1)=0$ in $\mathbb{F}_p$. Since $p$ is prime, it is equivalent to say that one of the factors is $0$.
SO you need to solve $m=1 \pmod p$, $m^2+m+1=0 \pmod p$, $m^4+\cdots+m+1=0 \pmod p$.
For each equation, if you have a root $m$, the other ones are the successive powers of $m$, so you just need to find one.
For, you can get inspired by the complex roots.
For $m^2+m+1=0$, a complex root is $\dfrac{-1+\sqrt{-3}}{2}$. Morally speaking (this can be proved in a rigorous way), this equation will have a root mod $p$ if and only if $-3$ is a square mod $p$.
Using Legendre symbol, we see that it the case if and only if, either $p=3$ (in this case $m=1$ mod $3$) or $p\equiv 1 \pmod 3$ (using Legendre symbol). In the last case, you have Tonelli-Shanks algorithm to extract a square root of $-3$ modulo $p$, and $m=\dfrac{-1\pm \sqrt{-3}}{2} \pmod p$ (where $1/2$ is an inverse of $2$ mod $p$, which is $(p-1)/2$ mod $p$, in fact).
For the last one it is a bit more subtle. A complex root of $m^4+\cdots+m+1=0$ is $\cos(2\pi/5)+i\sin(2\pi/5)$.
Set $c=\cos(2\pi/5)=\dfrac{-1+\sqrt{5}}{4}$. Then the complex root above is just $c+\sqrt{c^2-1}$.
Once again, we will have a solution mudlo $p$ if and only if $5$ is square modulo $p$. This is equivalent to, either $p=5$ (in this case $m=1$ mod $5$) or $p\equiv 1 \pmod 5$ (standard result in algebraic number theory of cyclotomic fields).
Then, you compute $c$ modulo $p$, using Tonelli-Shanks algorithm to extract a square root of $5$mod $p$, and you compute a square root of $c^2-1$ using the same algorithm. Then $m=c+\sqrt{c^2-1}$.
Tonelli-Shanks: https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm
