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!

• Keywords: discrete logarithm. In general, this is a computationally hard problem. – Paco Adajar Aug 20 at 8:13
• @PacoAdajar Discrete log is where you want to find the exponent. Here the exponent is known, namely 15. This problem is about extracting the $15$th root of $-1$ in the integers mod $p$. – Jaap Scherphuis Aug 20 at 8:18
• @JaapScherphuis You are correct. My bad. Still, finding primitive roots afaik is also computationally difficult. – Paco Adajar Aug 20 at 8:23
• but what is $L$? – Dmitry Ezhov Aug 20 at 8:38
• @DmitryEzhov $L$ is just a limit for the integers to search. It has nothing special about it nor a specific value, but it is large enough to require a computer. Other integers for which the equation holds that are larger than $L$ might exist, but I am not interested in them. I have updated the question to clarify this. – MC From Scratch Aug 20 at 8:47

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

• $p$ is likely odd, so the gcd is a multiple of 2, and then -1 is a not quite trivial solution. – Jaap Scherphuis Aug 20 at 8:53
• Thank you very much, this certainly simplifies the searching process. Didn't think of the simplification of the equation to $n^{30}\equiv 1\pmod{p}$ – MC From Scratch Aug 20 at 9:54

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

• Some of it might be beyond me, and I don't fully understand. What are the $\phi$'s exactly? The $X$'s? Also, isn't Tonelli-Shanks algorithm only viable for square roots? We're trying to find the 15th root here. Perhaps I don't 100% follow you. Would appreciate a little further explanation – MC From Scratch Aug 20 at 13:57
• $\Phi_n$ is the $n$th cyclotomic polynomial, and $X$ is just an indeterminate. No need really to know how they are defined, I gave the formulas. But I have reformulated my answer without using these polynomials...And yes, Tonelli Shanks is here to find square roots, but if you read my answer , you will see that some square roots are needed to compute the solutions of your equations – GreginGre Aug 20 at 14:56
• For example, for $m^2+m+1=0 \pmod p$, it will have a solution iff $p=1 \mod 3$. In this case, you will need a square root of $-3$ modulo $p$, and a solution will be $(-1+\sqrt{-3})/2$ (where $\sqrt{-3}$ is the square root modulo $p$ you computed) – GreginGre Aug 20 at 15:03
• Thanks, much clearer now! Will see if this works :) – MC From Scratch Aug 20 at 16:25

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)

• You're missing some solutions, e.g. $6, 15, 23, 26, 27, 29, 30$ for $p=31$. In general $p-1$ is always a solution, even for primes which are not of the form $30k+1$. – Jaap Scherphuis Aug 20 at 9:23
• Oh yes, correct code. – Dmitry Ezhov Aug 20 at 9:42
• What do you mean by "result repeated"? Also, $L$ may be far larger than $p$. Sorry if it's unclear, will include it now in the question. – MC From Scratch Aug 20 at 9:52
• Ok, more true say as: $(p,n)$=(31,3)=(31,3+j*31), where $j$=0,1,2,3,.... Becose calculation by modulo $p$. – Dmitry Ezhov Aug 20 at 10:17
• Yes I can see it now, wrote a program myself. So it seems I only need to find the solutions $n \lt p$. For small $p$ it is easy, but for large $p$ it takes a very long time. Any idea how to quickly find all such solutions? – MC From Scratch Aug 20 at 10:28