división euclidiana

División con resto de números enteros

17 se divide en 3 grupos de 5, y sobran 2. Aquí, el dividendo es 17, el divisor es 3, el cociente es 5 y el resto es 2 (que es estrictamente menor que el divisor 3), o más simbólicamente, 17 = (3 × 5) + 2.

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 una manera que produce un cociente entero y un resto de un número natural estrictamente menor que el valor absoluto del divisor. Una propiedad fundamental es que el cociente y el resto existen y son únicos, bajo algunas 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 enteros , siendo el más conocido la división larga .

La división euclidiana y los algoritmos para calcularla son fundamentales para muchas cuestiones relativas a 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 sólo se consideran los restos. ^[2] La operación que consiste en calcular solo el resto se llama operación de módulo , ^[3] y se usa a menudo tanto en matemáticas como en informática.

El pastel tiene 9 porciones, por lo que cada una de las 4 personas recibe 2 porciones y sobra 1.

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 enteros a y b , con b ≠ 0 , existen enteros únicos q y r tales que

a = bq + r

y

0 ≤r < | segundo | ,

donde | segundo | 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 llama división o, en caso de ambigüedad, división euclidiana . El teorema se denomina con frecuencia algoritmo de división (aunque es un teorema y no un algoritmo), porque su demostración, como se indica a continuación, se presta a un algoritmo de división simple para calcular q y r (consulte la sección Prueba para obtener más información).

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

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

Generalización

Aunque originalmente restringido a números enteros, la división euclidiana y el teorema de la división se pueden generalizar a polinomios univariados en un campo y a dominios euclidianos.

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

${\displaystyle \deg r<\deg b,}$

donde denota el grado del polinomio . ${\displaystyle \deg }$

En la generalización a dominios euclidianos, la desigualdad se vuelve

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

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

Historia

Aunque la "división euclidiana" lleva el nombre de Euclides , parece que éste 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 necesaria ]}

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 sólo los mejores matemáticos podían realizarla. 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 de Newton-Raphson , que es independiente de cualquier sistema numérico .

El término "división euclidiana" se introdujo durante el siglo XX como abreviatura de "división de anillos euclidianos ". Los matemáticos lo han adoptado rápidamente para distinguir esta división de otros tipos de división de números. ^{[ cita necesaria ]}

Ejemplo intuitivo

Supongamos que un pastel tiene 9 porciones y se van a dividir en partes iguales entre 4 personas. Usando la división euclidiana, 9 dividido por 4 es 2 y el resto 1. En otras palabras, cada persona recibe 2 porciones de pastel y sobra 1 porción.

Esto se puede confirmar mediante la multiplicación, lo inverso de la división: si cada una de las 4 personas recibió 2 porciones, entonces se repartieron 4 × 2 = 8 porciones en total. Sumando la 1 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 el pastel en partes iguales entre las personas de manera que cada persona reciba porciones (el cociente), siendo un número de porciones el sobrante (el resto). ). En cuyo caso, la ecuación se cumple. ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle q}$ ${\displaystyle 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 sobraría ninguna porción, lo que significa que el resto sería cero, lo que lleva a la conclusión de que 3 divide exactamente a 9, o que 3 divide a 9.

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

Ejemplos

• 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 demostración del teorema de la división se basa en el hecho de que una secuencia decreciente de números enteros no negativos eventualmente se detiene. Se separa en dos partes: una por existencia y otra por unicidad de y . Otras pruebas 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 ( ver § Efectividad para más información). ^[5] ${\displaystyle q}$ ${\displaystyle r}$

Existencia

Para probar la existencia de la división euclidiana, se puede suponer que, si la igualdad se puede reescribir, entonces, si la última igualdad es una división euclidiana y 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,}$

Dado y hay números enteros y tales que por ejemplo, y si y de otro modo y ${\displaystyle b>0}$ ${\displaystyle a,}$ ${\displaystyle q_{1}}$ ${\displaystyle r_{1}\geq 0}$ ${\displaystyle a=bq_{1}+r_{1};}$ ${\displaystyle q_{1}=0}$ ${\displaystyle r_{1}=a}$ ${\displaystyle a\geq 0,}$ ${\displaystyle q_{1}=a}$ ${\displaystyle r_{1}=a-ab.}$

Sea y un par de números que no sean negativos y sean mínimos. Si tenemos división euclidiana. Por lo tanto, tenemos que demostrar que si entonces no es mínimo. En efecto, si uno tiene con y no es mínimo ${\displaystyle q}$ ${\displaystyle r}$ ${\displaystyle r}$ ${\displaystyle r<b.}$ ${\displaystyle r\geq b,}$ ${\displaystyle r}$ ${\displaystyle r\geq b,}$ ${\displaystyle a=b(q+1)+(r-b),}$ ${\displaystyle 0\leq r-b<r,}$ ${\displaystyle r}$

Esto prueba la existencia en todos los casos. Esto proporciona también un algoritmo para calcular el cociente y el resto, comenzando desde (if ) 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}$ ${\displaystyle 1}$ ${\displaystyle a-bq<b.}$ ${\displaystyle a/b}$

Unicidad

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 satisfagan la misma condición del 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' < | segundo | , entonces debemos tener eso

q' = q y r' = r .

Para probar esta afirmación, primero comenzamos con los supuestos de que

0 ≤r < | segundo |

0 ≤ r' < | segundo |

a = bq + r

a = bq' + r'

Restando las dos ecuaciones se obtiene

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

Entonces b es un divisor de r ′ – r . Como

| r ′ – r | < | segundo |

por las desigualdades anteriores, se obtiene

r ′ – r = 0 ,

y

segundo ( q – q ′ ) = 0 .

Como 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 y el resto existentes, pero la prueba anterior proporciona inmediatamente un algoritmo (consulte 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 sólo sumas, restas y comparaciones de números enteros, sin implicar 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 informática. Sin embargo, para entradas grandes, generalmente se prefieren los algoritmos que reducen la división a la multiplicación, como Newton-Raphson , 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 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 | re | . Se podrá utilizar cualquier otro intervalo de la misma duración. Más precisamente, dados números enteros , , con , existen números enteros únicos y con tales que . ${\displaystyle m}$ ${\displaystyle a}$ ${\displaystyle d}$ ${\displaystyle m>0}$ ${\displaystyle q}$ ${\displaystyle 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 }$ ${\displaystyle r}$

Esto 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

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

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

En dominios euclidianos

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

Dado un elemento a y un elemento b distinto de cero 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] Ocurre sólo en casos excepcionales, típicamente para polinomios univariados y para números enteros, si se agrega la condición adicional r ≥ 0 .

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

1. "División y algoritmos euclidianos". www-groups.mcs.st-andrews.ac.uk . Consultado el 15 de noviembre de 2019 .
2. "¿Qué es la aritmética modular?". Academia Khan . Consultado el 15 de noviembre de 2019 .
3. "Diversión con la aritmética modular: mejor explicada". mejorexplicado.com . Consultado el 15 de noviembre de 2019 .
4. Burton, David M. (2010). Teoría elemental de números . McGraw-Hill. págs. 17-19. ISBN 978-0-07-338314-9.
5. Durbin, John R. (1992). Álgebra moderna: una introducción (3ª ed.). Nueva York: Wiley. pag. 63.ISBN _ 0-471-51001-7.
6. Fanático de Haining; Ming Gu; Jiaguang Sun; Kwok-Yan Lam (2012). "Obtención de más fórmulas similares a Karatsuba en 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. 
7. Rotman 2006, pág. 267
8. Fraleigh 1993, pág. 376

Referencias

• 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