Computing by homomorphic images
The Chinese remainder method has already been investigated by Chinese mathematicians more than 2000 years ago. For a short introduction to the history we refer to Knuth (1981). The main idea consists of solving a problem over the integers by solving this
- PDF / 2,488,869 Bytes
- 31 Pages / 505 x 720 pts Page_size
- 97 Downloads / 171 Views
Computing by
homomorphic images
3.1 The Chinese remainder problem and the modular method The Chinese remainder method has already been investigated by Chinese mathematicians more than 2000 years ago. For a short introduction to the history we refer to Knuth (1981). The main idea consists of solving a problem over the integers by solving this problem in several homomorphic images modulo various primes, and afterwards combining the solutions of the modular problems to a solution of the problem over the integers. In fact, the method can be generalized to work over arbitrary Euclidean domains, i.e., domains in which we can compute greatest common divisors by the Euclidean algorithm. An interesting list of different statements of the Chinese remainder theorem is given in Davis and Hersh (1981). Euclidean domains Definition 3.1.1. A Euclidean domain (ED) D is an integral domain together with a degree function deg: D* -+ No, such that a. deg(a· b)::: deg(a) for all a, bE D*, b. (division property) for all a, bED, b =I 0, there exists a quotient q and a remainder r in D such that a = q . b + rand (r = 0 or deg(r) < deg(b)).
When we write "r = a mod b" we mean that r is a remainder of a and b as in (a). In other words, the function mod b returns a remainder of its argument modulo b. In the same way we will consider functions quot and rem, yielding q and r, respectively, for inputs a and b as in Definition 3.1.1. Example 3.1.1. a. Z with deg(a) = lal is an ED. If a = q . b + rand 0 < r < Ibl, then also q + 1 and r - b are a possible pair of quotient and remainder for a and b. So in an ED quotients and remainders are not uniquely defined. b. Every field K with deg(a) = 1 for all a E K* is an ED. c. For every field K the univariate polynomial ring K[x], where the degree function deg returns the usual degree of a polynomial (canonical degree function), is an ED. In fact, quotient and remainder can be computed by the algorithm POLDIVK. d. If the coefficient ring of R[x] is not a field, then R[x] with the canonical degree function is not an ED. Consider ax = q . (bx) + r, where a, b E R. For q and r to be a quotient and remainder of ax and bx, q would have to be an element of R satisfying a = q . b. This equation, however, is not F. Winkler, Polynomial Algorithms in Computer Algebra © Springer-Verlag Wien 1996
52
Homomorphic images
solvable for arbitrary a, b E R*. So, for instance, polynomials over the integers and multivariate polynomials over a field together with the canonical degree function do not form Euclidean domains. In an ED D we have deg(l) :s deg(a) for all non-zero a, and deg(l) deg(a) if and only if a is a unit. If c is not a unit and non-zero and a = b . c, then deg(b) < deg(a).
Theorem 3.1.1. Any two non-zero elements a, b of an ED D have a greatest common divisor g which can be written as a linear combination g = s· a + t . b for some s, tED. Proof Let 1 = (a, b), the ideal generated by a, b in D. Let g be a non-zero element of 1 with minimal degree, i.e., for all c E 1*, deg(g) :s deg(c). So g = S . a +
Data Loading...
