0
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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$

$\endgroup$
1
$\begingroup$

The statement

A system of linear equations has no solutions, a unique solution, or infinitely many solutions

Is true; and, as mentioned, applies to linear equations. We may model this as a set of linear equations, but it's not a system, because one variable is restricted to a subset of $\Bbb R$ (namely, $\Bbb Z$). $a \equiv b \; (\mathrm{mod\;} x) $ implies there exists some $c$ such that $a - cx = b$. Thus, we apply this to your system of linear equations, and let this $c$ be denoted by $X_5$. Now, you have a system of $4$ equations in $5$ variables.

$$5X_1+6X_2+7X_3+8x_4-26X_5 = 15$$

$$4X_1+7X_2+4X_3+11x_4-26X_5 = 17$$

$$2X_1+6X_2+6X_3+2x_4-26X_5 = 10$$

$$9X_1+3X_2+1X_3+8x_4-26X_5 = 18$$

However, one of your variables is restricted to $\Bbb Z$.

This is all I have to say for now, and I will ponder a bit of this when I get my thoughts straight.

$\endgroup$
  • $\begingroup$ To clarify, does that mean that the mod means it's not actually linear? $\endgroup$ – EJoshuaS Dec 14 '16 at 22:01
  • 1
    $\begingroup$ @EJoshuaS I apologize; this is a system of linear equations $\endgroup$ – Meow Mix Dec 14 '16 at 22:14
  • $\begingroup$ @EJoshuaS Looks like I can't seem to make up my mind! :P It is not a system of linear equation in $\Bbb R^n$, because the variable we chose as a difference between our numbers is restricted to $\Bbb Z$. $\endgroup$ – Meow Mix Dec 14 '16 at 22:17
  • $\begingroup$ There should be a new variable for each equation. $\endgroup$ – egreg Dec 14 '16 at 22:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.