# 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$)?

-
You can note that $m^2 = -1 \equiv (2k+1)-1 = 2k \pmod{2k+1}$. –  talmid Jun 24 '12 at 7:47
Sorry, I do not understand what that means –  MyNameIsKhan Jun 24 '12 at 7:49
With congruences you can always add any multiple of the modulus, since they're all equivalent to $0$. In this case, since $m^2 \equiv -1 \pmod{2k+1}$, and $2k+1 \equiv 0 \pmod{2k+1}$, we have $$m^2 \equiv -1 = -1 + 0 \equiv -1 + 2k+1 = 2k \pmod{2k+1}$$ It's a string of equalities and equivalences, consider each $\equiv$ or $=$, and try to understand what happens in the passage from the left side to the right side of each $\equiv$ or $=$. In any case, this is only one thing you could do (to avoid the negative number; although you should be comfortable with having a negative right-hand side ... –  talmid Jun 24 '12 at 7:54
For example let's say k = 6. How do I find solutions to m^2 congruent to -1 mod 13? –  MyNameIsKhan Jun 24 '12 at 7:56
@talmid: changing $-1$ to $2k$ seems to me to be moving farther away from a solution rather than closer. The triumvirate of CRT, Hensel's and quadratic reciprocity works on the problem as stated (see the discussion here). –  anon Jun 24 '12 at 12:05

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}.$$

-
Perhaps one should first state the obvious that $m$ is a solution if and only if $m+q$ is a solution. So a very inefficient way to solve the congruence for a given $k$ would be to check which of the $q$ non-congruent $m$ are solutions. Now you describe a much more efficient algorithm for the solution. The description is quite clear, except for the solve for prime power moduli (by "lifting") part. –  Thomas Klimpel Jun 24 '12 at 11:01
Added a decsription of the lifting process. I will skip an exposition of the basics of residue classes. There is ample material in the web and the OP's lecture notes for that. –  Jyrki Lahtonen Jun 24 '12 at 11:47
Thanks, I really appreciated it to better understand the lifting process. (It was the group extension problem and the challenges of understanding group cohomology which motivated me to extend my knowledge of abstract algebra again years after having left university.) –  Thomas Klimpel Jun 24 '12 at 12:43
@JyrkiLahtonen I really appreciate the effort that went into this answer but I am afraid I am still confused. Is there no way to solve this other than guess and check? I'm trying to solve this system as a result of simply knowing what k is. –  MyNameIsKhan Jun 24 '12 at 13:40
@AgainstASicilian: What the answer is saying is that in addition to knowing $k$ you need to know the prime factorization of $2k+1$. So if $k$ is very large (the best computer programs would choke if $k$ has a few thousand digits, humans would give up a lot earlier) that step may become the bottleneck. –  Jyrki Lahtonen Jun 24 '12 at 15:16

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.

-
So -1-m^2 is a multiple of 2k+1? –  MyNameIsKhan Jun 24 '12 at 7:41
Yes. Is there a problem? –  Gerry Myerson Jun 24 '12 at 9:11
Just not sure how to take that information and solve for valid solutions –  MyNameIsKhan Jun 24 '12 at 13:47
Ah, I see you changed the problem from $m\equiv-1$ to $m^2\equiv-1$. Anyway, it looks like others have given you plenty to work with. –  Gerry Myerson Jun 24 '12 at 23:30

(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$.

-
Thanks, Henning. I need to work on my clarity and brevity :-) –  Jyrki Lahtonen Jun 24 '12 at 18:42
@JyrkiLahtonen: Not sure you're at fault. See recent chat transcript. –  Henning Makholm Jun 24 '12 at 18:45

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:

1. 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.

2. 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$.

3. 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.)

-
The OP's letter '$m$' is my letter '$n$', and I use $m$ to designate $2k+1$. All prime divisors of $m$ are necessarily congruent to $1\bmod 4$. –  anon Jun 24 '12 at 20:12