Solving $n^{15} \equiv p - 1 \space \pmod p$ for $n \in [1 , L]$

Question

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!

Answer 1

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

Answer 2

Not need $L>p-1$, becose result repeated.

pari-gp code:

 forprime(p=3, 100,
  for(n=2, p-1,
   m= Mod(n,p);
   h= znorder(m);
   k= znlog(p-1,m,h);
   if(k, if(15%h==k, print("("p", "n")")))
  )
 )

Output $(p,n)$:

(3, 2)
(5, 4)
(7, 3)
(7, 5)
(7, 6)
(11, 2)
(11, 6)
(11, 7)
(11, 8)
(11, 10)
(13, 4)
(13, 10)
(13, 12)
(17, 16)
(19, 8)
(19, 12)
(19, 18)
(23, 22)
(29, 28)
(31, 3)
(31, 6)
(31, 11)
(31, 12)
(31, 13)
(31, 15)
(31, 17)
(31, 21)
(31, 22)
(31, 23)
(31, 24)
(31, 26)
(31, 27)
(31, 29)
(31, 30)
(37, 11)
(37, 27)
(37, 36)
(41, 4)
(41, 23)
(41, 25)
(41, 31)
(41, 40)
(43, 7)
(43, 37)
(43, 42)
(47, 46)
(53, 52)
(59, 58)
(61, 3)
(61, 4)
(61, 5)
(61, 14)
(61, 19)
(61, 27)
(61, 36)
(61, 39)
(61, 41)
(61, 45)
(61, 46)
(61, 48)
(61, 49)
(61, 52)
(61, 60)
(67, 30)
(67, 38)
(67, 66)
(71, 14)
(71, 17)
(71, 46)
(71, 66)
(71, 70)
(73, 9)
(73, 65)
(73, 72)
(79, 24)
(79, 56)
(79, 78)
(83, 82)
(89, 88)
(97, 36)
(97, 62)
(97, 96)

Answer 3

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