Is it possible to solve $i^2+i+1\equiv 0\pmod{2^p-1}$ in general?

Question

While looking at the Mersenne numbers (for prime $p$, the number $2^p-1$), I noticed that only certain of them had any solution to the modular equation $i^2+i+1\equiv 0\pmod{2^p-1}$, e.g., $p=3,5,7,13,17,19,31,37,...$ but not $p=11,23,29,...$.

I have gotten as far as realizing that if $k$ is a solution then so is $-k-1$.

Questions:

• Is it possible to solve this modular equation (assuming there is a solution) in general given these restrictions?
• Suppose that for a given $p$ there is a solution $k$ such that $k^2+k+1\equiv 0\pmod{2^p-1}$; then $k\cdot(k+1)\equiv -1\pmod{2^p-1}$. Then (as noted in a comment) $k^3\equiv -(k+1)^3\equiv 1\pmod{2^p-1}$. Is it possible to conclusively prove whether $k$ or $k+1$ is a quadratic non-residue from this information?

Answer 1

Hint $\ $ If the quadratic is solvable then its discriminant $\,-3\,$ is a square mod $\,n = 2^p-1,\,$ so it remains a square mod each prime $\,q\mid n.\,$ But $\,-3\,$ is a square mod prime $q\iff q=1\pmod 3.\,$ Now, notice that the cases that you list having no roots all have prime factors $\ q = -1 \pmod 3,\,$ namely $2^{11}-1 = 23\cdot 89,\,\ 2^{23}-1 = 47\cdot 178481,\ldots$

Answer 2

Just as an alternate view of the particular solutions to this modular equation, if $$k^2+k+1\equiv 0\pmod q$$ then $$k^2\equiv -k-1\pmod q$$ so that solution is a quadratic residue $\mod q.$ Taking note of the comments, we have $$(k^2+k+1)(k-1)=k^3-1\implies k^3\equiv 1\pmod q$$ Since we also have $$k(k+1)\equiv -1\pmod q$$ then $$k^3(k+1)^3\equiv -1\pmod q$$ or $k^3\equiv -(k+1)^3\pmod q.$ Multiplying both sides by $k$ yields $$k^4\equiv k\equiv -k\cdot (k+1)\cdot(k+1)^2\equiv (k+1)^2\pmod q$$ thus showing that $k$ is also a quadratic residue.

Based on this success, consider whether $\exists m:m^2\equiv k+1\pmod q$ or $\exists n:n^2\equiv -k\pmod q.$ In the first case, note that $$m^2\equiv k+1\implies (k+1)^2m^2\equiv (k+1)^3\equiv -1\pmod q$$ and in the second case note that $$n^2\equiv -k\implies k^2n^2\equiv -k^3\equiv -1\pmod q$$ so the quadratic residue status of $k+1$ and $-k$ is the same as that of $-1.$ The real modulus is $2^p-1$ which is of the form $4s+3,$ which does not have $-1$ as a quadratic residue.

Taking this one step further (and using the solution $m^2\equiv -3\pmod q$ mentioned in the comments and the other answer), we have Lagrange's formula for the value of $m$ for $m^2=(2i+1)^2\equiv -3\pmod {2^p-1}$ which is $m\equiv \pm (-3)^{2^p-1+1\over 4}=\pm 3^{2^{p-2}}$. This is also obvious since $3$ is a quadratic non-residue $\pmod {2^p-1}$ and thus $3^{2^{p-1}-1}\equiv -1\pmod {2^p-1}$. Now we have that $i=2^{-1}\cdot(\pm 3^{2^{p-2}}-1)$.

The futility of attempting to use the solutions of $i^2+i+1\equiv 0\pmod{2^p-1}$ to reduce the computing time required for $3^{2^{p-1}-1}\pmod{2^p-1}$ is now readily apparent.