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

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ $p$ is likely odd, so the gcd is a multiple of 2, and then -1 is a not quite trivial solution. $\endgroup$ – Jaap Scherphuis Aug 20 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$ – MC From Scratch Aug 20 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

| cite | improve this answer | |
$\endgroup$
  • $\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$ – MC From Scratch Aug 20 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 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 at 15:03
  • $\begingroup$ Thanks, much clearer now! Will see if this works :) $\endgroup$ – MC From Scratch Aug 20 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)
| cite | improve this answer | |
$\endgroup$
  • $\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$ – Jaap Scherphuis Aug 20 at 9:23
  • $\begingroup$ Oh yes, correct code. $\endgroup$ – Dmitry Ezhov Aug 20 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$ – MC From Scratch Aug 20 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$ – Dmitry Ezhov Aug 20 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$ – MC From Scratch Aug 20 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.