If I have the congruence
$$m^2 \equiv -1 \pmod {2k+1}$$
how do I solve for the solutions to this congruence (given that I know $k$)?
Modular Arithmetic – How to Handle Negative Numbers
elementary-number-theorymodular arithmetic
Related Solutions
Finding the solution to $$x \times 41 \equiv 1 \pmod {99}$$ is equivalent to asking for the multiplicative inverse of $41$ modulo $99$. Since $\gcd(99,41)=1$, we know $41$ actually has an inverse, and it can be found using the Extended Euclidean Algorithm:
\begin{align*} 99-2 \times 41 &= 17 \\ 41-2 \times 17 &= 7 \\ 17-2 \times 7 &= 3 \\ 7-2\times 3 &= 1 &=\gcd(99,41). \\ \end{align*} Going back, we see that \begin{align*} 1 &= 7-2\times 3 \\ &= 7-2\times (17-2 \times 7) \\ &= 5 \times 7-2\times 17 \\ &= 5 \times (41-2 \times 17)-2\times 17 \\ &= -12 \times 17+5 \times 41 \\ &= -12 \times (99-2 \times 41)+5 \times 41 \\ &= 29 \times 41-12 \times 99 \\ \end{align*} Hence $29 \times 41 \equiv 1 \pmod {99}$ and thus $x=29$.
In the second case, we have $$7x+9y \equiv 0 \pmod {31}$$ and $$2x-5y\equiv 2 \pmod {31}.$$ Here we want to take $7x+9y=0 \pmod {31}$ and rearrange it to get $x \equiv ?? \pmod {31}$, then substitute it into the other equation and solve for $y$. This requires finding the multiplicative inverse of $7$ modulo $31$ (which we can do as above). It turns out $7 \times 9 \equiv 1 \pmod {31}$. Hence \begin{align*} & 7x+9y=0 \pmod {31} \\ \iff & 7x \equiv -9y \pmod {31} \\ \iff & x \equiv -9y \times 9 \pmod {31} \\ \iff & x \equiv 12y \pmod {31}. \end{align*} We then substitute this into the equation $2x-5y\equiv 2 \pmod {31}$, which implies $$2 \times 12y-5y \equiv 2 \pmod {31}$$ or equivalently $$19y \equiv 2 \pmod {31}.$$ Yet again, we find a multiplicative inverse, this time of $19$ modulo $31$, which turns out to be $18$. So \begin{align*} & 19y \equiv 2 \pmod {31} \\ \iff & y \equiv 2 \times 18 \pmod {31} \\ \iff & y \equiv 5 \pmod {31}. \end{align*} Hence $$x \equiv 12y \equiv 29 \pmod {31}.$$ Thus we have the solution $(x,y)=(29,5)$.
Prime factorization is required for finding all solutions.
As pointed out in the comments, if we know the prime factorization of $n$, then we can find the solutions of $x^2 - x \equiv 0 \pmod n$ using the Chinese remainder theorem. For example, if $n$ is a semiprime $pq$, then the four solutions are $x \equiv 0, 1, p^{q-1}, q^{p-1} \pmod n$.
Conversely, if we know one of the nontrivial solutions $x \not\equiv 0, 1 \pmod n$, then $\gcd(x, n)$ is a nontrivial factor of $n$. So any algorithm for finding these solutions is effectively an algorithm for factoring $n$.
Best Answer
As others have pointed out, when dealing with congruences the concept of a negative number is meaningless (as is the concept of a positive number). Judging from the comments you are, in addition to this, asking about the solvability of the congruence $m^2\equiv -1\pmod q$, where $q$ is some odd integer. Here the theory says that this congruence has solutions, if and only if all the prime divisors of $q$ are congruent to $1\pmod 4$.
For example, when $q=7$ there are no solutions, because $7\not\equiv1\pmod4$, but when $q=13$, there are solutions $m\equiv\pm5$. When $q$ is a prime, $m=\pm((q-1)/2)!$ are the only non-congruent solutions.
The general theory goes via the usual route: solve it for prime number moduli => solve for prime power moduli (by "lifting") => solve for general moduli with the aid of Chinese remainder theorem. The number of non-congruent solutions depends on the number of prime factors of $q$.
[Edit: In response to Thomas' comment.] If $m^2\equiv-1\pmod q$, then this can be lifted to a solution modulo $q^k$ for all positivie integers $k$. Lifting means that if we have, for some positive integer $k$, a solution $m_k$ such that $m_k\equiv m\pmod q$ and $m_k^2\equiv -1\pmod{q^k}$, then we can find an integer $m_{k+1}$ such that $m_{k+1}=m_k+aq^k$ and $m_{k+1}^2\equiv -1\pmod{q^{k+1}}$. This is not difficult, because we know that $m_k^2=-1+bq^k$ for some integer $b$, and can use this to solve $a$ from the congruence $$ m_{k+1}^2=m_k^2+2am_kq^k+a^2q^{2k}\equiv-1+(b+2am_k)q^k\pmod{q^{k+1}}, $$ because this is equivalent to the linear congruence $$ b+2am_k\equiv0\pmod q. $$ Here $\gcd(2m_k,q)=1$ so the solutions $a$ of this congruence form a unique residue class modulo $q$.
As an example, let us lift the solution $m=m_1=5$ of the congruence $m^2\equiv -1\pmod{13}$ to a square root of $-1$ modulo $13^2$. Here $m_1^2=25=-1+2\cdot13$, so $b=2$. We want to solve the linear congruence $$ b+2am_1=2+2\cdot5a\equiv0\pmod{13}. $$ The usual method for solving a linear congruence yields $a\equiv5\pmod{13}$ as the solution. Therefore $m_2=5+13a=5+5\cdot13=70$ should be a solution. Indeed, $$ m_2^2=4900=-1+4901=-1+13\cdot377=-1+13^2\cdot29\equiv-1\pmod{13^2}. $$ [/Edit]
[Edit^2: An example on using the CRT] Assume that we are given the task to solve the equation $$ m^2\equiv-1\pmod{2873}.\tag{1} $$ The process begins by factoring $2873$. If you know this an advance, you are lucky, because otherwise this could be tricky. We simply observe that $2873=13^2\cdot17$. It is our lucky day, because all the prime factors are $\equiv 1\pmod 4$ (of course I reverse engineered this example a bit). The idea is that we next solve the congruences $$ m^2\equiv-1\pmod{13^2}\tag{2} $$ and $$ m^2\equiv -1\pmod{17}\tag{3}$$ separately. In the previous example I showed how to lift the "guessable" solution $5^2\equiv1\pmod{13}$ to a solution $m=70$ of equation $(2)$, so let's reuse that. We observe that $-70\equiv99\pmod{13^2}$ is then the other solution of $(2)$.
Finding the solutions of $(3)$ is also easy, because $17$ is a relatively small number. There are several methods. Either we simply observe that $m=\pm4$ are solutions. Or, as above, we can calculate that $(17-1)/2=8$ and $8!=40320\equiv 13\equiv-4\pmod{17}$. We can also use the quicker (for primes a bit larger than $17$) but non-deterministic method that for any integer $a, 0<a<17$, the power $x=a^{(p-1)/4}=a^4$ is a solution of either the equation $x^2\equiv1$ or $x^2\equiv-1$. The non-deterministic part is that we don't know which it is. Let's try. With $a=2$ we get $x=16\equiv-1$, which is not a solution of $(3)$. But with $a=3$ we get $x=81\equiv13\equiv-4$, which we already knew to be a solution. Anyway, we now know that $(3)$ holds, if and only if $m\equiv\pm4\pmod{17}.$
Because $17$ and $13^2$ are coprime (no common prime factors), the Chinese remainder theorem tells us that $m$ satisfies congruence $(1)$, if and only if it satisfies both congruences $(2)$ and $(3)$. We can also conclude from CRT that there is a single residue class modulo $2873$ that satisfies e.g. both congruences $m\equiv70\pmod{13^2}$ and $m\equiv 4\pmod{17}$. The extended Euclidean algorithm gives us a method for finding integers $u$ and $v$ such that $$u\cdot 169+v\cdot 17=1,$$ for example $u=-1,v=10$. What this means is that the number $e_1=v\cdot17=170$ is congruent to $1$ modulo $13^2$ to $0$ modulo $17$, and OTOH the number $e_2=u\cdot169=-169$ is congruent to $0$ modulo $13^2$ and to $1$ modulo $17$. Therfore $$m_1=70\cdot e_1+4\cdot e_2=70\cdot170-4\cdot169=11224\equiv2605\pmod{2873}$$ is congruent to $70$ modulo $13^2$ and to $4$ modulo 17. So it should be a solution to $(1)$. With the aid of a calculator we can check $$ 2605^2=6786025\equiv-1\pmod{2873}, $$ so this is, indeed a solution. Using other solution to congruences $(2)$ and $(3)$ we get a total of of four non-congruent solutions: $$ m_2=99\cdot e_1+4\cdot e_2=16154\equiv1789\pmod{2873}$$ is congruent to $99$ modulo $13^2$ and to $4$ modulo $17$. Using the residue class $-4$ modulo $17$ gives us two more solutions $$ m_3=70\cdot e_1-4\cdot e_2=12576\equiv 1084\pmod{2873},$$ and $$m_4=99\cdot e_2-4\cdot e_2=17506\equiv 268\pmod{2873}.$$