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 of equation. $a+b+c=171, a+2b+4c = 46, a+3b+9c = 170$.

My task is to solve this system over $GF(211)$. Is there any special process?

Thanks for advice.

share|improve this question
1  
What joriki says below. If there was a typo, and you are to work over the field $GF(223)$ (that does exist by virtue of 223 being a prime), then you can apply the usual linear algebra techniques and perform row operations on a suitably augmented matrix. See my answer for an example - it is over $GF(29)$. If there was now typo, and you are to find the solutions in the ring $\mathbb{Z}_{221}$, then you can try the same technique. But it may or may not work! It is possible that at some point you would need to divide by 13 or 17, and that's a no-no. –  Jyrki Lahtonen Nov 25 '12 at 8:29
1  
(cont'd) but your matrix of coefficients is of Vandermonde type, so it looks like the process should work (the determinant is not divisible by either 13 or 17). In more general situations you may not get a unique solution, and things become more complicated. –  Jyrki Lahtonen Nov 25 '12 at 8:34
add comment

2 Answers 2

There is no such thing as $GF(221)$; finite fields exist only for prime-power orders; $221=13\cdot17$.

share|improve this answer
add comment

To answer your question "is there a special process", the answer is it depends on the underlying (field) number system. Processes like gaussian elimination always work but gram-schmidt and hence any method based on it doesn't always work even if a unique solution exists. For example in a vector space over a binary field gram-schmidt doesn't work because you can have a nonzero vector which is orthogonal to all other vectors. In real/complex fields the zero vector is the only one with this property.

The general rule to remember, in whatever number system you are working in, if the determinant of the matrix is invertible then the matrix itself is invertible. And if it is invertible then it will have a unique inverse and hence your system will have a unique solution. If the determinant isn't invertible then you can problems like no solutions or more than one (finite or infinite).

In this case, did you mean the ring Z/221Z or the field Z/223Z? In either case the determinant of your matrix is 2 which is invertible in both because 2 is coprime to both 221 and 223. So I would just use any standard method. The only thing to remember is that the arithmetic would be in whatever number system you are using.

share|improve this answer
    
I'm sorry, it should be over GF(211). –  kmaci Nov 25 '12 at 16:49
    
So everything I said is still true and you are good because 211 is prime. The determinant is 2 which is invertible so your system is uniquely solvable in GF(211). The matrix is small enough just plain gaussian elimination will suffice. –  Fixed Point Nov 25 '12 at 22:10
add comment

Your Answer

 
discard

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

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