Relación de bezout

La relación de Bezout es una representación del máximo común divisor de números enteros como su combinación lineal con coeficientes enteros [1] .

Nombrado en honor al matemático francés Étienne Bézout .

Historia

Por primera vez este hecho fue publicado en 1624 por el matemático francés Claude Gaspard Bacher de Meziriac para el caso de los números coprimos [2] . La formulación de Basche es la siguiente: " Dados dos números primos [mutuamente], encuentre el múltiplo más pequeño de cada uno que sea un múltiplo del otro " [3] . Para resolver el problema, Basche utilizó el algoritmo de Euclides .

Étienne Bezout, en su Cours de Mathematiques a l'usage des Gardes du Pavillon et de la Marine de cuatro volúmenes , volumen 3, 1766, generalizó el teorema al extenderlo a pares arbitrarios de números, así como a polinomios .

Redacción

Sean , números enteros , al menos uno de los cuales no es cero. Entonces hay números enteros tales que la relación $a$ $b$ $x, y$

MCD

(a, b) = x \cdot a + y \cdot b

Este enunciado se denomina relación de Bezout (para números y ), así como lema de Bezout o identidad de Bezout [4] . En este caso, los números enteros se denominan coeficientes de Bezout . $a$ $b$ $x, y$

También hay una modificación de la relación de Bezout, limitada a los números naturales [5] :

Sean , números naturales. Entonces existen números naturales tales que la relación $a$ $b$ $x, y$

MCD

(a,b)=x\cdot ay\cdot b

Ejemplos

GCD La relación de Bezout tiene la forma: $(12, 30) = 6.$ $6=3 \cdot 12 + (-1) \cdot 30$
- Hay otras opciones para la descomposición de GCD, por ejemplo: $6=(-2) \cdot 12 + 1 \cdot 30.$

Consecuencias

Si los números son coprimos , entonces la ecuación $a, b$

hacha+por=1

tiene soluciones enteras [6] . Este importante hecho facilita la solución de ecuaciones diofánticas de primer orden .

MCD es el número natural más pequeño que se puede representar como una combinación lineal de números y con coeficientes enteros [7] . $(a, b)$ $a$ $b$

El conjunto de combinaciones lineales enteras coincide con el conjunto de múltiplos para GCD ) [8] . $\{hacha+por\}$ $(a, b)$

Coeficientes de Bezout

Dado que el caso en que al menos uno de los números es igual a cero es trivial, el resto de esta sección asume que ambos números no son iguales a cero. $a, b$

Ambigüedad

Encontrar los coeficientes de Bézout es equivalente a resolver una ecuación diofántica de primer orden con dos incógnitas:

hacha+por=d,

donde gcd

re=

(a,b).

O lo que es lo mismo:

{\frac {a}{d}}x+{\frac {b}{d}}y=1.

De ello se deduce que los coeficientes de Bezout se definen de manera ambigua: si se conocen algunos de sus valores, entonces el conjunto completo de coeficientes viene dado por la fórmula [9] $x, y$ ${\ estilo de visualización x_ {0}, y_ {0}}$

\left\{\left(x_{0}+{\frac {kb}{d)),y_{0}-{\frac {ka}{d))\right)\mid k=0, \pm 1,\pm 2,\pm 3\puntos \right\}.

A continuación se mostrará que existen coeficientes de Bezout que satisfacen las desigualdades y . $|x|<\izquierda|{\frac {b}{d}}\derecha|$ $|y|<\izquierda|{\frac {a}{d}}\derecha|$

Cálculo de coeficientes mediante el algoritmo de Euclides

Para encontrar los coeficientes de Bezout, puede usar el algoritmo euclidiano extendido para encontrar GCD y representar los residuos como combinaciones lineales de a y b [10] . Los pasos del algoritmo se escriben de la siguiente forma:

r_{1}=a-bq_{0},

r_{2}=b-r_{1}q_{1}=b-(a-bq_{0})q_{1}=b(1+q_{0}q_{1})-aq_{ una},

r_{3}=r_{1}-r_{2}q_{2}=(a-bq_{0})-(b(1+q_{0}q_{1})-aq_{1} )q_{2}=a(1+q_{1}q_{2})-b(q_{0}+q_{2}+q_{0}q_{1}q_{2}),

…

r_{n}=r_{n-2}-r_{n-1}q_{n-1}=\dots =ax+by.

Ejemplo

Encontremos la relación de Bezout para las fórmulas del algoritmo de Euclides que tienen la forma ${\ estilo de visualización a = 991, b = 981.}$

991={\boldsymbol {981}}\cdot 1+10,

{\boldsymbol {981}}=10\cdot 98+1,

10=1\cdot 10.

Así, GDC . De estas fórmulas obtenemos: ${\ estilo de visualización (991981) = 1}$

10={\boldsymbol {991}}-1\cdot {\boldsymbol {981}},

1={\boldsymbol {981}}-10\cdot 98={\boldsymbol {981}}-98\cdot ({\boldsymbol {991}}-{\boldsymbol {981}})=99\cdot {\boldsymbol {981}}-98\cdot {\boldsymbol {991}}.

Como resultado, la relación de Bezout tiene la forma

1=99\cdot {\boldsymbol {981}}-98\cdot {\boldsymbol {991}}.

Cálculo de coeficientes mediante fracciones continuas

Una forma alternativa (esencialmente equivalente) de resolver la ecuación usa fracciones continuas . Dividamos ambas partes de la ecuación en MCD: . Luego, expanda en una fracción continua y calcule los convergentes . El o los últimos de ellos serán iguales y relacionados con el anterior por la relación habitual: $hacha+por=d$ $a_{1}x+b_{1}y=1$ ${\frac {|a_{1}|}{|b_{1}|}}$ ${\frac{p_{k}}{q_{k}}}$ $norte$ ${\frac {|a_{1}|}{|b_{1}|}}$

p_{n}q_{n-1}-q_{n}p_{n-1}=(-1)^{n-1}.

Sustituyendo en esta fórmula y multiplicando ambos lados por , obtenemos ${\displaystyle p_{n}=a_{1};q_{n}=b_{1))$ $d$

aq_{n-1}-bp_{n-1}=\pm d.

Hasta una señal, esta es la proporción de Bezout. por tanto, el penúltimo convergente da los módulos de la solución: está el denominador de esta fracción, y es el numerador. Resta, en base a la ecuación original, encontrar los signos ; para esto es suficiente encontrar los últimos dígitos en los productos [11] . ${\frac {p_{n-1}}{q_{n-1}}}$ $|x|$ $|y|$ $x, y$ $|hacha|,|por|$

Pares mínimos de coeficientes

El algoritmo dado en la sección anterior en términos de fracciones continuas, así como el algoritmo de Euclides equivalente, da como resultado un par que satisface las desigualdades $(x,y)$

|x|<\left|{\frac {b}{d}}\right|;\quad |y|<\left|{\frac {a}{d}}\right|.

Este hecho se deriva del hecho de que las fracciones y , como se indicó anteriormente, forman convergentes sucesivos , y el numerador y denominador del siguiente convergente es siempre mayor que el del anterior [11] [12] . Por brevedad, podemos llamar a tal par mínimo , siempre hay dos de esos pares. ${\frac {|y|}{|x|}}$ ${\frac {|a_{1}|}{|b_{1}|}}$

Ejemplo. deja _ mcd(12, 42) = 6. A continuación se muestran algunos elementos de la lista de pares de coeficientes de Bezout, con los pares mínimos resaltados en rojo: ${\ estilo de visualización a = 12, b = 42}$

{\begin{alignedat}{3}&\dots \\&12\times &\color {blue}{-10}&{}+42\times &\color {blue}{3}&{}= 6\\&12\veces y\color {rojo}{-3}&{}+42\veces y\color {rojo}{1}&{}=6\\&12\veces y\color {rojo}{4 }&{}+42\veces &\color {rojo}{-1}&{}=6\\&12\veces &\color {azul}{11}&{}+42\veces &\color {azul} {-3}&{}=6\\&12\veces y\color {azul}{18}&{}+42\veces y\color {azul}{-5}&{}=6\\&\puntos \end{datos alineados}}

Aplicación

La relación de Bezout se usa a menudo como un lema en el curso de la demostración de otros teoremas (por ejemplo, el teorema fundamental de la aritmética [13] ), así como para resolver ecuaciones diofánticas y comparaciones de módulo.

Solución de ecuaciones diofánticas de primer grado

Consideremos la solución en números enteros de ecuaciones diofánticas de la forma

hacha+por=c.

Denotar gcd Obviamente, la ecuación tiene soluciones enteras solo cuando es divisible por . Consideraremos que se cumple esta condición, y uno de los algoritmos anteriores encontrará los coeficientes de Bezout : ${\ estilo de visualización d = {}}$ $(a,b).$ $C$ $d$ $x, y$

a+by=d.

Entonces la solución de la ecuación original será el par [11] , donde . $c_{1}x,c_{1}y$ $c_{1}=c/d$

Resolución de comparaciones de primer grado

Para resolver comparaciones de primer grado

ax\equiv b{\pmod m}

basta con transformarlo a la forma [8]

hacha+mi=b.

Un caso especial prácticamente importante es encontrar el elemento recíproco en el anillo de residuos , es decir, resolver la comparación

hacha\equiv 1{\pmod {m)).

Variaciones y generalizaciones

La relación de Bezout se generaliza fácilmente al caso cuando hay más de dos números [1] :

Sean , …, números enteros no todos iguales a cero. Entonces existen tales enteros , …, , que se cumple la relación: $un_{1}$ $un$ $x_{1}$ $x_{n}$

MCD , …, =

(a_1

un)

x_1\cdot a_1 + \cdots x_n\cdot a_n

La relación de Bezout puede ser válida no solo para números enteros, sino también en otros anillos conmutativos (por ejemplo, para números enteros gaussianos ). Tales anillos se llaman anillos de Bezout .

Ejemplo: formulación para un anillo polinomial (de una variable):

Sea una familia de polinomios, y no todos ellos son iguales a cero. Denotemos su máximo común divisor. Entonces existe una familia de polinomios tal que se cumple la siguiente relación: $\left(P_i\right)_{i\in I}$ $\Delta$ $\left(A_i\right)_{i\in I}$

\Delta = \sum_{i\in I} A_iP_i

Los coeficientes de Bezout para dos polinomios en una variable se pueden calcular de manera similar a la anterior para números enteros (usando el algoritmo de Euclid extendido ) [14] . Las raíces comunes de dos polinomios son también las raíces de su máximo común divisor, por lo que de la relación de Bezout y el teorema fundamental del álgebra se sigue el siguiente resultado :

Sean polinomios y dados con coeficientes en algún campo. Entonces los polinomios y tales que existen si y sólo si y no tienen raíces comunes en ningún campo algebraicamente cerrado (normalmente se toma como este último el campo de los números complejos ). $f(x)$ $g(x)$ $hacha)$ $b(x)$ ${\ estilo de visualización af+bg=1}$ $f(x)$ $g(x)$

Una generalización de este resultado a cualquier número de polinomios e incógnitas es el Teorema cero de Hilbert .

Véase también

Notas

↑ 1 2 Hasse G., 1953 , p. 29
↑ Matemáticas del siglo XVII // Historia de las matemáticas / Editado por A.P. Yushkevich , en tres volúmenes. - M. : Nauka, 1970. - T. II. - S. 75.
↑ Claude Gaspard Bachet, señor de Méziriac. Problemes plaisants et delectables // Problemes plaisans, qui se font par nombres (francés) . — 2ª ed. - Lyon, Francia: Pierre Rigaud & Associates, 1624. - S. 18-33. Archivado el 13 de marzo de 2012 en Wayback Machine .
↑ Jones, GA;Jones, JM §1.2. Identidad de Bezout // Teoría elemental de números. - Berlín: Springer-Verlag, 1998. - P. 7-11.
↑ Davenport G. Aritmética superior. Introducción a la teoría de números. - M. : Nauka, 1965. - S. 28. - 176 p.
↑ Hasse G., 1953 , pág. 33.
↑ Faddeev D.K. Conferencias sobre álgebra. Libro de texto para universidades. - Nauka, 1984. - S. 9. - 416 p.
↑ 1 2 La identidad de Bezout . Fecha de acceso: 25 de diciembre de 2014. Archivado desde el original el 25 de diciembre de 2014. (indefinido)
↑ Gelfond A. O. Solución de ecuaciones en números enteros. - Nauka, 1983. - S. 9-10. — 63 pág. - (Clases populares de matemáticas, número 8).
↑ Egorov D. F. Elementos de teoría de números. - Moscú-Petrogrado: Gosizdat, 1923. - S. 14. - 202 p.
↑ 1 2 3 Sushkevich A. K. Teoría de los números. Curso elemental. - Jarkov: Editorial de la Universidad de Jarkov, 1954. - S. 49-51.
↑ Khinchin A. Ya. Fracciones continuas. - Ed. 3er. - M. : GIFML, 1961. - S. 11-12.
↑ Véase, por ejemplo: Zhikov V.V. El teorema fundamental de la aritmética // Soros Educational Journal . - 2000. - T. 6 , N º 3 . - S. 112-117 . Archivado desde el original el 23 de noviembre de 2018.
↑ Koblitz N. Curso de Teoría de Números y Criptografía. - M. : Editorial científica TVP, 2001. - S. 19. - 259 p. — ISBN 5-94057-103-4 .

Literatura

Vinogradov I.M. Fundamentos de la teoría de números. - M. - L. : GITTL, 1952. - 180 p.
Kaluzhnin L. A. El principal teorema de la aritmética. - M. : Nauka, 1969. - ( Conferencias populares sobre matemáticas ).
Hasse G. Conferencias sobre teoría de números. - M. : Ed. literatura extranjera, 1953. - 529 p.

Enlaces

Calculadora de proporción de Bezout en línea .
La identidad de Bezout .
Identidad de Bezout , algoritmo euclidiano .