Solving a system of equations using modular arithmetic

2,614

Here is a brief sketch of how one can solve linear systems modulo any fixed integer$~n>0$. If $n$ is prime, usual Gaussian reduction of the system works. If $n$ is a product of distinct relatively prime factors$~n_i$, then by the Chinese remainder theorem the system is equivalent to the collection of systems obtained from it by reducing modulo$~n_i$ for every $i$. Supposing each of these systems can be solved (or proven inconsistent, which I consider a form of solving) one can combine the solutions to get the solution for the original system via the Chinese remainder theorem. In detail: if the system reduced modulo any$~n_i$ is inconsistent, so it the original system; otherwise there are parametrised solutions modulo each$~n_i$, one may need to introduce dummy parameters (occurring with coefficient$~0$ everywhere) in some of them to force the same number of free parameters for each$~n_i$, and then the CRT can be applied to a particular solution and to each of the parameters to lift each of them to a value modulo$~n$, which gives a parametrised solution over $\def\Z{\Bbb Z}\Z/n\Z$.

One can thus reduce to the case where each $n_i$ is a prime power; one still needs to bridge the gap between prime powers $p^k$ and the prime$~p$. For this I suggest using a form of Hensel lifting* to the system. First reduce the system modulo$~p$ and solve that. Then if there are any solutions, lift one of them arbitrarily to a non-solution modulo$~p^2$. Then add an unknown multiple of$~p$ as correction term to it, and express the equation that the sum become a true solution modulo$~p^2$; since any defect of the lifted non-solution is a multiple of$~p$ one can divide a factor$~p$ from the equations obtained, and get a linear system modulo$~p$ that can again be solved using Gaussian elimination. Once lifted to$~p^2$, continue similarly to lift to higher powers of$~p$, until reaching$~p^k$.

There is a complication to this idea for which I do not have an answer right now. Solutions will in general not be unique but parametrised; in principle this means one must apply the lifting separately to a particular solution and to the parametrised part (the solution to the corresponding homogeneous system). However it looks like sometimes the question of whether the particular solution can be lifted at all to a higher power of$~p$ may depend on the choice of that particular solution. If this occurs, it would would mean that during the lifting process one would need to allow for adapting the particular solution to avoid inconsistencies in the set of equations obtained. This would be an additional headache, but maybe it can be shown that this never occurs. One thing that certainly can occur is that a solution exists modulo$~p$ but none exist modulo$~p^2$; this unlike the situation of Hensel's lemma (which only deals with one equation, but which is non-linear). A trivial example of that situation is the system of equations $(x\equiv1,x\equiv3)\pmod4$ which is clearly inconsistent but whose reduction modulo$~2$ is not.

*This is actually due to Schönemann, a relatively unknown 19th century mathematician who also first formulated "Eisenstein's criterion" for irreducibility of polynomials.

Share:
2,614

Related videos on Youtube

Cedric Mamo
Author by

Cedric Mamo

Autodidact

Updated on August 01, 2022

Comments

  • Cedric Mamo
    Cedric Mamo 7 days

    I am trying to implement a solver for the game lights out. You have a grid of lights, when you click on one of them the light you clicked and its four neighbours change colour, with the light starting over when it runs out of colours. The aim is to get all the lights to a particular colour.

    Because the way the colours change is cyclic, I thought I could implement it as a system of equations and do all calculations mod n (n being the number of available colours).

    This method worked for some puzzles but I got stuck in others.

    I am representing the game as a system of equations in an augmented matrix and reducing it to reduced row echelon form using gaussian elimination. As I said in some cases this worked well. However there are some cases (example to follow) where I end up with a line which I cannot reduce completely, reason being that, since I'm using modular arithmetic, some values don't have a multiplicative inverse so I get stuck.

    Here is an example: The game shown here represents a 4x4 grid with 4 colours available. Here is the matrix as it started out:

    1100100000000000 3
    1110010000000000 3
    0111001000000000 2
    0011000100000000 3
    1000110010000000 3
    0100111001000000 3
    0010011100100000 0
    0001001100010000 0
    0000100011001000 0
    0000010011100100 0
    0000001001110010 2
    0000000100110001 1
    0000000010001100 3
    0000000001001110 1
    0000000000100111 0
    0000000000010011 0
    

    and this is as far as I've managed to reduce it:

    1000000000000333 2
    0100000000003323 3
    0010000000003233 0
    0001000000003330 0
    0000100000001232 2
    0000010000002003 2
    0000001000003002 3
    0000000100002321 3
    0000000010001320 1
    0000000001003332 1
    0000000000102333 0
    0000000000010231 2
    0000000000000220 2
    0000000000002222 0
    0000000000002222 0
    0000000000000220 2
    

    In this case the last line, for example, is ...220 2 and I cannot figure out how I can reduce it since I cannot simply divide by 2 (2 has no multiplicative inverse in z4). Whatever I tried, I always ended up with a leading 2 in a row. I am absolutely certain a solution exists for the game (I did solve it correctly myself) but I'm not sure if I'm doing missing something here, or just that the method simply does not work for all cases.

    Thanks

    Edit: Fixed the matrices in the example. There were inconsistencies at the end. I've figured out that any inconsistencies there mean there is no solution. In the updated example a solution does exist for sure, and this results in no inconsistencies at the end. However I still cannot solve it

    • Calvin Lin
      Calvin Lin over 8 years
      Note that your last line, and fourth last line are inconsistent with each other. So is your second last and third last line.
    • Marc van Leeuwen
      Marc van Leeuwen over 8 years
      Gaussian elimanation works over fields, only. So it is no surprise tht it does not provide a fool-proof method for solving a system over $\Bbb Z/4\Bbb Z$.
    • Cedric Mamo
      Cedric Mamo over 8 years
      @calvin I noticed that about the inconsistent lines just now, was going to write about it.
    • Cedric Mamo
      Cedric Mamo over 8 years
      @MarcvanLeeuwen Pardon my ignorance, but how can I know if a ring is a field or not? (I'm not a mathematician, I'm just playing with numbers xD)
    • Marc van Leeuwen
      Marc van Leeuwen over 8 years
      Well, if you can divide by any nonzero element, it is a field, otherwise it is not. In $\Bbb Z/4\Bbb Z$ you cannot divide by$~2$ as you noticed, so it is not a field. In general $\Bbb Z/n\Bbb Z$ is only a field when $n$ is a prime number.
    • Erick Wong
      Erick Wong over 8 years
      @MarcvanLeeuwen True, not foolproof, but the logic should be sound regardless of whether one is operating in a ring or a field. In particular Gaussian elimination should not have turned a consistent system into an inconsistent one, so I think the original question is worth asking.
    • Cedric Mamo
      Cedric Mamo over 8 years
      In that example I must have built the original matrix badly (a mistake in the rightmost column), but I did notice that when the game does have a solution, the lines at the end (while not in reduced row echelon form) are consistent. If the game is unsolvable then the inconsistencies arise. So at the very least I can know whether a solution exists or not, but not what it is. Interestingly if the board is any other size (3x4, 5x5, 7x7, 6x6) then the game is perfectly solved. Maybe the ring size and the matrix height (4 and 16 respectively) are related somehow. Oh well, thanks for your comments
    • user7530
      user7530 over 8 years
      More generally: is there an algorithm akin to Gaussian elimination for solving linear systems modulo a prime power? Interesting question.
    • Cedric Mamo
      Cedric Mamo over 8 years
      If this cannot be solved using this system, Can anyone point me in the direction of a method used to solve such linear systems, if it exists. I don't necessarily expect an answer to this question, just a poke in the right direction, I'll research it myself. As I said, I'm not a mathematician, I just enjoy playing with numbers occasionally, and learn whatever I need to make them work as I go along
    • Marc van Leeuwen
      Marc van Leeuwen over 8 years
      Actually the example system is not very problematic. The equation in the last line is $2x_{14}+2x_{15}\equiv2\pmod4$, which you can divide by$~2$ to give $x_{14}+x_{15}\equiv1\pmod2$. Since the modulus is reduced to$~2$ here, it corresponds modulo$~4$ to an additional freedom. Suppose $x_{15}$ is chosen as a free parameter (modulo$~4$) in you solution, then you can use this equation to set $x_{14}=1+2p-x_{15}$ in $\Bbb Z/4\Bbb Z$ for an additional parameter $p\in\Bbb Z/4\Bbb Z$ (but of which only the parity matters).