Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have this system:

$$ \begin{align} a_{11} x_1 + a_{12} x_2 + \ldots + a_{1n} x_n &= b_1 \mod p \\ a_{21} x_1 + a_{22} x_2 + \ldots + a_{2n} x_n &= b_2 \mod p \\ \vdots \\ a_{n1} x_1 + a_{n2} x_2 + \ldots + a_{nn} x_n &= b_n \mod p \\ \end{align} $$

Can I solve it using ordinary Gaussian elimination? It seems to be incorrect to multiply a row by a constant, and then add or subtract this row with another, right?

If Gaussian elimination can't be applied here, then what other technique can I use?

share|improve this question

migrated from stackoverflow.com Jun 6 '13 at 14:31

This question came from our site for professional and enthusiast programmers.

add comment

1 Answer 1

up vote 3 down vote accepted

When p is a prime number, the integers modulo p still form a field (as the rationals and the reals do).

The Gaussian elimination works over any field, so in this case as well. Just be sure that you understand how to invert elements mod p and how to test for zero mod p.

For general p (that is, p is not a prime number), you can still make something similar to Gaussian elimination. Just bring your coefficient matrix into Smith normal form over the integers, which is a diagonal matrix. This makes solving the resulting equations mod p trivial.

The Smith normal form is described here, for example: https://en.wikipedia.org/wiki/Smith_normal_form.

The problem is even solvable in case the modulus on the right hand side is not the same for each equation. Given $$ a_{11} x_1 + \dots + a_{1m} x_m = b_1 \pmod {p_1} \\ \vdots\\ a_{n1} x_1 + \dots + a_{nm} x_m = b_n \pmod {p_n}, $$ rewrite the system as $$ a_{11} x_1 + \dots + a_{1m} x_m + p_1 y = b_1 \\ \vdots\\ a_{n1} x_1 + \dots + a_{nm} x_m + p_n y = b_n, $$ which is in the variables $x_1, \dots, x_n, y$. Solve this system over the integers (using Smith normal form). Finally project the resulting solutions $(x_1, \dots, x_n, y)$ to $(x_1, \dots, x_n)$.

share|improve this answer
    
Upvoted, but I don't understand why should p be prime to form a field, what does it mean? –  Alcott Jun 6 '13 at 13:21
1  
A commutative ring is an algebraic structure where you can do addition and multiplication and where those operations obey the usual rules, e.g. the commutativity laws and the distributivity law. Examples of rings are the integers, the reals and the integers modulo n. A field is a special type of a commutative ring, namely where an element in multiplicatively invertible if and only if it is non-zero. This is true for the rationals or the reals where you are allowed to divide by an element if and only if it is non-zero, so both for a field... (to be continued) –  Marc Jun 6 '13 at 13:29
    
... It is not true for the integers, e.g. 2 can not be inverted in the integers as there is no integer x with 2 * x = 1. The integers mod n usually do not form a field either: E.g. consider the case n = 6. Then 2 * 3 = 0 mod n. Therefore, neither 2 nor 3 can possess an inverse although both are zero. For n a prime number p, however, the integers mod p do form a field. Take p = 5, for example. A multiplicative inverse for, say, 2 is given by 3 because 2 * 3 = 1 mod 5. –  Marc Jun 6 '13 at 13:31
    
... The reason for this is the Euclidean algorithm. If a is non-zero mod p, this means that p does not divide a, that is the gcd of a and p is 1. The Euclidean algorithm (performed in the integers) yield integers s and t such that 1 = s a + t p. It follows that s is a multiplicative inverse for a mod p. –  Marc Jun 6 '13 at 13:33
    
Thank you so much, although it'll take some efforts for to digest your explanation, ;-). By form a field, you mean there indeed are solutions for a problem? –  Alcott Jun 6 '13 at 13:34
show 6 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.