División euclidiana

En aritmética , la división euclidiana (o división con resto ) es el proceso de dividir un número entero (el dividendo) por otro (el divisor), de forma que se produzca un cociente entero y un resto natural estrictamente menor que el valor absoluto del divisor. Una propiedad fundamental es que el cociente y el resto existen y son únicos, bajo ciertas condiciones. Debido a esta unicidad, la división euclidiana a menudo se considera sin hacer referencia a ningún método de cálculo y sin calcular explícitamente el cociente y el resto. Los métodos de cálculo se denominan algoritmos de división de números enteros , siendo el más conocido de ellos la división larga .

La división euclidiana y los algoritmos para calcularla son fundamentales para muchas cuestiones relacionadas con los números enteros, como el algoritmo euclidiano para encontrar el máximo común divisor de dos números enteros, ^[1] y la aritmética modular , para la que solo se consideran los residuos. ^[2] La operación que consiste en calcular solo el residuo se denomina operación módulo , ^[3] y se utiliza a menudo tanto en matemáticas como en informática.

La división euclidiana se basa en el siguiente resultado, que a veces se denomina lema de división de Euclides .

Dados dos números enteros a y b , con b ≠ 0 , existen números enteros únicos q y r tales que

a = bq + r

y

0 ≤ r < | b | ,

donde | b | denota el valor absoluto de b . ^[4]

En el teorema anterior, cada uno de los cuatro números enteros tiene un nombre propio: a se llama dividendo , b se llama divisor , q se llama cociente y r se llama resto .

El cálculo del cociente y el resto del dividendo y el divisor se denomina división o, en caso de ambigüedad, división euclidiana . El teorema se conoce con frecuencia como algoritmo de división (aunque es un teorema y no un algoritmo), porque su demostración, como se muestra a continuación, se presta a un algoritmo de división simple para calcular q y r (consulte la sección Demostración para obtener más información).

La división no está definida en el caso donde b = 0 ; ver división por cero .

Para el resto y la operación módulo , existen convenciones distintas a 0 ≤ r < | b | , ver § Otros intervalos para el resto.

Aunque originalmente estaban restringidos a números enteros, la división euclidiana y el teorema de la división pueden generalizarse a polinomios univariados sobre un campo y a dominios euclidianos.

En el caso de polinomios univariados , la principal diferencia es que las desigualdades se reemplazan con${\displaystyle 0\leq r<|b|}$

${\displaystyle r=0}$o${\displaystyle \deg r<\deg b,}$

donde denota el grado del polinomio .${\estilo de visualización \grado}$

En la generalización a los dominios euclidianos, la desigualdad se convierte en

${\displaystyle r=0}$o${\displaystyle f(r)<f(b),}$

donde denotan una función específica del dominio de los números naturales llamada "función euclidiana".${\estilo de visualización f}$

La unicidad del cociente y del resto sigue siendo cierta para los polinomios, pero es falsa en general.

Esta sección necesita citas adicionales para su verificación . Por favor, ayude a mejorar este artículo añadiendo citas de fuentes fiables en esta sección. El material sin fuentes puede ser cuestionado y eliminado. Buscar fuentes:  «División euclidiana» – noticias  · periódicos  · libros  · académico  · JSTOR ( septiembre de 2016 ) ( Aprenda cómo y cuándo eliminar este mensaje )

Aunque la "división euclidiana" recibe su nombre de Euclides , parece que no conocía el teorema de existencia y unicidad, y que el único método de cálculo que conocía era la división por sustracción repetida . ^{[ cita requerida ]}

Antes del descubrimiento del sistema de numeración hindú-arábigo , introducido en Europa en el siglo XIII por Fibonacci , la división era extremadamente difícil y solo los mejores matemáticos eran capaces de realizarla. En la actualidad, la mayoría de los algoritmos de división , incluida la división larga , se basan en esta notación o en sus variantes, como los números binarios . Una notable excepción es la división de Newton-Raphson , que es independiente de cualquier sistema de numeración .

El término "división euclidiana" se introdujo durante el siglo XX como una forma abreviada de decir "división de anillos euclidianos ". Los matemáticos lo adoptaron rápidamente para distinguir esta división de los otros tipos de división de números. ^{[ cita requerida ]}

Supongamos que una tarta tiene 9 porciones y que se deben dividir equitativamente entre 4 personas. Si utilizamos la división euclidiana, 9 dividido por 4 es 2 y el resto es 1. En otras palabras, cada persona recibe 2 porciones de tarta y sobra 1.

Esto se puede comprobar mediante la multiplicación, la operación inversa de la división: si cada una de las 4 personas recibió 2 rebanadas, entonces se repartieron 4 × 2 = 8 rebanadas en total. Si se suma la rebanada restante, el resultado son 9 rebanadas. En resumen: 9 = 4 × 2 + 1.

En general, si se denota el número de porciones y el número de personas , entonces se puede dividir la tarta de manera uniforme entre las personas, de modo que cada persona reciba porciones (el cociente) y quede una cierta cantidad de porciones como resto. En ese caso, la ecuación se cumple.${\estilo de visualización a}$${\estilo de visualización b}$${\estilo de visualización q}$${\estilo de visualización r<b}$${\displaystyle a=bq+r}$

Si se dividieran 9 porciones entre 3 personas en lugar de 4, entonces cada uno recibiría 3 y no quedaría ninguna porción, lo que significa que el resto sería cero, lo que lleva a la conclusión de que 3 divide a 9, o que 3 divide a 9.

La división euclidiana también se puede extender al dividendo negativo (o divisor negativo) utilizando la misma fórmula; por ejemplo, −9 = 4 × (−3) + 3, lo que significa que −9 dividido por 4 es −3 con resto 3.

• Si a = 7 y b = 3, entonces q = 2 y r = 1, ya que 7 = 3 × 2 + 1.
• Si a = 7 y b = −3, entonces q = −2 y r = 1, ya que 7 = −3 × (−2) + 1.
• Si a = −7 y b = 3, entonces q = −3 y r = 2, ya que −7 = 3 × (−3) + 2.
• Si a = −7 y b = −3, entonces q = 3 y r = 2, ya que −7 = −3 × 3 + 2.

La siguiente demostración del teorema de la división se basa en el hecho de que una secuencia decreciente de números enteros no negativos se detiene en algún momento. Se divide en dos partes: una para la existencia y otra para la unicidad de y . Otras demostraciones utilizan el principio de buen orden (es decir, la afirmación de que todo conjunto no vacío de números enteros no negativos tiene un elemento más pequeño) para simplificar el razonamiento, pero tienen la desventaja de no proporcionar directamente un algoritmo para resolver la división (consulte § Efectividad para obtener más información). ^[5]${\estilo de visualización q}$${\estilo de visualización r}$

Para probar la existencia de la división euclidiana, se puede suponer que, si la igualdad puede reescribirse Entonces, si la última igualdad es una división euclidiana, la primera también es una división euclidiana.${\displaystyle b>0,}$${\displaystyle b<0,}$${\displaystyle a=bq+r}$${\displaystyle a=(-b)(-q)+r.}$${\displaystyle -b>0,}$

Dados y hay números enteros y tales que por ejemplo, y si y en caso contrario y${\displaystyle b>0}$${\estilo de visualización a,}$$estilo de visualización q_{1}}$${\displaystyle r_{1}\geq 0}$${\displaystyle a=bq_{1}+r_{1};}$$estilo de visualización q_{1}=0}$$estilo de visualización r_{1}=a}$${\displaystyle a\geq 0,}$$estilo de visualización q_{1}=a}$${\displaystyle r_{1}=a-ab.}$

Sea y un par de números para los cuales es no negativo y mínimo. Si tenemos división euclidiana. Por lo tanto, tenemos que demostrar que, si entonces no es mínimo. De hecho, si uno tiene con y no es mínimo${\estilo de visualización q}$${\estilo de visualización r}$${\estilo de visualización r}$${\displaystyle r<b.}$${\displaystyle r\geq b,}$${\estilo de visualización r}$${\displaystyle r\geq b,}$${\displaystyle a=b(q+1)+(rb),}$${\displaystyle 0\leq rb<r,}$${\estilo de visualización r}$

Esto prueba la existencia en todos los casos. Esto proporciona también un algoritmo para calcular el cociente y el resto, partiendo de (si ) y sumándole hasta Sin embargo, este algoritmo no es eficiente, ya que su número de pasos es del orden de${\displaystyle q=0}$${\displaystyle a\geq 0}$${\estilo de visualización 1}$${\displaystyle a-bq<b.}$${\estilo de visualización a/b}$

El par de números enteros r y q tal que a = bq + r es único, en el sentido de que no puede haber otro par de números enteros que satisfaga la misma condición en el teorema de la división de Euclides. En otras palabras, si tenemos otra división de a por b , digamos a = bq' + r' con 0 ≤ r' < | b | , entonces debemos tener que

q' = q y r' = r .

Para probar esta afirmación, primero comenzamos con las suposiciones de que

0 ≤ r < | b |

0 ≤ r' < | b |

a = bq + r

a = bq' + r'

Restando las dos ecuaciones obtenemos

b ( q – q ′ ) = r ′ – r .

Por lo tanto, b es un divisor de r ′ – r . Como

| r ′ – r | < | b |

por las desigualdades anteriores, se obtiene

r ′ – r = 0 ,

y

b ( q – q ′ ) = 0 .

Como b ≠ 0 , obtenemos que r = r ′ y q = q ′ , lo que demuestra la parte de unicidad del teorema de división euclidiana.

En general, una prueba de existencia no proporciona un algoritmo para calcular el cociente y el resto existentes, pero la prueba anterior sí proporciona inmediatamente un algoritmo (ver Algoritmo de división#División por sustracción repetida ), aunque no es muy eficiente ya que requiere tantos pasos como el tamaño del cociente. Esto se relaciona con el hecho de que utiliza solo sumas, restas y comparaciones de números enteros, sin involucrar la multiplicación ni ninguna representación particular de los números enteros como la notación decimal.

En términos de notación decimal, la división larga proporciona un algoritmo mucho más eficiente para resolver divisiones euclidianas. Su generalización a notación binaria y hexadecimal proporciona mayor flexibilidad y posibilidad de implementación en computadoras. Sin embargo, para entradas grandes, los algoritmos que reducen la división a multiplicación, como Newton-Raphson , suelen ser los preferidos, porque solo necesitan un tiempo que es proporcional al tiempo de la multiplicación necesaria para verificar el resultado, independientemente del algoritmo de multiplicación que se use (para obtener más información, consulte Algoritmo de división#Métodos de división rápida ).

La división euclidiana admite diversas variantes, algunas de las cuales se enumeran a continuación.

En la división euclidiana con d como divisor, se supone que el resto pertenece al intervalo [0, d ) de longitud | d | . Se puede utilizar cualquier otro intervalo de la misma longitud. Más precisamente, dados los números enteros , , con , existen números enteros únicos y con tales que .${\estilo de visualización m}$${\estilo de visualización a}$${\estilo de visualización d}$${\displaystyle m>0}$${\estilo de visualización q}$${\estilo de visualización r}$${\displaystyle d\leq r<m+d}$${\displaystyle a=mq+r}$

En particular, si entonces . Esta división se llama división centrada , y su resto se llama resto centrado o resto mínimo absoluto .${\displaystyle d=-\left\lfloor {\frac {m}{2}}\right\rfloor }$${\displaystyle -\left\lfloor {\frac {m}{2}}\right\rfloor \leq r<m-\left\lfloor {\frac {m}{2}}\right\rfloor }$${\estilo de visualización r}$

Esto se utiliza para aproximar números reales : la división euclidiana define el truncamiento y la división centrada define el redondeo .

Dados los números enteros , y con y sea el inverso multiplicativo modular de (es decir, con siendo un múltiplo de ), entonces existen números enteros únicos y con tales que . Este resultado generaliza la división impar de Hensel (1900). ^[6]${\estilo de visualización a}$${\estilo de visualización m}$${\estilo de visualización R,}$${\displaystyle m>0}$${\displaystyle \mcd(R,m)=1,}$$Estilo de visualización R-1$${\estilo de visualización R}$${\displaystyle 0<R^{-1}<m}$$Estilo de visualización R^{-1}R-1}$${\estilo de visualización m}$${\estilo de visualización q}$${\estilo de visualización r}$${\displaystyle 0\leq r<m}$${\displaystyle a=mq+R^{-1}\cdot r}$

El valor es el residuo N definido en la reducción de Montgomery .${\estilo de visualización r}$

Los dominios euclidianos (también conocidos como anillos euclidianos ) ^[7] se definen como dominios integrales que admiten la siguiente generalización de la división euclidiana:

Dado un elemento a y un elemento distinto de cero b en un dominio euclidiano R equipado con una función euclidiana d (también conocida como valoración euclidiana ^[8] o función de grado ^[7] ), existen q y r en R tales que a = bq + r y r = 0 o d ( r ) < d ( b ) .

No se requiere la unicidad de q y r ^{. [1]} Esto ocurre solo en casos excepcionales, típicamente para polinomios univariados y para números enteros, si se agrega la condición adicional r ≥ 0 .

Entre los ejemplos de dominios euclidianos se incluyen los campos , los anillos polinómicos en una variable sobre un campo y los números enteros gaussianos . La división euclidiana de polinomios ha sido objeto de desarrollos específicos.

• Lema de Euclides
• Algoritmo euclidiano

• Fraleigh, John B. (1993), Un primer curso de álgebra abstracta (5ª ed.), Addison-Wesley, ISBN 978-0-201-53467-2
• Rotman, Joseph J. (2006), Un primer curso de álgebra abstracta con aplicaciones (3.ª ed.), Prentice-Hall, ISBN 978-0-13-186267-8