3
$\begingroup$

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

  • 0
    You can note that $m^2 = -1 \equiv (2k+1)-1 = 2k \pmod{2k+1}$.2012-06-24
  • 0
    Sorry, I do not understand what that means2012-06-24
  • 0
    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 ...2012-06-24
  • 0
    For example let's say k = 6. How do I find solutions to m^2 congruent to -1 mod 13?2012-06-24
  • 0
    ... in the equation). Now, to find the values of $m$ that satisfy the congruence, if $k$ is small you could just try some values.2012-06-24
  • 1
    @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](http://math.stackexchange.com/questions/162266/under-what-situations-does-x1-divide-4n2-x/)).2012-06-24
  • 0
    Is there a way to solve this without guess and check? In all these responses I have no idea where these numbers are coming from. For instance, if the k=6 case, where on earth are people getting 5 from?2012-06-24
  • 0
    I am trying to find a systematic way to do this.2012-06-24
  • 0
    In the case $k=6$ I might use $$m\equiv k!=720=5+55\cdot13\equiv 5\pmod{13}.$$ But that works only because $13$ is a prime number and congruent to $1\pmod 4$. (Ok, guessing would be faster in this case). There is a method for calculating the answer (or deciding that it doesn't exist), if we know the prime factorization of $2k+1$.2012-06-24
  • 0
    @JyrkiLahtonen So what is the method given that we know the prime factorization?2012-06-24
  • 0
    @anon I agree, but I understood that the OP was uncomfortable with having a negative right-hand side, and this is a way to avoid that.2012-06-24

4 Answers 4

7

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

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

  • 0
    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.2012-06-24
  • 1
    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.2012-06-24
  • 0
    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.)2012-06-24
  • 0
    @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.2012-06-24
  • 0
    @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.2012-06-24
  • 0
    @JyrkiLahtonen I have no problems with the prime factorization part. I am technically getting my 2k+1's by combining together different combinations of 1mod4 primes, so its product = 2k+1, so I can get k. But now I don't know where to go from there.2012-06-24
  • 0
    @AgainstASicilian: Ok, I will add another example, where we have two prime factors. The catch is that those $1\pmod 4$ primes are more important than $k$ here.2012-06-24
  • 0
    @JyrkiLahtonen By the way, does this apply if we have powers of prime powers, too? Like if we have 13*13*17 = 2k+1?2012-06-24
  • 0
    @AgainstASicilian: Yes, that's what the latest example is about. Whenever we have a power of a prime, we lift. When we have many primes, we use the CRT.2012-06-24
  • 0
    BTW: The length of my answer combined to instant preview is apparently pushing the limits of my laptop. I cannot add any more text to that. The last edit was painfully slow.2012-06-24
  • 0
    @JyrkiLahtonen I don't quite understand the lifting process. 2k+1 is the product of many 1 modulo 4 primes, potentially with multiplicity. This means that for each prime, I lift them if that prime's exponent is greater than 1, right? I lift all the primes, then crt them together and this gives me the value of m^2? Is this right so far?2012-06-24
  • 0
    Yup, that's it. You lift for each prime as much as is needed, and then CRT the solutions together. If there are $k$ distinct primes, you get $2^k$ (pairwise non-congruent) solutions in the end.2012-06-24
  • 0
    @JyrkiLahtonen I do not quite get how to lift. Say I have 13*13*17 = 2k+1. How do I know how to "lift" the 13?2012-06-24
  • 0
    The first addendum(edit) to my answer is exactly about lifting from $13$ to $13^2$.2012-06-24
  • 0
    @JyrkiLahtonen I am still quite lost but I am sure it's correct; voting this as the answer. Thanks for the help otherwise... I suspect this might just be too advanced for me. With each new explanation I just feel more confused than before. I have no idea where many of these numbers are coming from. I'm trying to find a systematic approach that does not rely on guessing2012-06-24
  • 0
    Yeah, the answer is also a bit of patchwork. For example, I use the same notation $m_k$ for different things. When lifting, the subscript indicates the power of $q$. When explaining CRT, the subscripts are used to distinguish the non-congruent roots modulo $13^2\cdot 17$. Sorry about that.2012-06-24
5

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.

  • 0
    So -1-m^2 is a multiple of 2k+1?2012-06-24
  • 0
    Yes. Is there a problem?2012-06-24
  • 0
    Just not sure how to take that information and solve for valid solutions2012-06-24
  • 0
    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.2012-06-24
2

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

  • 0
    Thanks, Henning. I need to work on my clarity and brevity :-)2012-06-24
  • 0
    @JyrkiLahtonen: Not sure you're at fault. See recent chat transcript.2012-06-24
2

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

  • 0
    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$.2012-06-24