<s>[INST] Is it possible to solve $i^2+i+1\equiv 0\pmod{2^p-1}$ in general? 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?

 [/INST] 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.
</s>