4

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?
abiessu
  • 8,115
  • 2
    For any $p$, $(2^p-1,2^n)=1$, in particular for $n=1,2$ so you can write $$m^2=(i+2^{-1})^2=-3\cdot 4^{-1}\mod 2^p-1$$ and it becomes a problem w.r.t to residues $\mod 2^p-1$. – Pedro Feb 06 '14 at 16:54
  • 2
    I don't know if you used 'suppose further' to imply that it was an extra hypothesis needed, but it's easy to show that you must have $k^3\equiv 1$; $k^3-1=(k^2+k+1)(k-1)\equiv 0$. – Steven Stadnicki Feb 06 '14 at 16:54
  • @StevenStadnicki: perfect, that makes sense, I was wondering why whenever I found two such numbers they would always have that condition of $k^3\equiv (k+1)^6\equiv 1$... – abiessu Feb 06 '14 at 17:10
  • @PedroTamaroff: I'm not sure I follow; I'll have to work on that a bit. Do you have any way of clarifying how you got that modular equation or how it relates to my questions? – abiessu Feb 06 '14 at 17:15
  • @PedroTamaroff: ok, between your comment and the accepted answer, I believe I understand this better now. Sadly, it seems that although the equation is somewhat interesting in its own right, I cannot use it to short-circuit the calculation of $3^{2^{p-1}-1}$ as was my original intent and as detailed in the answer that I added. – abiessu Feb 09 '14 at 19:22

2 Answers2

4

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$

Bill Dubuque
  • 272,048
  • To clarify, the discriminant in this case is $b^2-4ac$, correct? – abiessu Feb 06 '14 at 17:42
  • Yes, $,\ 0\equiv f(i) = i^2+i+1\iff 0\equiv 4f(i) = (2i+1)^2+3\iff (2i+i)^2\equiv -3,$ by completing the square, and using: $,2,$ is invertible so cancellable modulo odd $,m,$ (which implies that $\ x\equiv 0 \iff 2x\equiv 0 \iff 4x\equiv 0)\ \ $ – Bill Dubuque Feb 06 '14 at 17:48
1

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.

abiessu
  • 8,115