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 manera que se produzca un cociente y un resto más pequeños que el divisor. [1] Una propiedad fundamental es que el cociente y el resto existen y son únicos, bajo algunas condiciones. Debido a esta singularidad, 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 enteros., siendo la más conocida 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 enteros, [2] y la aritmética modular , para la cual solo se consideran los restos. [3] La operación que consiste en calcular solo el resto se llama operación módulo , [4] y se usa a menudo tanto en matemáticas como en ciencias de la computación.
Teorema de división
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 un y b , con b ≠ 0 , existen únicos números enteros q y r tales que
- a = bq + r
y
- 0 ≤ r <| b | ,
donde | b | denota el valor absoluto de b . [5]
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 . [1]
El cálculo del cociente y el resto del dividendo y el divisor se llama división o, en caso de ambigüedad, división euclidiana . El teorema se refiere con frecuencia como el algoritmo de la división (aunque es un teorema y no un algoritmo), debido a que su prueba como se indica a continuación presta a sí mismo un simple algoritmo de la división para el cálculo de q y r (ver la sección de prueba para más).
La división no está definida en el caso donde b = 0 ; ver división por cero .
Para el resto y la operación de módulo , existen convenciones distintas de 0 ≤ r <| b | , consulte § Otros intervalos para el resto .
Historia
Aunque la "división euclidiana" lleva el 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 resta repetida . [ cita requerida ]
Antes del descubrimiento del sistema de numeración hindú-árabe , que fue introducido en Europa durante el siglo XIII por Fibonacci , la división era extremadamente difícil y solo los mejores matemáticos podían hacerlo. [6] Actualmente, la mayoría de los algoritmos de división , incluida la división larga , se basan en esta notación o sus variantes, como los números binarios . Una excepción notable es la división Newton-Raphson , que es independiente de cualquier sistema numérico .
El término "división euclidiana" se introdujo durante el siglo XX como una abreviatura de "división de los anillos euclidianos ". Ha sido rápidamente adoptado por los matemáticos para distinguir esta división de los otros tipos de división de números. [ cita requerida ]
Ejemplo intuitivo
Suponga que un pastel tiene 9 porciones y que se van a dividir equitativamente entre 4 personas. Usando la división euclidiana, 9 dividido por 4 es 2 con el resto 1. En otras palabras, cada persona recibe 2 rebanadas de pastel y queda 1 rebanada.
Esto se puede confirmar mediante la multiplicación, la inversa de la división: si cada una de las 4 personas recibió 2 rebanadas, entonces se repartieron 4 × 2 = 8 rebanadas en total. Añadiendo la 1 rebanada restante, el resultado es 9 rebanadas. En resumen: 9 = 4 × 2 + 1.
En general, si se indica el número de cortes y el número de personas se denota , entonces uno puede dividir el pastel en partes iguales entre las personas de modo que cada persona reciba rebanadas (el cociente), con cierto número de rebanadas siendo el sobrante (el resto). En cuyo caso, la ecuación sostiene.
Como ejemplo alternativo, si se dividieran 9 porciones entre 3 personas en lugar de 4, cada una recibiría 3 y no quedaría ninguna porción, lo que significa que el resto sería cero, lo que llevaría a la conclusión de que 3 divide uniformemente a 9, o que 3 divide 9.
La división euclidiana también se puede extender al dividendo negativo (o divisor negativo) usando la misma fórmula; [1] por ejemplo −9 = 4 × (−3) + 3, lo que significa que −9 dividido por 4 es −3 con resto 3.
Ejemplos de
- 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.
Prueba
La siguiente prueba del teorema de la división se basa en el hecho de que una secuencia decreciente de enteros no negativos se detiene eventualmente. Se divide en dos partes: una para la existencia y otra para la unicidad de y . Otras pruebas usan el principio de ordenamiento correcto (es decir, la afirmación de que cada conjunto no vacío de 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 ( ver § Efectividad para más información). [7]
Existencia
Considere primero el caso b <0 . Estableciendo b ' = - b y q' = - q , la ecuación a = bq + r puede reescribirse como a = b'q ' + r y la desigualdad 0 ≤ r < | b | puede reescribirse como 0 ≤ r < | b ′ | . Esto reduce la existencia del caso b <0 a la del caso b > 0 .
De manera similar, si a <0 y b > 0 , estableciendo a ' = - a , q' = - q - 1 y r ' = b - r , la ecuación a = bq + r puede reescribirse como a' = bq ' + r ′ , y la desigualdad 0 ≤ r <| b | puede reescribirse como 0 ≤ r ' <| b | . Así, la prueba de la existencia se reduce al caso un ≥ 0 y b > 0 - que será considerado en el resto de la prueba.
Deje q 1 = 0 y r 1 = a , entonces estos son números no negativos tales que a = bq 1 + r 1 . Si r 1 < b, entonces la división está completa, así que suponga que r 1 ≥ b . Luego, definiendo q 2 = q 1 + 1 y r 2 = r 1 - b , uno tiene a = bq 2 + r 2 con 0 ≤ r 2 < r 1 . Como solo hay r 1 enteros no negativos menores que r 1 , solo es necesario repetir este proceso como máximo r 1 veces para alcanzar el cociente final y el resto. Es decir, existe un número natural k ≤ r 1 tal que a = bq k + r k y 0 ≤ r k <| b | .
Esto prueba la existencia y también proporciona un algoritmo de división simple para calcular el cociente y el resto. Sin embargo, este algoritmo no es eficiente, ya que su número de pasos es del orden de a / b .
Unicidad
El par de enteros r y q tal que un = bq + r es único, en el sentido de que no puede haber otro par de enteros que satisface el mismo estado en el teorema de la división euclidiana. En otras palabras, si tenemos otra división de a por b , digamos a = bq ' + r' con 0 ≤ r ' <| b | , entonces debemos tener eso
- 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'
Restar las dos ecuaciones da como resultado
- segundo ( q - q ′ ) = r ′ - r .
Entonces b es un divisor de r ′ - r . Como
- | r ′ - r | <| b |
por las desigualdades anteriores, uno obtiene
- r ′ - r = 0 ,
y
- b ( q - q ′ ) = 0 .
Dado que b ≠ 0 , obtenemos que r = r ′ y q = q ′ , lo que demuestra la parte de unicidad del teorema de la división euclidiana.
Eficacia
En general, una prueba de existencia no proporciona un algoritmo para calcular el cociente existente y el resto, pero la prueba anterior proporciona inmediatamente un algoritmo (ver Algoritmo de división # División por resta repetida ), aunque no es muy eficiente ya que requiere tantos pasos como el tamaño del cociente. Esto está relacionado con el hecho de que utiliza solo sumas, restas y comparaciones de números enteros, sin involucrar multiplicaciones, 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 una mayor flexibilidad y posibilidad de implementación informática. [1] Sin embargo, para entradas grandes, los algoritmos que reducen la división a la multiplicación, como Newton-Raphson , generalmente se prefieren, porque solo necesitan un tiempo que es proporcional al tiempo de la multiplicación necesario para verificar el resultado, independientemente de la algoritmo de multiplicación que se utiliza (para obtener más información, consulte Algoritmo de división # Métodos de división rápida ).
Variantes
La división euclidiana admite una serie de variantes, algunas de las cuales se enumeran a continuación.
Otros intervalos para el resto
En la división euclidiana con d como divisor, se supone que el resto pertenece al intervalo [0, d ) de longitud | d | . Puede usarse cualquier otro intervalo de la misma longitud. Más precisamente, enteros dados, , con , existen enteros únicos y con tal que .
En particular, si luego . Esta división se llama división centrada y su restose llama residuo centrado o residuo absoluto mínimo .
Se utiliza para aproximar números reales : la división euclidiana define el truncamiento y la división centrada define el redondeo .
División de Montgomery
Enteros dados , y con y dejar ser el inverso multiplicativo modular de (es decir, con siendo un múltiplo de ), entonces existen enteros únicos y con tal que . Este resultado generaliza la extraña división de Hensel (1900). [8]
El valor es el residuo N definido en la reducción de Montgomery .
En dominios euclidianos
Los dominios euclidianos (también conocidos como anillos euclidianos ) [9] se definen como dominios integrales que apoyan la siguiente generalización de la división euclidiana:
- Dado un elemento de una y un elemento no nulo b en un dominio euclidiano R equipado con una función euclidiana d (también conocido como una valoración euclidiana [10] o la función de grado [9] ), existen q y r en R tal que una = bq + r y r = 0 o d ( r ) < d ( b ) .
Singularidad de q y r no es necesario. [2] Ocurre solo en casos excepcionales, típicamente para polinomios univariados y para números enteros, si se agrega la condición adicional r ≥ 0 .
Los ejemplos de dominios euclidianos incluyen campos , anillos polinomiales en una variable sobre un campo y los enteros gaussianos . La división euclidiana de polinomios ha sido objeto de desarrollos específicos.
Ver también
- Lema de Euclides
- Algoritmo euclidiano
Notas
- ^ a b c d "La guía definitiva de matemáticas superiores a la división larga y sus variantes - para enteros" . Bóveda de matemáticas . 2019-02-24 . Consultado el 15 de noviembre de 2019 .
- ^ a b "División y algoritmos euclidianos" . www-groups.mcs.st-andrews.ac.uk . Consultado el 15 de noviembre de 2019 .
- ^ "¿Qué es la aritmética modular?" . Khan Academy . Consultado el 15 de noviembre de 2019 .
- ^ "Diversión con aritmética modular - mejor explicado" . betterexplained.com . Consultado el 15 de noviembre de 2019 .
- ^ Burton, David M. (2010). Teoría elemental de números . McGraw-Hill. págs. 17-19. ISBN 978-0-07-338314-9.
- ^ "Fibonacci - Matemáticas medievales - La historia de las matemáticas" . www.storyofmathematics.com . Consultado el 15 de noviembre de 2019 .
- ^ Durbin, John R. (1992). Álgebra moderna: una introducción (3ª ed.). Nueva York: Wiley. pag. 63. ISBN 0-471-51001-7.
- ^ Haining Fan; Ming Gu; Jiaguang Sun; Kwok-Yan Lam (2012). "Obtención de fórmulas más similares a Karatsuba sobre el campo binario". Seguridad de la información IET . 6 (1): 14-19. CiteSeerX 10.1.1.215.1576 . doi : 10.1049 / iet-ifs.2010.0114 .
- ↑ a b Rotman , 2006 , p. 267
- ^ Fraleigh 1993 , p. 376
Referencias
- Fraleigh, John B. (1993), Un primer curso de álgebra abstracta (5a ed.), Addison-Wesley, ISBN 978-0-201-53467-2
- Rotman, Joseph J. (2006), Un primer curso de álgebra abstracta con aplicaciones (3a ed.), Prentice-Hall, ISBN 978-0-13-186267-8