2
$\begingroup$

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!

$\endgroup$
7
  • $\begingroup$ Keywords: discrete logarithm. In general, this is a computationally hard problem. $\endgroup$ Aug 20, 2020 at 8:13
  • 1
    $\begingroup$ @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$. $\endgroup$ Aug 20, 2020 at 8:18
  • $\begingroup$ @JaapScherphuis You are correct. My bad. Still, finding primitive roots afaik is also computationally difficult. $\endgroup$ Aug 20, 2020 at 8:23
  • $\begingroup$ but what is $L$? $\endgroup$ Aug 20, 2020 at 8:38
  • $\begingroup$ @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. $\endgroup$ Aug 20, 2020 at 8:47

3 Answers 3

2
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ $p$ is likely odd, so the gcd is a multiple of 2, and then -1 is a not quite trivial solution. $\endgroup$ Aug 20, 2020 at 8:53
  • $\begingroup$ 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}$ $\endgroup$ Aug 20, 2020 at 9:54
2
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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 $\endgroup$ Aug 20, 2020 at 13:57
  • $\begingroup$ $\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 $\endgroup$
    – GreginGre
    Aug 20, 2020 at 14:56
  • $\begingroup$ 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) $\endgroup$
    – GreginGre
    Aug 20, 2020 at 15:03
  • $\begingroup$ Thanks, much clearer now! Will see if this works :) $\endgroup$ Aug 20, 2020 at 16:25
1
$\begingroup$

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)
$\endgroup$
7
  • $\begingroup$ 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$. $\endgroup$ Aug 20, 2020 at 9:23
  • $\begingroup$ Oh yes, correct code. $\endgroup$ Aug 20, 2020 at 9:42
  • $\begingroup$ 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. $\endgroup$ Aug 20, 2020 at 9:52
  • $\begingroup$ Ok, more true say as: $(p,n)$=(31,3)=(31,3+j*31), where $j$=0,1,2,3,.... Becose calculation by modulo $p$. $\endgroup$ Aug 20, 2020 at 10:17
  • $\begingroup$ 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? $\endgroup$ Aug 20, 2020 at 10:28

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.