You've probably used Gauss-Jordan elimination over the reals. What properties of real numbers make Gauss-Jordan elimination work? The real numbers have additi

You've probably used Gauss-Jordan elimination over the reals. What properties of real numbers make Gauss-Jordan elimination work? The real numbers have addition and multiplication operations which each obey commutative, associative, identity, and inverse laws; and multiplication is distributes over addition. These properties are all that's required for Gauss-Jordan elimination to work. (We don't need other properties of real numbers, such as properties involving convergence of sequences, which you may have studied in calculus or real analysis class.) A set and binary operators + and * which have all of these properties, are called a "field" [1]. The real numbers, rational numbers, and complex numbers are probably your most familiar examples of fields. When talking about a field like "the field of rational numbers, Q", you're actually referring to a data structure (Q, +, *) which includes definitions of the addition and multiplication operators. Since most fields have "standard" addition and multiplication operators, often mathematicians drop them from discussion. Kind of like, when you're discussing a program with a colleague, you say, "Add the offset to the base," your colleague doesn't ask, "Add them as integers or floating-point numbers? What should I do if they overflow?" The answers to these questions are almost always clear from context, and also almost always near-universally standardized, at least within a particular programming language. Anyway, as other posters have noted, the integers modulo p, where p is prime, are actually a field. It's obvious that Z_p has most of the properties of a field, but multiplicative inverse is interesting. The proof of existence of multiplicative inverses mod p -- and a fast O(log(p)) implementation of finding them -- is the Euclidean algorithm, one of the oldest algorithms known to mankind. [2] [1] http://en.wikipedia.org/wiki/Field_%28mathematics%29 http://en.wikipedia.org/wiki/Field_%28mathematics%29 [2] http://en.wikipedia.org/wiki/Euclidean_Algorithm http://en.wikipedia.org/wiki/Euclidean_Algorithm