Modular arithmetic for negative numbers 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$)?
 A: Negative, schmegative. $a\equiv b\pmod n$ means $b-a$ is a multiple of $n$, and it doesn't matter whether $a$ and/or $b$ is positive, negative, or zero. 
A: (This is Jyrki's answer with all of the examples removed, because it apparently confuses the OP when numbers are "pulled out of a hat":)
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$.
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$.
Lifting: 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^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$.
A: I discuss the solution method here, involving the Chinese Remainder Theorem, Wilson's Theorem, Hensel's Lemma, and Quadratic Reciprocity, and provide some explicit formulas for calculation:

  
*
  
*To compute $n_p$ (for each prime $p|m$), we use this fact: $$\begin{array}{c l} (p-1)! & \equiv 1\cdot 2\cdots\frac{p-1}{2}\frac{p+1}{2}\cdots (p-1) \\ 
& \equiv 1\cdot 2\cdots\frac{p-1}{2}\left(p-\frac{p-1}{2}\right)\cdots\big(p-(1)\big) \\ 
& \equiv \left(\frac{p-1}{2}\;!\right)^2(-1)^{(p-1)/2} \mod p. \end{array} \tag{$\bigcirc$}$$ When $p\equiv1\mod 4$, $(-1)^{(p-1)/2}=-1$, thus (applying Wilson's theorem to the LHS):
  $$n_p\equiv \left(\frac{p-1}{2}\right)!\mod p \tag{$\times$}$$ is a square root of $-1$ modulo $p$. Note that computing factorials can be expensive, so you want to do it via repeated modular multiplication, which is more efficient.
  
*To compute $\hat{n}_p$, the solution to $f(u):= u^2+1\equiv0\mod p^r$, we apply HL. First we evaluate $f\,'$ (the derivative) at the argument $n_p$, getting $2n_p$, and compute the multiplicative inverse of $2n_p$ modulo $p^{r-1}$ and multiply by the integer $-f(n_p)/p$; in other words $$\hat{n}_p\equiv-\left(\frac{n_p^2+1}{p}\right)\left[\frac{1}{2n_p}\bmod p^{r-1}\right] \mod p^r \tag{$\square$}$$ Note that since $p|(n_p^2+1)$, the division in parentheses is integer division, and the reciprocal in brackets is computed via modular arithmetic $\bmod p^{r-1}$, but then viewed $\bmod p^r$ afterwards. Furthermore, we may multiply $\hat{n}_p$ by $-1\bmod p^r$ to get a second square root of $-1\bmod p^r$; call these two roots $n_p^+$ and $n_p^-$ respectively. An arbitrary choice of $\pm$ is available for each $p$.
  
*Using the general case formula for CRT, we glue all of the "localized" solutions together: $$n\equiv \sum_{p}n_p^{\pm}\left(\frac{m}{p^r}\right)\left[\left(\frac{m}{p^r}\right)^{-1}\bmod p^r \right] \mod m \tag{$\triangle$}$$ Again, a choice of $+$ or $-$ is made for each $p$. Counterintuitively, these do not designate the notions of "positive" or "negative"; they designate an initially computed root versus an optional, auxiliary root. Above, division in parentheses is done in the integers (so not in modular arithmetic), whereas the reciprocals in brackets are computed $\bmod p^r$ (for various values of $p$), and then the results are reinterpreted as integers $\bmod m$.

(None of this was present in the original version of my answer, when I CW'd it for virtually duplicating the discussion in Arturo's answer that preceded mine.)
A: Using a generalization of Wilson's theorem
$\prod_{\gcd(i,n)=1 \leq i\leq n}i\equiv -1 (\text{mod }n)$
each $i$ will have a pair in the product $n-i$ and if there are an even number of those pairs (since each pair is congruent to the negative of the other one) each -1 in the product will cancel out with the other one and be a square so there is a solution if $\phi(n)$ is a multiple of 4.
