Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?
share|improve this question
1  
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 Tamaroff Feb 6 at 16:54
1  
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 6 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 6 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 6 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 9 at 19:22

2 Answers 2

up vote 3 down vote accepted

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$

share|improve this answer
    
To clarify, the discriminant in this case is $b^2-4ac$, correct? –  abiessu Feb 6 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 6 at 17:48

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.