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

Solution 1:

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

Solution 2:

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.

Solution 3:

(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":)

When $q$ is a prime, $m=\pm((q-1)/2)!$ are the only non-congruent solutions.

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

Solution 4:

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

Solution 5:

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.