[Math] Solving systems of linear equations involving modulo

linear algebrasystems of equations

I encountered this question on Stack Overflow earlier and became curious about its mathematics. Basically, the question is how to solve systems of linear equations under modular arithmetic. The equation is as follows:
$(5X_1 + 6X_2 + 7X_3 + 8X_4) \mod 26 = 15$
$(4X_1 + 7X_2 + 4X_3 + 11X_4) \mod 26 = 17$
$(2X_1 + 6X_2 + 6X_3 + 2X_4) \mod 26 = 10$
$(9X_1 + 3X_2 + 1X_3 + 8X_4) \mod 26 = 18$

Clearly, this is just a system of simultaneous equations. If this just involved "normal" integers, I'd just set up an augmented matrix and row-reduce it to find the answer. Unfortunately this isn't so easy.

First, would it be correct to just say that we're solving this in $Z_{26}$ or am I misreading the notation? Also, am I correct in saying that $Z_{26}$ is not a finite field since 26 is neither prime nor a power of a prime?

I've read several other posts that talk about similar problems, such as:

I've been having trouble finding a detailed walk-through on how to do this though. Is it possible to still row-reduce here somehow, or should I try something like Cramer's Rule? How do I do that?

There is, of course, an exceptionally dumb brute force way of solving this if you happen to be using a computer:

for (int i = 0; i <= 25; i++)
{
    for (int j = 0; j <= 25; j++)
    {
        for (int k = 0; k <= 25; k++)
        {
            for (int l = 0; l <= 25; l++)
            {
                int equation1 = (5 * i) + (6 * j) + (7 * k) + (8 * l);
                int equation2 = (4 * i) + (7 * j) + (4 * k) + (11 * l);
                int equation3 = (2 * i) + (6 * j) + (6 * k) + (2 * l);
                int equation4 = (9 * i) + (3 * i) + k + (8 * l);

                if (equation1 % 26 == 15 && equation2 % 26 == 17 && equation3 % 26 == 10 && equation4 % 26 == 18)
                {
                    string result = string.Format("i: {0} j: {1} k: {2} l: {3}{4}", i, j, k, l, Environment.NewLine);

                    File.AppendAllText(resultsFile, result);
                }
           }
       }
    }
 }

Interestingly, this gives me the results
$x_1 = 23, x_2 = 11, x_3 = 24, x_4 = 20$
and
$x_1 = 23, x_2 = 24, x_3 = 24, x_4 = 7$
where $i = x_1, j = x_2, k = x_3, l = x_4$.

It seems odd to me that there should be 2 solutions here, since according to one of my favorite linear algebra textbooks (Robert A. Beezer's A First Course in Linear Algebra, which has the dual advantages of being both free and concise :)) states that "A system of linear equations has no solutions, a unique solution or infinitely many solutions." Did I mess something up in how I wrote this, or is it legitimately possible that systems of linear equations under modular arithmetic will have $1 < n < \infty$ solutions?

Just for clarification, I'm looking mostly for the mathematical (not programmatic) way of solving this. (The programmatic way of solving it is probably a better fit for Software Engineering SE).

Best Answer

Try to solve this system by mod 13 and by mod 2. ($Z_{13}$ and $Z_2$ is a finite fields )

Determinant of the matrix is -1024 => where is one solution in $Z_{13}$ (Use Gauss or Kramer to found it - it is (10, 11, 11, 7))

In $Z_2$:

$X_1 + X_3 = 1$

$X_2 + X_4 = 1$

0 = 0

$X_1 + X_2 + X_3 = 0$

=>$X_1+ X_3 = 1 , X_2 = 1, X_4 = 0$

Related Question