Wikipedia:Reference desk/Archives/Mathematics/2020 September 13

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

September 13

Algorithm for solving a system of congruences

I need to solve a fairly large number of systems of congruences in a program. A simple example is:

• $3x\equiv 1\mod 20$
• $7y\equiv 2\mod 20$
• $11z\equiv 3\mod 20$

Find (x,y,z). Is there something better than basically brute force that can be implemented in a program? Bubba73 ^{You talkin' to me?} 05:32, 13 September 2020 (UTC)

This is reminiscent of the Chinese remainder theorem, which applies to a system of congruences with different moduli, but a single, shared unknown. But what we have here is hardly a system – the unknowns do not co-occur in any of the congruences, so each can be solved separately.

The congruence $ax\equiv b~(\mathrm {mod} ~m)$ is solved by $x\equiv a^{{-}1}b~(\mathrm {mod} ~m)$, assuming that the coefficient $a$ is coprime with the modulus. Otherwise, for there to be a solution, $b$ needs to be divisible by $\mathrm {gcd} (a,m)$; then simply replace $a$, $b$ and $m$ by the result of dividing each by this common divisor. The multiplicative inverse $a^{{-}1}$ defined by $a^{{-}1}a\equiv 1~(\mathrm {mod} ~m)$ can efficiently be computed by solving Bézout's equation using the extended Euclidean algorithm (see Modular arithmetic).  --Lambiam 10:16, 13 September 2020 (UTC)

I wrote that right before going to bed and left out a condition: 3x, 7y, and 11z are to be in the interval [20n+1, 20n+19] for some n. Find n (or x, y, and z). Bubba73 ^{You talkin' to me?} 16:02, 13 September 2020 (UTC)

That additional requirement does not present a problem. You can always take $n=0$. Taking the example problem:

• $~~3^{-1}\equiv ~~7~(\mathrm {mod} ~20)$, so $x\equiv ~~7{\times }1\equiv ~~7~(\mathrm {mod} ~20)$
• $~~7^{-1}\equiv ~~3~(\mathrm {mod} ~20)$, so $y\equiv ~~3{\times }2\equiv ~~6~(\mathrm {mod} ~20)$
• $11^{-1}\equiv 11~(\mathrm {mod} ~20)$, so $z\equiv 11{\times }3\equiv 13~(\mathrm {mod} ~20)$

Just take the reduced values $(7,6,13)$; all are in the interval $[20n+1,20n+19]$ for $n=0$.  --Lambiam 16:47, 13 September 2020 (UTC)

Sorry, here the three of $(x,y,z)$ are in the interval $[1,19]$, but you wrote that $(3x,7y,11x)$ need to be roommates. Back to the drawing board. Right now I have no time to look into this.  --Lambiam 21:10, 14 September 2020 (UTC)

Let $c$ be the reduced form (modulo $m$) of $a^{{-}1}b$, that is, the unique solution of $c\equiv a^{{-}1}b~(\mathrm {mod} ~m)$ such that $0\leq c<m$, which is the same as the remainder of dividing $a^{{-}1}b$ by $m$ if the numbers involved are positive. Then $ac\equiv b~(\mathrm {mod} ~m)$, so $ac-b$ is an integral multiple of $m$. Put $q=(ac-b)\div m$. Then $ac=qm+b$. For example, for the first congruence $3x\equiv 1~(\mathrm {mod} ~20)$ above, $c=7$, $ac=3\times 7=21$ and $b=1$, so $q=(21-1)\div 20=1$ and $ac=1\times 20+1$.

Since $x\equiv c~(\mathrm {mod} ~m)$, the general form of $x$ is given by $x=km+c$. To find a value for $ax$ in the interval $[nm+1,nm+m{-}1]$, assuming for a moment that $n$ is somehow given, we need to solve $nm+1\leq a(km+c)<nm+m$ for $k$, or, equivalently, $nm+1\leq akm+ac=akm+qm+b=(ak+q)m+b<nm+m$. Given such a solution, assuming $b$ is in reduced form, $n=ak+q$, so that then also $n\equiv q~(\mathrm {mod} ~a)$. A solution of the latter for $n$ provides a solution for $k$.

Each of the congruences of the original system can thus be turned into another congruence in which the unknown is $n$. For the example system in the question, this results in the new system

• $n\equiv 1~(\mathrm {mod} ~~~3),$
• $n\equiv 2~(\mathrm {mod} ~~~7),$
• $n\equiv 7~(\mathrm {mod} ~11).$

This is the type of system that can be solved with the Chinese remainder theorem. One solution is given by $n=205$, corresponding to $x=1367,y=586,z=373$.  --Lambiam 14:22, 15 September 2020 (UTC)

The above assumes that in each congruence $ax\equiv b~(\mathrm {mod} ~m)$ of the original system $b\not \equiv 0~(\mathrm {mod} ~m)$. Otherwise, it has no solutions for $x$ such that $ax\in [nm+1,(n{+}1)m)$ for any value of $n$. If the requirement is relaxed to $ax\in [nm,(n{+}1)m)$, solutions are possible, and the method sketched above still applies.  --Lambiam 19:02, 15 September 2020 (UTC)