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

Mathematics desk
< September 12	<< Aug | September | Oct >>	Current desk >

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:

• ${\displaystyle 3x\equiv 1\mod 20}$ 
• ${\displaystyle 7y\equiv 2\mod 20}$ 
• ${\displaystyle 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)[reply]

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 ${\displaystyle ax\equiv b~(\mathrm {mod} ~m)}$  is solved by ${\displaystyle x\equiv a^{{-}1}b~(\mathrm {mod} ~m)}$ , assuming that the coefficient ${\displaystyle a}$  is coprime with the modulus. Otherwise, for there to be a solution, ${\displaystyle b}$  needs to be divisible by ${\displaystyle \mathrm {gcd} (a,m)}$ ; then simply replace ${\displaystyle a}$ , ${\displaystyle b}$  and ${\displaystyle m}$  by the result of dividing each by this common divisor. The multiplicative inverse ${\displaystyle a^{{-}1}}$  defined by ${\displaystyle 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)[reply]

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)[reply]

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

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

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

Sorry, here the three of ${\displaystyle (x,y,z)}$  are in the interval ${\displaystyle [1,19]}$ , but you wrote that ${\displaystyle (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)[reply]

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

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

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

• ${\displaystyle n\equiv 1~(\mathrm {mod} ~~~3),}$ 
• ${\displaystyle n\equiv 2~(\mathrm {mod} ~~~7),}$ 
• ${\displaystyle 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 ${\displaystyle n=205}$ , corresponding to ${\displaystyle x=1367,y=586,z=373}$ .  --Lambiam 14:22, 15 September 2020 (UTC)[reply]

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