Алгоритм евклида для многочленов теорема

О1)Общим делителем многочленов f(x)
и
g(x)
называется такой
d(x)
что, выполняются
f(x)d(x)
и
g(x)d(x).

О2)Наибольшим будет тот из общих
делителей степень которого больше.

Будем считать что, общий делитель d(x)
который делится на любой другой делитель
этих многочленов будет наибольшим
d(x)=(f(x),g(x))
очевидно что, общим делителем многочленов
будет и делитель вида:
с*d(x)=(с*f(x),с*g(x)),c=const
0.

НОД отыскивается с точностью до
постоянного множителя. Многочлены
отличающееся друг от друга постоянным
множителем называются ассоциированными.
НОД отыскивают с помощью алгоритма
Евклида который состоит в следующем: с
начал делят с остатком многочлен f(x)
на g(x) затем
g(x) на остаток


от первого деления затем

от первого деления на остаток

от второго деления и так далее до тех
пока не получится нулевой остаток при
этом получается цепочка равенств.

Последний не нулевой остаток и есть НОД
двух многочленов.

Пример 1:

В кольце R[x]
найти НОД двух многочленов:

























.

На практике может возникнуть задача
отыскания нескольких многочленов:

НОД(f,g…q)=НОД(f,НОД(g,…НОД(t,q)…)).

Т1:НОД двух многочленов может быт
представлен в виде:

Где

из тогоже кольца что, и данные многочлены.

Доказательство:

Для нахождения НОД(f,g)
воспользуемся равенствами 1 алгоритма
Евклида:



подставляя это равенство во второе
равенство совокупности 1 можем выразить
остаток
.

действуя так и далее можно выразить
остаток

через f(x) и
g(x) а, также
последний остаток
.

Пример 2:

Из примера 1 запишем представление
остатков:

§ 8 Наименьшее общее кратное двух многочленов.

О1) Многочлен

называется общим кратным для


и


если

.

О2)Общее кратное f(x)
и
g(x)
на которое делится любое общее кратное
этих многочленов называется наименьшим
общим кратным многочленов


и


и обозначается:

.

Т1:Для любых многочленов

существует наименьшее общее кратное
которое можно найти по формуле

Доказательство:

Пусть многочлен

некоторое произвольное общее кратное
многочленов f(x)
и g(x). Так
как М общее кратное то M(x)=f(x)p(x),
M(x)=g(x)q(x)

(f(x),g(x))=d(x),
тогда

g(x)⋮d(x)


Из этого равенства видно, что


Получено выражение для произвольного
общего кратного многочленов f(x)
g(x) положив
в этом выражении 𝜑(x)=1
получим формулу для нахождения наименьшего
общего кратного.

Замечание:

[f,g]⋮f

[f,g]⋮g

M⋮[f,g]

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

  • #
  • #
  • #
  • #
  • #
  • #
  • #
  • #
  • #
  • #
  • #

In algebra, the greatest common divisor (frequently abbreviated as GCD) of two polynomials is a polynomial, of the highest possible degree, that is a factor of both the two original polynomials. This concept is analogous to the greatest common divisor of two integers.

In the important case of univariate polynomials over a field the polynomial GCD may be computed, like for the integer GCD, by the Euclidean algorithm using long division. The polynomial GCD is defined only up to the multiplication by an invertible constant.

The similarity between the integer GCD and the polynomial GCD allows extending to univariate polynomials all the properties that may be deduced from the Euclidean algorithm and Euclidean division. Moreover, the polynomial GCD has specific properties that make it a fundamental notion in various areas of algebra. Typically, the roots of the GCD of two polynomials are the common roots of the two polynomials, and this provides information on the roots without computing them. For example, the multiple roots of a polynomial are the roots of the GCD of the polynomial and its derivative, and further GCD computations allow computing the square-free factorization of the polynomial, which provides polynomials whose roots are the roots of a given multiplicity of the original polynomial.

The greatest common divisor may be defined and exists, more generally, for multivariate polynomials over a field or the ring of integers, and also over a unique factorization domain. There exist algorithms to compute them as soon as one has a GCD algorithm in the ring of coefficients. These algorithms proceed by a recursion on the number of variables to reduce the problem to a variant of the Euclidean algorithm. They are a fundamental tool in computer algebra, because computer algebra systems use them systematically to simplify fractions. Conversely, most of the modern theory of polynomial GCD has been developed to satisfy the need for efficiency of computer algebra systems.

General definition[edit]

Let p and q be polynomials with coefficients in an integral domain F, typically a field or the integers.
A greatest common divisor of p and q is a polynomial d that divides p and q, and such that every common divisor of p and q also divides d. Every pair of polynomials (not both zero) has a GCD if and only if F is a unique factorization domain.

If F is a field and p and q are not both zero, a polynomial d is a greatest common divisor if and only if it divides both p and q, and it has the greatest degree among the polynomials having this property. If p = q = 0, the GCD is 0. However, some authors consider that it is not defined in this case.

The greatest common divisor of p and q is usually denoted «gcd(p, q)«.

The greatest common divisor is not unique: if d is a GCD of p and q, then the polynomial f is another GCD if and only if there is an invertible element u of F such that

f=u d

and

d=u^{-1} f.

In other words, the GCD is unique up to the multiplication by an invertible constant.

In the case of the integers, this indetermination has been settled by choosing, as the GCD, the unique one which is positive (there is another one, which is its opposite). With this convention, the GCD of two integers is also the greatest (for the usual ordering) common divisor. However, since there is no natural total order for polynomials over an integral domain, one cannot proceed in the same way here. For univariate polynomials over a field, one can additionally require the GCD to be monic (that is to have 1 as its coefficient of the highest degree), but in more general cases there is no general convention. Therefore, equalities like d = gcd(p, q) or gcd(p, q) = gcd(r, s) are common abuses of notation which should be read «d is a GCD of p and q» and «p and q have the same set of GCDs as r and s«. In particular, gcd(p, q) = 1 means that the invertible constants are the only common divisors. In this case, by analogy with the integer case, one says that p and q are coprime polynomials.

Properties[edit]

gcd(p, q, r) = gcd(p, gcd(q, r)),
and

gcd(p_1, p_2, dots , p_n) = gcd( p_1, gcd(p_2, dots , p_n)).

GCD by hand computation[edit]

There are several ways to find the greatest common divisor of two polynomials. Two of them are:

  1. Factorization of polynomials, in which one finds the factors of each expression, then selects the set of common factors held by all from within each set of factors. This method may be useful only in simple cases, as factoring is usually more difficult than computing the greatest common divisor.
  2. The Euclidean algorithm, which can be used to find the GCD of two polynomials in the same manner as for two numbers.

Factoring[edit]

To find the GCD of two polynomials using factoring, simply factor the two polynomials completely. Then, take the product of all common factors. At this stage, we do not necessarily have a monic polynomial, so finally multiply this by a constant to make it a monic polynomial. This will be the GCD of the two polynomials as it includes all common divisors and is monic.

Example one: Find the GCD of x2 + 7x + 6 and x2 − 5x − 6.

x2 + 7x + 6 = (x + 1)(x + 6)
x2 − 5x − 6 = (x + 1)(x − 6)

Thus, their GCD is x + 1.

Euclidean algorithm[edit]

Factoring polynomials can be difficult, especially if the polynomials have a large degree. The Euclidean algorithm is a method that works for any pair of polynomials. It makes repeated use of Euclidean division. When using this algorithm on two numbers, the size of the numbers decreases at each stage. With polynomials, the degree of the polynomials decreases at each stage. The last nonzero remainder, made monic if necessary, is the GCD of the two polynomials.

More specifically, for finding the gcd of two polynomials a(x) and b(x), one can suppose b ≠ 0 (otherwise, the GCD is a(x)), and

deg(b(x)) le deg(a(x)) ,.

The Euclidean division provides two polynomials q(x), the quotient and r(x), the remainder such that

{displaystyle a(x)=q_{0}(x)b(x)+r_{0}(x)qquad {text{and}}qquad deg(r_{0}(x))<deg(b(x))}

A polynomial g(x) divides both a(x) and b(x) if and only if it divides both b(x) and r0(x). Thus

{displaystyle gcd(a(x),b(x))=gcd(b(x),r_{0}(x)).}

Setting

{displaystyle a_{1}(x)=b(x),b_{1}(x)=r_{0}(x),}

one can repeat the Euclidean division to get new polynomials q1(x), r1(x), a2(x), b2(x) and so on. At each stage we have

{displaystyle deg(a_{k+1})+deg(b_{k+1})<deg(a_{k})+deg(b_{k}),}

so the sequence will eventually reach a point at which

b_N(x) = 0

and one has got the GCD:

{displaystyle gcd(a,b)=gcd(a_{1},b_{1})=cdots =gcd(a_{N},0)=a_{N}.}

Example: finding the GCD of x2 + 7x + 6 and x2 − 5x − 6:

x2 + 7x + 6 = 1 ⋅ (x2 − 5x − 6) + (12 x + 12)
x2 − 5x − 6 = (12 x + 12) (1/12 x1/2) + 0

Since 12 x + 12 is the last nonzero remainder, it is a GCD of the original polynomials, and the monic GCD is x + 1.

In this example, it is not difficult to avoid introducing denominators by factoring out 12 before the second step. This can always be done by using pseudo-remainder sequences, but, without care, this may introduce very large integers during the computation. Therefore, for computer computation, other algorithms are used, that are described below.

This method works only if one can test the equality to zero of the coefficients that occur during the computation. So, in practice, the coefficients must be integers, rational numbers, elements of a finite field, or must belong to some finitely generated field extension of one of the preceding fields. If the coefficients are floating-point numbers that represent real numbers that are known only approximately, then one must know the degree of the GCD for having a well defined computation result (that is a numerically stable result; in this cases other techniques may be used, usually based on singular value decomposition.

Univariate polynomials with coefficients in a field[edit]

The case of univariate polynomials over a field is especially important for several reasons. Firstly, it is the most elementary case and therefore appears in most first courses in algebra. Secondly, it is very similar to the case of the integers, and this analogy is the source of the notion of Euclidean domain. A third reason is that the theory and the algorithms for the multivariate case and for coefficients in a unique factorization domain are strongly based on this particular case. Last but not least, polynomial GCD algorithms and derived algorithms allow one to get useful information on the roots of a polynomial, without computing them.

Euclidean division[edit]

Euclidean division of polynomials, which is used in Euclid’s algorithm for computing GCDs, is very similar to Euclidean division of integers. Its existence is based on the following theorem: Given two univariate polynomials a and b ≠ 0 defined over a field, there exist two polynomials q (the quotient) and r (the remainder) which satisfy

a=bq+r

and

deg(r)<deg(b),

where «deg(…)» denotes the degree and the degree of the zero polynomial is defined as being negative. Moreover, q and r are uniquely defined by these relations.

The difference from Euclidean division of the integers is that, for the integers, the degree is replaced by the absolute value, and that to have uniqueness one has to suppose that r is non-negative. The rings for which such a theorem exists are called Euclidean domains.

Like for the integers, the Euclidean division of the polynomials may be computed by the long division algorithm. This algorithm is usually presented for paper-and-pencil computation, but it works well on computers when formalized as follows (note that the names of the variables correspond exactly to the regions of the paper sheet in a pencil-and-paper computation of long division). In the following computation «deg» stands for the degree of its argument (with the convention deg(0) < 0), and «lc» stands for the leading coefficient, the coefficient of the highest degree of the variable.

Euclidean division

Input: a and b ≠ 0 two polynomials in the variable x;
Output: q, the quotient, and r, the remainder;

Begin
    q := 0
    r := a
    d := deg(b)
    c := lc(b)
    while deg(r) ≥ d do
        s := lc(r)/c xdeg(r)−d
        q := q + s
        r := rsb
    end do
    return (q, r)
end

The proof of the validity of this algorithm relies on the fact that during the whole «while» loop, we have a = bq + r and deg(r) is a non-negative integer that decreases at each iteration. Thus the proof of the validity of this algorithm also proves the validity of the Euclidean division.

Euclid’s algorithm[edit]

As for the integers, the Euclidean division allows us to define Euclid’s algorithm for computing GCDs.

Starting from two polynomials a and b, Euclid’s algorithm consists of recursively replacing the pair (a, b) by (b, rem(a, b)) (where «rem(a, b)» denotes the remainder of the Euclidean division, computed by the algorithm of the preceding section), until b = 0. The GCD is the last non zero remainder.

Euclid’s algorithm may be formalized in the recursive programming style as:

{displaystyle gcd(a,b):={text{if }}b=0{text{ then }}a{text{ else }}gcd(b,operatorname {rem} (a,b)).}

In the imperative programming style, the same algorithm becomes, giving a name to each intermediate remainder:

begin{align} r_0:=a\ r_1:=b end{align}

for (i:=1; r_i neq 0; i:=i+1) do
    {displaystyle {begin{aligned}r_{i+1}&:=operatorname {rem} (r_{i-1},r_{i})end{aligned}}}
end do

return (r_{i-1}).

The sequence of the degrees of the ri is strictly decreasing. Thus after, at most, deg(b) steps, one get a null remainder, say rk. As (a, b) and (b, rem(a,b)) have the same divisors, the set of the common divisors is not changed by Euclid’s algorithm and thus all pairs (ri, ri+1) have the same set of common divisors. The common divisors of a and b are thus the common divisors of rk−1 and 0. Thus rk−1 is a GCD of a and b.
This not only proves that Euclid’s algorithm computes GCDs but also proves that GCDs exist.

Bézout’s identity and extended GCD algorithm[edit]

Bézout’s identity is a GCD related theorem, initially proved for the integers, which is valid for every principal ideal domain. In the case of the univariate polynomials over a field, it may be stated as follows.

If g is the greatest common divisor of two polynomials a and b (not both zero), then there are two polynomials u and v such that

{displaystyle au+bv=gquad } (Bézout’s identity)

and either u = 1, v = 0, or u = 0, v = 1, or

deg(u)<deg(b)-deg(g), quad deg(v)<deg(a)-deg(g).

The interest of this result in the case of the polynomials is that there is an efficient algorithm to compute the polynomials u and v, This algorithm differs from Euclid’s algorithm by a few more computations done at each iteration of the loop. It is therefore called extended GCD algorithm. Another difference with Euclid’s algorithm is that it also uses the quotient, denoted «quo», of the Euclidean division instead of only the remainder. This algorithm works as follows.

Extended GCD algorithm

Input: a, b, univariate polynomials

Output:
    g, the GCD of a and b
    u, v, as in above statement
    a1, b1, such that
        {displaystyle {begin{aligned}a=ga_{1}\b=gb_{1}end{aligned}}}
Begin
    {displaystyle {begin{array}{ll}r_{0}=a&r_{1}=b\s_{0}=1&s_{1}=0\t_{0}=0&t_{1}=1end{array}}}
  
    for (i = 1; ri ≠ 0; i = i+1) do
        {displaystyle q=operatorname {quo} (r_{i-1},r_{i})}
        {displaystyle {begin{aligned}r_{i+1}&=r_{i-1}-qr_{i}\s_{i+1}&=s_{i-1}-qs_{i}\t_{i+1}&=t_{i-1}-qt_{i}end{aligned}}}
    end do
    {displaystyle {begin{aligned}g&=r_{i-1}\u&=s_{i-1}\v&=t_{i-1}end{aligned}}}
    {displaystyle {begin{aligned}a_{1}&=(-1)^{i-1}t_{i}\b_{1}&=(-1)^{i}s_{i}end{aligned}}}
end

The proof that the algorithm satisfies its output specification relies on the fact that, for every i we have

r_i=as_i+bt_i
s_it_{i+1}-t_is_{i+1}=s_it_{i-1}-t_is_{i-1},

the latter equality implying

s_it_{i+1}-t_is_{i+1}=(-1)^i.

The assertion on the degrees follows from the fact that, at every iteration, the degrees of si and ti increase at most as the degree of ri decreases.

An interesting feature of this algorithm is that, when the coefficients of Bezout’s identity are needed, one gets for free the quotient of the input polynomials by their GCD.

Arithmetic of algebraic extensions[edit]

An important application of the extended GCD algorithm is that it allows one to compute division in algebraic field extensions.

Let L an algebraic extension of a field K, generated by an element whose minimal polynomial f has degree n. The elements of L are usually represented by univariate polynomials over K of degree less than n.

The addition in L is simply the addition of polynomials:

a+_Lb=a+_{K[X]}b.

The multiplication in L is the multiplication of polynomials followed by the division by f:

{displaystyle acdot _{L}b=operatorname {rem} (a._{K[X]}b,f).}

The inverse of a non zero element a of L is the coefficient u in Bézout’s identity au + fv = 1, which may be computed by extended GCD algorithm. (the GCD is 1 because the minimal polynomial f is irreducible). The degrees inequality in the specification of extended GCD algorithm shows that a further division by f is not needed to get deg(u) < deg(f).

Subresultants[edit]

In the case of univariate polynomials, there is a strong relationship between the greatest common divisors and resultants. More precisely, the resultant of two polynomials P, Q is a polynomial function of the coefficients of P and Q which has the value zero if and only if the GCD of P and Q is not constant.

The subresultants theory is a generalization of this property that allows characterizing generically the GCD of two polynomials, and the resultant is the 0-th subresultant polynomial.[1]

The i-th subresultant polynomial Si(P ,Q) of two polynomials P and Q is a polynomial of degree at most i whose coefficients are polynomial functions of the coefficients of P and Q, and the i-th principal subresultant coefficient si(P ,Q) is the coefficient of degree i of Si(P, Q). They have the property that the GCD of P and Q has a degree d if and only if

s_0(P,Q)=cdots=s_{d-1}(P,Q) =0  , s_d(P,Q)neq 0.

In this case, Sd(P ,Q) is a GCD of P and Q and

S_0(P,Q)=cdots=S_{d-1}(P,Q) =0.

Every coefficient of the subresultant polynomials is defined as the determinant of a submatrix of the Sylvester matrix of P and Q. This implies that subresultants «specialize» well. More precisely, subresultants are defined for polynomials over any commutative ring R, and have the following property.

Let φ be a ring homomorphism of R into another commutative ring S. It extends to another homomorphism, denoted also φ between the polynomials rings over R and S. Then, if P and Q are univariate polynomials with coefficients in R such that

deg(P)=deg(varphi(P))

and

deg(Q)=deg(varphi(Q)),

then the subresultant polynomials and the principal subresultant coefficients of φ(P) and φ(Q) are the image by φ of those of P and Q.

The subresultants have two important properties which make them fundamental for the computation on computers of the GCD of two polynomials with integer coefficients.
Firstly, their definition through determinants allows bounding, through Hadamard inequality, the size of the coefficients of the GCD.
Secondly, this bound and the property of good specialization allow computing the GCD of two polynomials with integer coefficients through modular computation and Chinese remainder theorem (see below).

Technical definition[edit]

Let

P=p_0+p_1 X+cdots +p_m X^m,quad Q=q_0+q_1 X+cdots +q_n X^n.

be two univariate polynomials with coefficients in a field K. Let us denote by {mathcal {P}}_{i} the K vector space of dimension i of polynomials of degree less than i. For non-negative integer i such that im and in, let

varphi_i:mathcal{P}_{n-i} times mathcal{P}_{m-i} rightarrow mathcal{P}_{m+n-i}

be the linear map such that

varphi_i(A,B)=AP+BQ.

The resultant of P and Q is the determinant of the Sylvester matrix, which is the (square) matrix of varphi _{0} on the bases of the powers of X. Similarly, the i-subresultant polynomial is defined in term of determinants of submatrices of the matrix of varphi_i.

Let us describe these matrices more precisely;

Let pi = 0 for i < 0 or i > m, and qi = 0 for i < 0 or i > n. The Sylvester matrix is the (m + n) × (m + n)-matrix such that the coefficient of the i-th row and the j-th column is pm+ji for jn and qji for j > n:[2]

S=begin{pmatrix} 
p_m     & 0       & cdots & 0       & q_n     & 0       & cdots & 0       \
p_{m-1} & p_m     & cdots & 0       & q_{n-1} & q_n     & cdots & 0  \
p_{m-2} & p_{m-1} & ddots & 0       & q_{n-2} & q_{n-1} & ddots & 0 \
vdots  &vdots   & ddots & p_m     & vdots  &vdots   & ddots & q_n  \
vdots  &vdots   & cdots & p_{m-1} & vdots  &vdots   & cdots & q_{n-1}\
p_0     & p_1     & cdots & vdots  & q_0     & q_1     & cdots & vdots\
0       & p_0     & ddots &  vdots & 0       & q_0     & ddots &  vdots & \
vdots  & vdots  & ddots & p_1     & vdots  & vdots  & ddots & q_1   \
0       & 0       & cdots & p_0     & 0       & 0       & cdots & q_0   
end{pmatrix}.

The matrix Ti of varphi _{i} is the (m + ni) × (m + n − 2i)-submatrix of S which is obtained by removing the last i rows of zeros in the submatrix of the columns 1 to ni and n + 1 to m + ni of S (that is removing i columns in each block and the i last rows of zeros). The principal subresultant coefficient si is the determinant of the m + n − 2i first rows of Ti.

Let Vi be the (m + n − 2i) × (m + ni) matrix defined as follows. First we add (i + 1) columns of zeros to the right of the (m + n − 2i − 1) × (m + n − 2i − 1) identity matrix. Then we border the bottom of the resulting matrix by a row consisting in (m + ni − 1) zeros followed by Xi, Xi−1, …, X, 1:

V_i=begin{pmatrix} 
1       & 0       & cdots & 0       & 0       & 0      & cdots & 0 \
0       & 1       & cdots & 0       & 0       & 0      & cdots & 0 \
vdots  &vdots   & ddots & vdots  & vdots  &ddots  & vdots & 0 \
0       & 0       & cdots & 1       & 0       & 0      & cdots & 0 \
0       & 0       & cdots & 0       & X^i     & X^{i-1}& cdots & 1 
end{pmatrix}.

With this notation, the i-th subresultant polynomial is the determinant of the matrix product ViTi. Its coefficient of degree j is the determinant of the square submatrix of Ti consisting in its m + n − 2i − 1 first rows and the (m + nij)-th row.

Sketch of the proof[edit]

It is not obvious that, as defined, the subresultants have the desired properties. Nevertheless, the proof is rather simple if the properties of linear algebra and those of polynomials are put together.

As defined, the columns of the matrix Ti are the vectors of the coefficients of some polynomials belonging to the image of varphi _{i}. The definition of the i-th subresultant polynomial Si shows that the vector of its coefficients is a linear combination of these column vectors, and thus that Si belongs to the image of varphi_i.

If the degree of the GCD is greater than i, then Bézout’s identity shows that every non zero polynomial in the image of varphi _{i} has a degree larger than i. This implies that Si=0.

If, on the other hand, the degree of the GCD is i, then Bézout’s identity again allows proving that the multiples of the GCD that have a degree lower than m + ni are in the image of varphi _{i}. The vector space of these multiples has the dimension m + n − 2i and has a base of polynomials of pairwise different degrees, not smaller than i. This implies that the submatrix of the m + n − 2i first rows of the column echelon form of Ti is the identity matrix and thus that si is not 0. Thus Si is a polynomial in the image of varphi _{i}, which is a multiple of the GCD and has the same degree. It is thus a greatest common divisor.

GCD and root finding[edit]

Square-free factorization[edit]

Most root-finding algorithms behave badly with polynomials that have multiple roots. It is therefore useful to detect and remove them before calling a root-finding algorithm. A GCD computation allows detection of the existence of multiple roots, since the multiple roots of a polynomial are the roots of the GCD of the polynomial and its derivative.

After computing the GCD of the polynomial and its derivative, further GCD computations provide the complete square-free factorization of the polynomial, which is a factorization

f=prod_{i=1}^{deg(f)} f_i^i

where, for each i, the polynomial fi either is 1 if f does not have any root of multiplicity i or is a square-free polynomial (that is a polynomial without multiple root) whose roots are exactly the roots of multiplicity i of f (see Yun’s algorithm).

Thus the square-free factorization reduces root-finding of a polynomial with multiple roots to root-finding of several square-free polynomials of lower degree. The square-free factorization is also the first step in most polynomial factorization algorithms.

Sturm sequence[edit]

The Sturm sequence of a polynomial with real coefficients is the sequence of the remainders provided by a variant of Euclid’s algorithm applied to the polynomial and its derivative. For getting the Sturm sequence, one simply replaces the instruction

{displaystyle r_{i+1}:=operatorname {rem} (r_{i-1},r_{i})}

of Euclid’s algorithm by

{displaystyle r_{i+1}:=-operatorname {rem} (r_{i-1},r_{i}).}

Let V(a) be the number of changes of signs in the sequence, when evaluated at a point a. Sturm’s theorem asserts that V(a) − V(b) is the number of real roots of the polynomial in the interval [a, b]. Thus the Sturm sequence allows computing the number of real roots in a given interval. By subdividing the interval until every subinterval contains at most one root, this provides an algorithm that locates the real roots in intervals of arbitrary small length.

GCD over a ring and its field of fractions[edit]

In this section, we consider polynomials over a unique factorization domain R, typically the ring of the integers, and over its field of fractions F, typically the field of the rational numbers, and we denote R[X] and F[X] the rings of polynomials in a set of variables over these rings.

Primitive part–content factorization[edit]

The content of a polynomial pR[X], denoted «cont(p)», is the GCD of its coefficients. A polynomial qF[X] may be written

q = frac{p}{c}

where pR[X] and cR: it suffices to take for c a multiple of all denominators of the coefficients of q (for example their product) and p = cq. The content of q is defined as:

{displaystyle operatorname {cont} (q)={frac {operatorname {cont} (p)}{c}}.}

In both cases, the content is defined up to the multiplication by a unit of R.

The primitive part of a polynomial in R[X] or F[X] is defined by

{displaystyle operatorname {primpart} (p)={frac {p}{operatorname {cont} (p)}}.}

In both cases, it is a polynomial in R[X] that is primitive, which means that 1 is a GCD of its coefficients.

Thus every polynomial in R[X] or F[X] may be factorized as

{displaystyle p=operatorname {cont} (p),operatorname {primpart} (p),}

and this factorization is unique up to the multiplication of the content by a unit of R and of the primitive part by the inverse of this unit.

Gauss’s lemma implies that the product of two primitive polynomials is primitive. It follows that

{displaystyle operatorname {primpart} (pq)=operatorname {primpart} (p)operatorname {primpart} (q)}

and

{displaystyle operatorname {cont} (pq)=operatorname {cont} (p)operatorname {cont} (q).}

Relation between the GCD over R and over F[edit]

The relations of the preceding section imply a strong relation between the GCD’s in R[X] and in F[X]. To avoid ambiguities, the notation «gcd» will be indexed, in the following, by the ring in which the GCD is computed.

If q1 and q2 belong to F[X], then

{displaystyle operatorname {primpart} (gcd _{F[X]}(q_{1},q_{2}))=gcd _{R[X]}(operatorname {primpart} (q_{1}),operatorname {primpart} (q_{2})).}

If p1 and p2 belong to R[X], then

{displaystyle gcd _{R[X]}(p_{1},p_{2})=gcd _{R}(operatorname {cont} (p_{1}),operatorname {cont} (p_{2}))gcd _{R[X]}(operatorname {primpart} (p_{1}),operatorname {primpart} (p_{2})),}

and

{displaystyle gcd _{R[X]}(operatorname {primpart} (p_{1}),operatorname {primpart} (p_{2}))=operatorname {primpart} (gcd _{F[X]}(p_{1},p_{2})).}

Thus the computation of polynomial GCD’s is essentially the same problem over F[X] and over R[X].

For univariate polynomials over the rational numbers, one may think that Euclid’s algorithm is a convenient method for computing the GCD. However, it involves simplifying a large number of fractions of integers, and the resulting algorithm is not efficient. For this reason, methods have been designed to modify Euclid’s algorithm for working only with polynomials over the integers. They consist of replacing the Euclidean division, which introduces fractions, by a so-called pseudo-division, and replacing the remainder sequence of the Euclid’s algorithm by so-called pseudo-remainder sequences (see below).

Proof that GCD exists for multivariate polynomials[edit]

In the previous section we have seen that the GCD of polynomials in R[X] may be deduced from GCDs in R and in F[X]. A closer look on the proof shows that this allows us to prove the existence of GCDs in R[X], if they exist in R and in F[X]. In particular, if GCDs exist in R, and if X is reduced to one variable, this proves that GCDs exist in R[X] (Euclid’s algorithm proves the existence of GCDs in F[X]).

A polynomial in n variables may be considered as a univariate polynomial over the ring of polynomials in (n − 1) variables. Thus a recursion on the number of variables shows that if GCDs exist and may be computed in R, then they exist and may be computed in every multivariate polynomial ring over R. In particular, if R is either the ring of the integers or a field, then GCDs exist in R[x1,…, xn], and what precedes provides an algorithm to compute them.

The proof that a polynomial ring over a unique factorization domain is also a unique factorization domain is similar, but it does not provide an algorithm, because there is no general algorithm to factor univariate polynomials over a field (there are examples of fields for which there does not exist any factorization algorithm for the univariate polynomials).

Pseudo-remainder sequences[edit]

In this section, we consider an integral domain Z (typically the ring Z of the integers) and its field of fractions Q (typically the field Q of the rational numbers). Given two polynomials A and B in the univariate polynomial ring Z[X], the Euclidean division (over Q) of A by B provides a quotient and a remainder which may not belong to Z[X].

For, if one applies Euclid’s algorithm to the following polynomials [3]

X^8+X^6-3 X^4-3 X^3+8 X^2+2 X-5

and

3 X^6+5 X^4-4 X^2-9 X+21,

the successive remainders of Euclid’s algorithm are

{displaystyle {begin{aligned}&-{tfrac {5}{9}}X^{4}+{tfrac {1}{9}}X^{2}-{tfrac {1}{3}},\&-{tfrac {117}{25}}X^{2}-9X+{tfrac {441}{25}},\&{tfrac {233150}{19773}}X-{tfrac {102500}{6591}},\&-{tfrac {1288744821}{543589225}}.end{aligned}}}

One sees that, despite the small degree and the small size of the coefficients of the input polynomials, one has to manipulate and simplify integer fractions of rather large size.


The pseudo-division has been introduced to allow a variant of Euclid’s algorithm for which all remainders belong to Z[X].

If deg(A)=a and deg(B)=b and ab, the pseudo-remainder of the pseudo-division of A by B, denoted by prem(A,B) is

{displaystyle operatorname {prem} (A,B)=operatorname {rem} (operatorname {lc} (B)^{a-b+1}A,B),}

where lc(B) is the leading coefficient of B (the coefficient of Xb).

The pseudo-remainder of the pseudo-division of two polynomials in Z[X] belongs always to Z[X].

A pseudo-remainder sequence is the sequence of the (pseudo) remainders ri obtained by replacing the instruction

{displaystyle r_{i+1}:=operatorname {rem} (r_{i-1},r_{i})}

of Euclid’s algorithm by

{displaystyle r_{i+1}:={frac {operatorname {prem} (r_{i-1},r_{i})}{alpha }},}

where α is an element of Z that divides exactly every coefficient of the numerator. Different choices of α give different pseudo-remainder sequences, which are described in the next subsections.

As the common divisors of two polynomials are not changed if the polynomials are multiplied by invertible constants (in Q), the last nonzero term in a pseudo-remainder sequence is a GCD (in Q[X]) of the input polynomials. Therefore, pseudo-remainder sequences allows computing GCD’s in Q[X] without introducing fractions in Q.

In some contexts, it is essential to control the sign of the leading coefficient of the pseudo-remainder. This is typically the case when computing resultants and subresultants, or for using Sturm’s theorem. This control can be done either by replacing lc(B) by its absolute value in the definition of the pseudo-remainder, or by controlling the sign of α (if α divides all coefficients of a remainder, the same is true for α).[1]

Trivial pseudo-remainder sequence[edit]

The simplest (to define) remainder sequence consists in taking always α = 1. In practice, it is not interesting, as the size of the coefficients grows exponentially with the degree of the input polynomials. This appears clearly on the example of the preceding section, for which the successive pseudo-remainders are

-15, X^4+3, X^2-9,
15795, X^2+30375, X-59535,
1254542875143750, X-1654608338437500,
12593338795500743100931141992187500.

The number of digits of the coefficients of the successive remainders is more than doubled at each iteration of the algorithm. This is typical behavior of the trivial pseudo-remainder sequences.

Primitive pseudo-remainder sequence[edit]

The primitive pseudo-remainder sequence consists in taking for α the content of the numerator. Thus all the ri are primitive polynomials.

The primitive pseudo-remainder sequence is the pseudo-remainder sequence, which generates the smallest coefficients. However it requires to compute a number of GCD’s in Z, and therefore is not sufficiently efficient to be used in practice, especially when Z is itself a polynomial ring.

With the same input as in the preceding sections, the successive remainders, after division by their content are

-5,X^4+X^2-3,
13,X^2+25,X-49,
4663,X-6150,
1.

The small size of the coefficients hides the fact that a number of integers GCD and divisions by the GCD have been computed.

Subresultant pseudo-remainder sequence[edit]

A subresultant sequence can be also computed with pseudo-remainders. The process consists in choosing α in such a way that every ri is a subresultant polynomial. Surprisingly, the computation of α is very easy (see below). On the other hand, the proof of correctness of the algorithm is difficult, because it should take into account all the possibilities for the difference of degrees of two consecutive remainders.

The coefficients in the subresultant sequence are rarely much larger than those of the primitive pseudo-remainder sequence. As GCD computations in Z are not needed, the subresultant sequence with pseudo-remainders gives the most efficient computation.

With the same input as in the preceding sections, the successive remainders are

15,X^4-3,X^2+9,
65,X^2+125,X-245,
9326,X-12300,
260708.

The coefficients have a reasonable size. They are obtained without any GCD computation, only exact divisions. This makes this algorithm more efficient than that of primitive pseudo-remainder sequences.

The algorithm computing the subresultant sequence with pseudo-remainders is given below. In this algorithm, the input (a, b) is a pair of polynomials in Z[X]. The ri are the successive pseudo remainders in Z[X], the variables i and di are non negative integers, and the Greek letters denote elements in Z. The functions deg() and rem() denote the degree of a polynomial and the remainder of the Euclidean division. In the algorithm, this remainder is always in Z[X]. Finally the divisions denoted / are always exact and have their result either in Z[X] or in Z.

begin{align}r_0:=a\ r_1:=b end{align}
for (i:=1; r_i neq 0; i:=i+1;) do
    {displaystyle {begin{aligned}d_{i}&:=deg(r_{i-1})-deg(r_{i})\gamma _{i}&:=operatorname {lc} (r_{i})end{aligned}}}
    if i=1 then
        begin{align} beta_1&:=(-1)^{d_1+1}\ psi_1&:=-1 end{align}
    else
        {displaystyle {begin{aligned}psi _{i}&:={frac {(-gamma _{i-1})^{d_{i-1}}}{psi _{i-1}^{d_{i-1}-1}}}\beta _{i}&:=-gamma _{i-1}psi _{i}^{d_{i}}end{aligned}}}
    end if
    {displaystyle r_{i+1}:={frac {operatorname {rem} (gamma _{i}^{d_{i}+1}r_{i-1},r_{i})}{beta _{i}}}}
end do.

Note: «lc» stands for the leading coefficient, the coefficient of the highest degree of the variable.

This algorithm computes not only the greatest common divisor (the last non zero ri), but also all the subresultant polynomials: The remainder ri is the (deg(ri−1) − 1)-th subresultant polynomial. If deg(ri) < deg(ri−1) − 1, the deg(ri)-th subresultant polynomial is lc(ri)deg(ri−1)−deg(ri)−1ri. All the other subresultant polynomials are zero.

Sturm sequence with pseudo-remainders[edit]

One may use pseudo-remainders for constructing sequences having the same properties as Sturm sequences. This requires to control the signs of the successive pseudo-remainders, in order to have the same signs as in the Sturm sequence. This may be done by defining a modified pseudo-remainder as follows.

If deg(A)=a and deg(B)=b and ab, the modified pseudo-remainder prem2(A, B) of the pseudo-division of A by B is

operatorname {prem2}(A,B)=-operatorname {rem}(|operatorname {lc}(B)|^{{a-b+1}}A,B),

where |lc(B)| is the absolute value of the leading coefficient of B (the coefficient of Xb).

For input polynomials with integer coefficients, this allows retrieval of Sturm sequences consisting of polynomials with integer coefficients. The subresultant pseudo-remainder sequence may be modified similarly, in which case the signs of the remainders coincide with those computed over the rationals.

Note that the algorithm for computing the subresultant pseudo-remainder sequence given above will compute wrong subresultant polynomials if one uses {displaystyle -mathrm {prem2} (A,B)} instead of operatorname {prem}(A,B).

Modular GCD algorithm[edit]

If f and g are polynomials in F[x] for some finitely generated field F, the Euclidean Algorithm is the most natural way to compute their GCD. However, modern computer algebra systems only use it if F is finite because of a phenomenon called intermediate expression swell. Although degrees keep decreasing during the Euclidean algorithm, if F is not finite then the bit size of the polynomials can increase (sometimes dramatically) during the computations because repeated arithmetic operations in F tends to lead to larger expressions. For example, the addition of two rational numbers whose denominators are bounded by b leads to a rational number whose denominator is bounded by b2, so in the worst case, the bit size could nearly double with just one operation.

To expedite the computation, take a ring D for which f and g are in D[x], and take an ideal I such that D/I is a finite ring. Then compute the GCD over this finite ring with the Euclidean Algorithm. Using reconstruction techniques (Chinese remainder theorem, rational reconstruction, etc.) one can recover the GCD of f and g from its image modulo a number of ideals I. One can prove[4] that this works provided that one discards modular images with non-minimal degrees, and avoids ideals I modulo which a leading coefficient vanishes.

Suppose F = mathbb{Q}(sqrt{3}), D = mathbb{Z}[sqrt{3}], f = sqrt{3}x^3 - 5 x^2 + 4x + 9 and g = x^4 + 4 x^2 + 3sqrt{3}x - 6. If we take I=(2) then D/I is a finite ring (not a field since I is not maximal in D). The Euclidean algorithm applied to the images of f,g in (D/I)[x] succeeds and returns 1. This implies that the GCD of f,g in F[x] must be 1 as well. Note that this example could easily be handled by any method because the degrees were too small for expression swell to occur, but it illustrates that if two polynomials have GCD 1, then the modular algorithm is likely to terminate after a single ideal I.

See also[edit]

  • List of polynomial topics
  • Multivariate division algorithm

References[edit]

  1. ^ a b Basu, Pollack & Roy 2006
  2. ^ Many author define the Sylvester matrix as the transpose of S. This breaks the usual convention for writing the matrix of a linear map.
  3. ^ Knuth 1969
  4. ^ van Hoeij & Monagan 2004
  • Basu, Saugata; Pollack, Richard; Roy, Marie-Françoise (2006). Algorithms in real algebraic geometry, chapter 4.2. Springer-Verlag.
  • Davenport, James H.; Siret, Yvon; Tournier, Évelyne (1988). Computer algebra: systems and algorithms for algebraic computation. Translated from the French by A. Davenport and J.H. Davenport. Academic Press. ISBN 978-0-12-204230-0.
  • van Hoeij, M.; Monagan, M.B. (2004). Algorithms for polynomial GCD computation over algebraic function fields. ISSAC 2004. pp. 297–304.
  • Javadi, S.M.M.; Monagan, M.B. (2007). A sparse modular GCD algorithm for polynomials over algebraic function fields. ISSAC 2007. pp. 187–194.
  • Knuth, Donald E. (1969). The Art of Computer Programming II. Addison-Wesley. pp. 370–371.
  • Knuth, Donald E. (1997). Seminumerical Algorithms. The Art of Computer Programming. Vol. 2 (Third ed.). Reading, Massachusetts: Addison-Wesley. pp. 439–461, 678–691. ISBN 0-201-89684-2.
  • Loos, Rudiger (1982), «Generalized polynomial remainder sequences», in B. Buchberger; R. Loos; G. Collins (eds.), Computer Algebra, Springer Verlag

Алгори́тм Евкли́да — эффективный алгоритм для нахождения наибольшего общего делителя двух целых чисел (или общей меры двух отрезков). Алгоритм назван в честь греческого математика Евклида (III век до н. э.), который впервые описал его в VII[1] и X[2] книгах «Начал». Это один из старейших численных алгоритмов, используемых в наше время[3].

В самом простом случае алгоритм Евклида применяется к паре положительных целых чисел и формирует новую пару, которая состоит из меньшего числа и разницы между большим и меньшим числом. Процесс повторяется, пока числа не станут равными. Найденное число и есть наибольший общий делитель исходной пары. Евклид предложил алгоритм только для натуральных чисел и геометрических величин (длин, площадей, объёмов). Однако в XIX веке он был обобщён на другие типы математических объектов, включая целые числа Гаусса и полиномы от одной переменной. Это привело к появлению в современной общей алгебре такого понятия, как евклидово кольцо. Позже алгоритм Евклида был обобщён на другие математические структуры, такие как узлы и многомерные полиномы.

Для данного алгоритма существует множество теоретических и практических применений. В частности, он является основой для криптографического алгоритма с открытым ключом RSA[4], широко распространённого в электронной коммерции. Также алгоритм используется при решении линейных диофантовых уравнений[5], при построении непрерывных дробей[6], в методе Штурма[7]. Алгоритм Евклида является основным инструментом для доказательства теорем в современной теории чисел, например таких как теорема Лагранжа о сумме четырёх квадратов[8] и основная теорема арифметики[9].

История[править | править код]

Древнегреческие математики называли этот алгоритм ἀνθυφαίρεσις или ἀνταναίρεσις — «взаимное вычитание». Этот алгоритм не был открыт Евклидом, так как упоминание о нём имеется уже в Топике Аристотеля (IV век до н. э.)[3]. В «Началах» Евклида он описан дважды — в VII книге для нахождения наибольшего общего делителя двух натуральных чисел[1] и в X книге для нахождения наибольшей общей меры двух однородных величин[2]. В обоих случаях дано геометрическое описание алгоритма, для нахождения «общей меры» двух отрезков.

Историками математики было выдвинуто предположение, что именно с помощью алгоритма Евклида (процедуры последовательного взаимного вычитания) в древнегреческой математике впервые было открыто существование несоизмеримых величин (стороны и диагонали квадрата, или стороны и диагонали правильного пятиугольника)[10]. Впрочем, это предположение не имеет достаточных документальных подтверждений. Алгоритм для поиска наибольшего общего делителя двух натуральных чисел описан также в I книге древнекитайского трактата Математика в девяти книгах.

Описание[править | править код]

Алгоритм Евклида для целых чисел[править | править код]

Пусть a и b — целые числа, не равные одновременно нулю, и последовательность чисел

{displaystyle a>b>r_{1}>r_{2}>r_{3}>r_{4}> dots  >r_{n}}

определена тем, что каждое r_{k} — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть:

a=bq_{0}+r_{1},
b=r_{1}q_{1}+r_{2},
r_{1}=r_{2}q_{2}+r_{3},
cdots
r_{k-2}=r_{k-1}q_{k-1}+r_{k},
cdots
r_{n-2}=r_{n-1}q_{n-1}+r_{n},
r_{n-1}=r_{n}q_{n}.

Тогда НОД(a, b), наибольший общий делитель a и b, равен rn, последнему ненулевому члену этой последовательности[11].

Существование таких r1, r2, …, rn, то есть возможность деления с остатком m на n для любого целого m и целого n ≠ 0, доказывается индукцией по m.

Корректность этого алгоритма вытекает из следующих двух утверждений[12]:

I. Пусть a = bq + r, тогда НОД (a, b) = НОД (b, r).

Доказательство

  1. Пусть k — любой общий делитель чисел a и b, не обязательно наибольший, тогда a = t1k и b = t2k, где t1 и t2 — целые числа из определения.
  2. Тогда k является также общим делителем чисел b и r, так как b делится на k по определению, а {displaystyle r=a-bcdot q=(t_{1}-t_{2}cdot q)cdot k} (выражение в скобках есть целое число, следовательно, k делит r без остатка).
  3. Обратное также верно и доказывается аналогично пункту 2: любой делитель b и r так же является делителем a и b.
  4. Следовательно, все общие делители пар чисел (a, b) и (b, r) совпадают. Другими словами, нет общего делителя у чисел (a, b), который не был бы также делителем (b, r), и наоборот.
  5. В частности, наибольший общий делитель остаётся тем же самым, так как в предположении, что НОД (a, b) > НОД (b, r) или НОД (a, b) < НОД (b, r) получаются противоречия, следовательно, НОД (a, b) = НОД (b, r). Что и требовалось доказать.

II. НОД(r, 0) = r для любого ненулевого r (так как 0 делится на любое целое число).

Геометрический алгоритм Евклида[править | править код]

Пусть даны два отрезка длины a и b. Вычтем из большего отрезка меньший и заменим больший отрезок полученной разностью. Повторяем эту операцию, вычитая из большего отрезка меньший, пока отрезки не станут равны. Если это произойдёт, то исходные отрезки соизмеримы, и последний полученный отрезок есть их наибольшая общая мера. Если общей меры нет, то процесс бесконечен. В таком виде алгоритм описан Евклидом[2] и реализуется с помощью циркуля и линейки.

Пример[править | править код]

Для иллюстрации алгоритм Евклида будет использован, чтобы найти НОД a = 1071 и b = 462. Для начала от 1071 отнимем кратное значение 462, пока не получим разность меньше, чем 462. Мы должны дважды отнять 462, (q0 = 2), оставаясь с остатком 147:

1071 = 2 × 462 + 147.

Затем от 462 отнимем кратное значение 147, пока не получим разность меньше, чем 147. Мы должны трижды отнять 147 (q1 = 3), оставаясь с остатком 21:

462 = 3 × 147 + 21.

Затем от 147 отнимем кратное значение 21, пока не получим разность меньше, чем 21. Мы должны семь раз отнять 21 (q2 = 7), оставаясь без остатка:

147 = 7 × 21 + 0.

Таким образом последовательность a > b > r1 > r2 > r3 > … > rn в данном конкретном случае будет выглядеть так:

1071 > 462 > 147 > 21.

Так как последний остаток равен нулю, алгоритм заканчивается числом 21 и НОД(1071, 462) = 21.

В табличной форме шаги были следующие:

Шаг k Равенство Частное и остаток
0 1071 = q0 462 + r0 q0 = 2 и r0 = 147
1 462 = q1 147 + r1 q1 = 3 и r1 = 21
2 147 = q2 21 + r2 q2 = 7 и r2 = 0; алгоритм заканчивается

Если требуется найти НОД для более чем двух чисел, алгоритм аналогичен, на каждом шаге все числа, кроме
наименьшего, заменяются остатками по модулю наименьшего. Нулевые остатки, если получатся, вычёркиваются. Алгоритм завершается, когда остаётся одно ненулевое число, это и есть НОД.

Применения[править | править код]

Расширенный алгоритм Евклида и соотношение Безу[править | править код]

Формулы для r_{i} могут быть переписаны следующим образом:

r_{1}=a+b(-q_{0})
r_{2}=b-r_{1}q_{1}=a(-q_{1})+b(1+q_{1}q_{0})
vdots
НОД (a,b)=r_{n}=as+bt

Здесь s и t целые. Это представление наибольшего общего делителя называется соотношением Безу, а числа s и t — коэффициентами Безу[13]. Соотношение Безу является ключевым в доказательстве леммы Евклида и основной теоремы арифметики.

Цепные дроби[править | править код]

Алгоритм Евклида достаточно тесно связан с цепными дробями[6]. Отношение a/b допускает представление в виде цепной дроби:

{frac {a}{b}}=[q_{0};q_{1},q_{2},cdots ,q_{n}].

При этом цепная дробь без последнего члена равна отношению коэффициентов Безу t/s, взятому со знаком минус:

[q_{0};q_{1},q_{2},cdots ,q_{n-1}]=-{frac {t}{s}}.

Последовательность равенств, задающая алгоритм Евклида, может быть переписана в форме:

{begin{aligned}{frac {a}{b}}&=q_{0}+{frac {r_{0}}{b}}\{frac {b}{r_{0}}}&=q_{1}+{frac {r_{1}}{r_{0}}}\{frac {r_{0}}{r_{1}}}&=q_{2}+{frac {r_{2}}{r_{1}}}\&{} vdots \{frac {r_{k-2}}{r_{k-1}}}&=q_{k}+{frac {r_{k}}{r_{k-1}}}\&{} vdots \{frac {r_{N-2}}{r_{N-1}}}&=q_{N}end{aligned}}

Последнее слагаемое в правой части равенства всегда равно обратному значению левой части следующего уравнения. Поэтому первые два уравнения могут быть объединены в форме:

{frac {a}{b}}=q_{0}+{cfrac {1}{q_{1}+{cfrac {r_{1}}{r_{0}}}}}

Третье равенство может быть использовано, чтобы заменить знаменатель выражения r1/r0, получим:

{frac {a}{b}}=q_{0}+{cfrac {1}{q_{1}+{cfrac {1}{q_{2}+{cfrac {r_{2}}{r_{1}}}}}}}

Последнее отношение остатков rk/rk−1 всегда может быть заменено с использованием следующего равенства в последовательности, и так до последнего уравнения. Результатом является цепная дробь:

{frac {a}{b}}=q_{0}+{cfrac {1}{q_{1}+{cfrac {1}{q_{2}+{cfrac {1}{ddots +{cfrac {1}{q_{N}}}}}}}}}=[q_{0};q_{1},q_{2},ldots ,q_{N}]

В приведённом выше примере НОД(1071, 462) был посчитан и были найдены частные qk, равные 2, 3 и 7 соответственно. Поэтому 1071/462 может быть записана как:

{displaystyle {frac {1071}{462}}=2+{cfrac {1}{3+{cfrac {1}{7}}}}=[2;3;7]}

Линейные диофантовы уравнения[править | править код]

Диофантово уравнение — это уравнение с целочисленными коэффициентами и с одним или несколькими переменными, причём ставится задача поиска лишь его целых корней. Такое уравнение может иметь бесконечно много решений, конечное число решений или не иметь их вовсе. Простейшее диофантово уравнение — линейное с двумя неизвестными:

acdot x+bcdot y=c,

где a, b, c — целые числа. С помощью алгоритма Евклида может быть найдено полное решение уравнения такого типа[5]. Сначала с помощью этого алгоритма можно определить d = НОД(a, b). Затем, используя расширенный алгоритм Евклида, определяются такие k и l, что:

acdot k+bcdot l=d.

То есть x = k и y = l — это частное решение уравнения при c = d. Получается, что если c = q⋅d, то x = q⋅k, y = q⋅l — частное решение исходного уравнения, так как:

acdot x+bcdot y=acdot (qcdot k)+bcdot (qcdot l)=qcdot (acdot k+bcdot l)=qcdot d=c.

Обратно, если существует хотя бы одно решение уравнения, то c кратно d. Это следует из того, что d делит и a, и b (а значит, и всю левую часть), поэтому должно делить и c (правую часть). Таким образом, линейное диофантово уравнение имеет хотя бы одно решение тогда и только тогда, когда c кратно НОД(a, b).

Вариации и обобщения[править | править код]

Евклидово кольцо[править | править код]

Кольца, в которых применим алгоритм Евклида, называются евклидовыми кольцами[14]. К ним относятся, в частности, кольца целых чисел и кольца многочленов.

Обобщённый алгоритм Евклида для многочленов[править | править код]

Алгоритм Евклида и расширенный алгоритм Евклида естественным образом обобщается на кольцо многочленов k[x] от одной переменной над произвольным полем k, поскольку для таких многочленов определена операция деления с остатком. При выполнении алгоритма Евклида для многочленов аналогично алгоритму Евклида для целых чисел получается последовательность полиномиальных остатков (PRS)[15].

Пример для кольца Z[x]

Пусть cont(f) по определению — НОД коэффициентов многочлена f(x) из {displaystyle Z[x]} — содержание многочлена. Частное от деления f(x) на cont(f) называется примитивной частью многочлена f(x) и обозначается primpart(f(x)). Эти определения понадобятся для нахождения НОД двух многочленов p1(x) и p2(x) в кольце {displaystyle Z[x]}. Для многочленов над целыми числами верно следующее:

cont(НОД{p_{1}(x),p_{2}(x)})=НОД{cont(p_{1}(x)),cont(p_{2}(x))},

primpart(НОД{p_{1}(x),p_{2}(x)})=НОД{primpart(p_{1}(x)),primpart(p_{2}(x))}.

Таким образом, задача поиска НОД двух произвольных многочленов сводится к задаче поиска НОД примитивных полиномов.

Пусть есть два примитивных многочлена p1(x) и p2(x) из Z[x], для которых выполняется соотношение между их степенями: deg(p1(x)) = m и deg(p2(x)) = n, m > n. Деление многочленов с остатком предполагает точную делимость старшего коэффициента делимого на старший коэффициент делителя, в общем случае деление с остатком выполнить невозможно. Поэтому вводят алгоритм псевдоделения, который всё же позволяет получить псевдочастное и псевдоостаток (prem), которые будут сами по себе принадлежать множеству многочленов над целыми числами.

Под псевдоделением будем понимать, что самому делению предшествует умножение полинома p_{1}(x) на (lc(p_{2}(x)))^{m-n+1}, то есть

lc(p_{2}(x))^{m-n+1}p_{1}(x)=p_{2}(x)q(x)+r_{2}(x),deg(r(x))<deg(p_{2}(x)),

где q(x) и r(x) — соответственно псевдочастное и псевдоостаток.

Итак, p_{1}(x),p_{2}(x)in Z[x], причём deg(p_{1})=n_{1}geq deg(p_{2})=n_{2}. Тогда алгоритм Евклида состоит из следующих шагов:

1. Вычисление НОД содержаний:

c:=НОД{cont(p_{1}),cont(p_{2})}.

2. Вычисление примитивных частей:

p_{1}'(x):=primpart(p_{1}(x));

p_{2}'(x):=primpart(p_{2}(x)).

3. Построение последовательности полиномиальных остатков:

p_{1}'(x),

p_{2}'(x),

p_{3}(x):=prem(p_{1}'(x),p_{2}'(x)),

p_{4}(x):=prem(p_{2}'(x),p_{3}(x)),

p_{5}(x):=prem(p_{3}(x),p_{4}(x)),

...

p_{h}(x):=prem(p_{h-2}(x),p_{h-1}(x)).

4. Возврат результата:

Если deg(p_{h}(x))=0, то вернуть c, иначе вернуть ccdot primpart(p_{h}(x)).

Ускоренные версии алгоритма[править | править код]

  • Одним из методов ускорения целочисленного алгоритма Евклида является использование симметричного остатка[16]:
r_{i}equiv r_{i-2}{pmod {r_{i-1}}},
где

-{frac {r_{i-1}}{2}}leq r_{i}leq {frac {r_{i-1}}{2}}.
  • Одна из версий ускоренного алгоритма Евклида для полиномов основывается на том, что промежуточные значения алгоритма в основном зависят от высоких степеней. Применение стратегии «разделяй и властвуй» позволяет уменьшить асимптотическую сложность алгоритма[16].

Вычислительная сложность алгоритма[править | править код]

"A set of colored lines radiating outwards from the origin of an x-y coordinate system. Each line corresponds to a set of number pairs requiring the same number of steps in the Euclidean algorithm."

Число шагов в алгоритме Евклида для НОД(x,y). Более светлые точки (красные и жёлтые) указывают на относительно меньшее количество шагов, тогда как более тёмные точки (фиолетовые и синие) на большее количество шагов. Самая большая тёмная область следует за прямой y = Φx, где Φ — золотое сечение.

Вычислительная сложность алгоритма Евклида изучена полностью.[17] Эта сложность может быть описана произведением количества шагов деления, требуемых алгоритмом, на вычислительную сложность одного шага. Первый известный анализ алгоритма Евклида был предложен Рейнаудом в 1811.[18] Он показал, что число шагов алгоритма для пары чисел (u, v) ограничено v. Позже он улучшил оценку до v/2 + 2. Эмиль Леже в 1837 году изучил наихудший случай, когда для вычисления НОД подаются последовательные числа Фибоначчи.[19] Затем, в 1841 году, Пьер Джосеф Финк показал,[20] что количество шагов алгоритма не превышает 2 log2 v + 1. Следовательно, алгоритм работает за полиномиальное время от размера меньшего из пары чисел (u, v).[19] Анализ Финка был уточнён Габриэлем Ламе в 1844 году.[21] Он показал, что количество шагов, необходимых для завершения алгоритма, не более чем в пять раз превышает h — количество цифр в десятичном представлении меньшего из пары чисел (u, v).[22][23]

Когда НОД вычисляется для чисел, которые вписываются в одно машинное слово, каждый шаг алгоритма занимает постоянное время. В данном случае анализ Ламе предполагает, что вычислительная сложность оценивается как O(h). Однако в модели расчёта, подходящей для вычислений с числами больше одного машинного слова, оценка сложности вычисления одного остатка может быть O(h2).[24] В этом случае общее время для всех этапов алгоритма можно проанализировать с помощью телескопического ряда, показав, что это также O(h2). Для ускорения алгоритма Евклида могут быть использованы современные алгоритмические методы, основанные на методе Шёнхаге — Штрассена для быстрого целочисленного умножения. Это приводит к квазиполиномиальному времени.[25]

Количество шагов[править | править код]

Число шагов для вычисления НОД двух натуральных чисел a и b обозначим как T(ab). Если g — это наибольший общий делитель a и b, тогда a = mg и b = ng для двух взаимно простых чисел m и n. Тогда T(a, b) = T(m, n), что можно заметить, если разделить уравнения, полученные при вычислении НОД для пары (ab), на g.[26] Используя тот же принцип, число шагов алгоритма остаётся неизменным, если a и b умножаются на общий множитель w, что эквивалентно равенству T(a, b) = T(wa, wb). Следовательно, количество шагов T может сильно различаться между соседними парами чисел, такими как (ab) и (ab+1), так как данная величина зависит от НОД.

Рекурсивный характер алгоритма Евклида даёт следующее уравнение T(a, b) = 1 + T(b, r0) = 2 + T(r0, r1) = … = N + T(rN−2, rN−1) = N + 1, где T(x, 0) = 0 по предположению.[17]

Наихудший случай[править | править код]

Если для алгоритма Евклида требуются N шагов для пары натуральных чисел a > b > 0, наименьшие значения a и b, для которых это выполняется — числа Фибоначчи FN+2 и FN+1 соответственно.[27] Тогда, если алгоритм Евклида требует N шагов для пары чисел (a,b), где a > b, выполняются следующие неравенства a ≥ FN+2 и b ≥ FN+1. Доказать это можно по математической индукции. Если N = 1, тогда a делится на b без остатка. Наименьшие натуральные числа, для которых это верно, равны b = 1 и a = 2, соответственно F2 и F3. Предположим теперь, что результат выполняется для всех значений N до M − 1. Первый шаг алгоритма Евклида с M шагами a = q0b + r0, и алгоритм Евклида для пары чисел (b,r0), где b > r0, требует M − 1 шагов. По предположению индукции имеем b ≥ FM+1 и r0 ≥ FM. Следовательно, a = q0b + r0 ≥ b + r0 ≥ FM+1 + FM = FM+2, что является искомым неравенством. Это доказательство, опубликованное Габриэлем Ламе в 1844 году, представляет собой начало теории сложности вычислений,[28] а также первое практическое применение чисел Фибоначчи.[27]

Теорема Ламе[править | править код]

Число делений с остатком в процессе применения алгоритма Евклида не превосходит упятеренного количества цифр меньшего числа b, записанного в десятичной системе[29].

Среднее[править | править код]

Существуют различные способы вычисления среднего количества шагов алгоритма. Первый способ вычисления — среднее время T(a), необходимое для вычисления НОД заданного числа a и меньшего натурального числа b, выбранного с равной вероятностью из целых чисел от 0 до a − 1.[17]

{displaystyle T(a)={frac {1}{a}}sum _{0leq b<a}T(a,b).}

Однако, поскольку T(a, b) сильно колеблется в зависимости от НОД двух чисел, усреднённая функция T(a) также является «шумной».[30] Для того, чтобы уменьшить этот шум, второе среднее τ(a) берётся по всем числам, взаимно простым с a.

{displaystyle tau (a)={frac {1}{varphi (a)}}sum _{begin{smallmatrix}0leq b<a\gcd(a,b)=1end{smallmatrix}}T(a,b)}

где φ(a) функция Эйлера. Это среднее плавно растёт с ростом a.[31]

{displaystyle tau (a)={frac {12}{pi ^{2}}}ln 2ln a+C+O(a^{-1/6-varepsilon })}

Константа (константа Портера[32]) в этой формуле {displaystyle Capprox 1.467}, а ε является бесконечно малым.

Третье среднее значение Y(n) определяется как среднее число шагов, требуемых, когда a и b выбираются случайным образом (с равномерным распределением) от 1 до n.

{displaystyle Y(n)={frac {1}{n^{2}}}sum _{a=1}^{n}sum _{b=1}^{n}T(a,b)={frac {1}{n}}sum _{a=1}^{n}T(a).}

Вычислительная сложность шага[править | править код]

На каждом шаге алгоритма Евклида вычисляется коэффициент qk и остаток rk для заданной пары целых чисел rk−2 и rk−1. Эти величины связаны следующим соотношением:

rk−2 = qk rk−1 + rk

Вычислительная сложность каждого шага связана главным образом с нахождением qk, так как остаток rk можно быстро вычислить, используя rk−2, rk−1, и qk

rk = rk−2qk rk−1

Вычислительная сложность операции деления чисел размером h бит оценивается как O(h(+1)), где размер частного.[24]

Для сравнения, исходный алгоритм Евклида, с использованием вычитания, может быть намного медленнее. В большинстве случаев коэффициент qk является малым числом. Вероятность данного частного q примерно равна ln|u/(u − 1)|, где u = (q + 1)2.[33] Для иллюстрации вероятность частного 1, 2, 3 или 4 составляет примерно 41,5 %, 17,0 %, 9,3 % и 5,9 % соответственно. Так как операция вычитания быстрее, чем деление, особенно для чисел больше одного машинного слова,[34] алгоритм Евклида с использованием вычитания может быть более конкурентоспособным в сравнении с алгоритмом, использующим деление.[35] Это используется в бинарном алгоритме вычисления НОД.[36]

Оценка сложности алгоритма вычисляется как произведение количества шагов на время выполнения одного шага. Она показывает, что алгоритм Евклида растёт квадратично O(h2), где h — среднее число цифр в двух начальных числах a и b в десятичной записи. Пусть h0, h1, …, hN−1 представляют число цифр в последовательных остатках r0r1, …, rN−1. Так как число шагов N растёт линейно с h, время работы ограничено следующим выражением:

{displaystyle O{Big (}sum _{i<N}h_{i}(h_{i}-h_{i+1}+2){Big )}subseteq O{Big (}hsum _{i<N}(h_{i}-h_{i+1}+2){Big )}subseteq O(h(h_{0}+2N))subseteq O(h^{2}).}

Примечания[править | править код]

  1. 1 2 Мордухай-Болтовской, 1949, с. 11—13.
  2. 1 2 3 Мордухай-Болтовской, 1949, с. 103—105.
  3. 1 2 Кнут, 2001, с. 378.
  4. Menezes, 1996, с. 286.
  5. 1 2 Курант, 2001, с. 74—76.
  6. 1 2 Виноградов, 1952, с. 14—18.
  7. Энгелер, 1987, с. 24—31.
  8. Тихомиров, 2003, с. 11—14.
  9. Калужин, 1969, с. 6—14.
  10. Цейтен, 1932, с. 112—114.
  11. Виноградов, 1952, с. 9—10.
  12. Курант, 2001, с. 67—70.
  13. Хассе, 1953, с. 29—30.
  14. Курош, 1973, с. 91—92.
  15. Панкратьев, 2007, с. 54—58.
  16. 1 2 Gathen, 2013, с. 313—326.
  17. 1 2 3 Knuth, 1997, с. 344.
  18. Shallit, 1994, с. 414.
  19. 1 2 Shallit, 1994, с. 401—419.
  20. Shallit, 1994, с. 413.
  21. Lame, 1844, с. 867—870.
  22. Grossman, 1924, с. 443.
  23. Абрамов С. А. Математические построения и программирование. — М., Наука, 1978. — Тираж 100 000 экз. — c. 170
  24. 1 2 Knuth, 1997, с. 257—261.
  25. Moeller, 2005, с. 1.
  26. Ore, 1948, с. 45.
  27. 1 2 Knuth, 1997, с. 343.
  28. LeVeque, 1996, с. 3.
  29. Абрамов С. А. Математические построения и программирование. — М., Наука, 1978. — Тираж 100 000 экз. — c. 170
  30. Knuth, 1997, с. 353.
  31. Tonkov, 1974, с. 47—57.
  32. Weisstein, Eric W. Porter’s Constant (англ.) на сайте Wolfram MathWorld.
  33. Knuth, 1997, с. 352.
  34. Wagon, 1999, с. 335—336.
  35. Cohen, 1993, с. 14.
  36. Cohen, 1993, с. 14—15, 17-18.

Литература[править | править код]

  • Абрамов С. А. Самый знаменитый алгоритм // Квант / под ред. И. К. Кикоин, Ю. А. Осипьян, В. В. Козлов, А. Л. Семёнов, А. А. Гайфуллин — МИАН, 1985. — вып. 11. — С. 44—46. — ISSN 0130-2221
  • Виноградов И. М. Основы теории чисел. — М.Л.: ГИТТЛ, 1952. — 180 с. — ISBN 978-5-811-40535-0.
  • Калужин Л. А. Основная теорема арифметики. — Популярные лекции по математике. — М.: Наука, 1969. — 33 с.
  • Кнут Д. Э. Искусство программирования. — Вильямс, 2001. — Т. 2. — 829 с. — ISBN 5-8459-0081-6.
  • Курант Р., Роббинс Г. Дополнение к главе I, § 4. // Что такое математика? — 3-e изд., испр. и доп. — М., 2001. — 568 с. — ISBN 5-900916-45-6.
  • Курош А. Г. Лекции по общей алгебре / под ред. О. Н. Головин — 2-е изд. — М.: Наука, 1973. — 400 с. — ISBN 978-5-8114-0617-3
  • Начала Евклида / пер.с греч. и комм. Д. Д. Мордухая-Болтовского под ред. Выгодского М. Я. и Веселовского И. Н.. — ГИТТЛ, 1949. — Т. 2. — 511 с.
  • Панкратьев Е. В. Элементы компьютерной алгебры. — ИНТУИТ, 2007. — 217 с. — ISBN 978-5-955-60099-4.
  • Тихомиров В. М. Великие математики прошлого и их великие теоремы. — 2-е изд., испр. — МЦНМО, 2003. — 16 с. — ISBN 5-94057-110-7.
  • Хассе Г. Лекции по теории чисел. — Изд. иностранной литературы, 1953. — 527 с.
  • Цейтен Г. Г. История математики в Древности и в Средние века. — ГТТИ, 1932. — 232 с.
  • Энгелер Э. Метаматематика элементарной математики. — М.: Мир, 1987. — 128 с.
  • Cohen H. A Course in Computational Algebraic Number Theory. — Springer-Verlag, 1993. — ISBN 0-387-55640-0.
  • von zur Gathen J., Gerhard J. Modern Computer Algebra. — Cambridge University Press, 2013. — 808 с. — ISBN 978-1-107-03903-2.
  • Grossman H. On the Number of Divisions in Finding a G.C.D. (англ.) // The American Mathematical Monthly. — 1924. — Vol. 31, iss. 9. — P. 443. — doi:10.2307/2298146. — JSTOR 2298146.
  • Knuth D. E. The Art of Computer Programming. — 3. — Addison–Wesley, 1997. — Т. 2: Seminumerical Algorithms. — ISBN 0-201-89684-2.
  • Lamé G. Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers (фр.). — Comptes Rendus Acad. Sci., 1844. — No 19.
  • LeVeque W. J. Fundamentals of Number Theory (англ.). — Dover, 1996. — ISBN 0-486-68906-9.
  • Menezes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography. — CRC-Press, 1996. — 816 с. — (Discrete Mathematics and Its Applications). — ISBN 0-8493-8523-7.
  • Moeller Niels. Mathematics of Computation (англ.). — 2005.
  • Ore O. Number Theory and Its History (англ.). — McGraw–Hill, 1948.
  • Shallit J. Origins of the analysis of the Euclidean algorithm (англ.) // Historia Math.. — 1994. — Vol. 21. — doi:10.1006/hmat.1994.1031.
  • Tonkov T. On the average length of finite continued fractions (англ.) // Acta Arithmetica. — 1974. — Vol. 26.
  • Wagon S. Mathematica in Action (англ.). — Springer-Verlag, 1999. — ISBN 0-387-98252-3.

Ссылки[править | править код]

  • Реализация алгоритма Евклида на языке Pascal
  • Алгоритм Евклида на e-maxx.ru
  • Реализация расширенного алгоритма Евклида на языке C

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *