División euclidiana

En aritmética, a división euclidiana (ou división con resto) é o proceso de dividir un número enteiro (o dividendo) por outro (o divisor), de forma que se produce un cociente enteiro e un resto natural estritamente menor que o valor absoluto do divisor. Unha propiedade fundamental é que o cociente e o resto existen e son únicos, baixo algunhas condicións. Os métodos de cálculo chámanse algoritmos de división enteira, sendo o máis coñecido a división longa.

Teorema da división

A división euclidiana baséase no resultado, ás veces chamado lema de división de Euclides, que mostramos a conyinuación.

Dados dous números enteiros $a$ e $b$ , con $b \neq 0$ , existen números enteiros únicos $q$ e $r$ tal que

a = bq + r

e

0 \leq r < | b |

,

onde $| b |$ denota o valor absoluto de $b$ . ^[1]

No teorema anterior, cada un dos catro enteiros ten un nome propio: $a$ chámase dividendo, $b$ chámase divisor, $q$ chámase cociente e $r$ chámase resto.

Xeneralización

Aínda que orixinalmente foi pensada para números enteiros, a división euclidiana e o teorema da división poden xeneralizarse a polinomios univariados sobre un corpo e a dominios euclidianos.

No caso dos polinomios, temos que a principal diferenza é que as desigualdades $0\leq r<|b|$ substitúense por

\deg r<\deg b,

onde $\deg$ denota o grao do polinomio.

Na xeneralización a dominios euclidianos, a desigualdade descríbese como

f(r)<f(b),

onde $f$ denota unha función específica do dominio aos números naturais chamada "función euclidiana".

Exemplos

Se a = 7 e b = 3, entón q = 2 e r = 1, xa que 7 = 3 × 2 + 1.
Se a = 7 e b = −3, entón q = −2 e r = 1, xa que 7 = −3 × (−2) + 1.
Se a = −7 e b = 3, entón q = −3 e r = 2, xa que −7 = 3 × (−3) + 2.
Se a = −7 e b = −3, entón q = 3 e r = 2, xa que −7 = −3 × 3 + 2.

En termos de notación decimal, a división longa proporciona un algoritmo eficiente para resolver divisións euclidianas. A súa xeneralización á notación binaria e hexadecimal proporciona máis flexibilidade e posibilidades de implementación en aplicacións informáticas. No entanto, para números grandes, adoitan preferirse os algoritmos que reducen a división á multiplicación, como o método de Newton–Raphson, porque só necesitan un tempo proporcional ao tempo da multiplicación necesario para verificar o resultado, independentemente do algoritmo de multiplicación que use.

Variantes

A división euclidiana admite unha serie de variantes, algunhas delas enuméranse a continuación.

Outros intervalos para o resto

Na división euclidiana con $d$ como divisor, o resto pertence ao intervalo $[0, d)$ de lonxitude $| d |$ . Poderase utilizar calquera outro intervalo da mesma lonxitude. Por exemplo, dados os enteiros $m$ , $a$ , $d$ con $m>0$ , existen números enteiros únicos $q$ e $r$ con $d\leq r<m+d$ tal que $a=mq+r$ .

En particular, se $d=-\left\lfloor {\frac {m}{2}}\right\rfloor$ entón $-\left\lfloor {\frac {m}{2}}\right\rfloor \leq r<m-\left\lfloor {\frac {m}{2}}\right\rfloor$ . Esta división chámase división centrada e o seu resto $r$ chámase resto centrado ou resto mínimo absoluto.

Isto úsase para aproximar números reais: a división euclidiana define o truncamento, e a división centrada define o redondeo.

División de Montgomery

Dados os números enteiros $a$ , $m$ e $R,$ con $m>0$ e $\gcd(R,m)=1,$ sexa $R^{-1}$ o inverso multiplicativo modular de $R$ (é dicir, $0<R^{-1}<m$ con $R^{-1}R-1$ sendo múltiplo de $m$ ), entón existen números enteiros únicos $q$ e $r$ con $0\leq r<m$ tal que $a=mq+R^{-1}\cdot r$ . Este resultado xeneraliza a división impar de Hensel (1900). ^[2]

O valor $r$ é o N-residuo definido na redución de Montgomery.

En dominios euclidianos

Os dominios euclidianos (tamén coñecidos como aneis euclidianos) ^[3] defínense como dominios de integridade que admiten a seguinte xeneralización da división euclidiana:

Dados un elemento

a

e un elemento distinto de cero

b

nun dominio euclidiano

R

equipado cunha función euclidiana

d

(tamén coñecida como valoración euclidiana ^[4] ou función de grao ^[3] ), existen

q

e

r

en

R

tal que

a = bq + r

e a maiores

r = 0

ou

d (r) < d (b)

.

Non se require a unicidade de $q$ e $r$ . ^[5] Ocorre só en casos excepcionais, normalmente para polinomios univariados, e para números enteiros, se se engade a condición adicional $r \geq 0$ .

Exemplos de dominios euclidianos inclúen os corpos, os aneis polinómicos nunha variable sobre un corpo e tamén os enteiros gaussiano. A división euclidiana de polinomios ten sido obxecto de desenvolvementos específicos.

Notas

↑ . 2010. pp. 17–19. ISBN 978-0-07-338314-9. Falta o |title= (Axuda)
↑ 6. 2012: 14–19. doi:10.1049/iet-ifs.2010.0114. Falta o |title= (Axuda)
↑ ^3,0 ^3,1 Rotman 2006
↑ Fraleigh 1993
↑ "Divison and Euclidean Algorithm". www-groups.mcs.st-andrews.ac.uk. Arquivado dende o orixinal o 06 de maio de 2021. Consultado o 16 de maio de 2024.

Véxase tamén

Bibliografía

Fraleigh, John B. (1993). A First Course in Abstract Algebra (5th ed.). Addison-Wesley. ISBN 978-0-201-53467-2.
Rotman, Joseph J. (2006). A First Course in Abstract Algebra with Applications (3rd ed.). Prentice-Hall. ISBN 978-0-13-186267-8.

Outros artigos

[1] . 2010. pp. 17–19. ISBN 978-0-07-338314-9. Falta o |title= (Axuda)

[2] 6. 2012: 14–19. doi:10.1049/iet-ifs.2010.0114. Falta o |title= (Axuda)

[Rot06-3] 3,0 ^3,1 Rotman 2006

[4] Fraleigh 1993

[:1-5] "Divison and Euclidean Algorithm". www-groups.mcs.st-andrews.ac.uk. Arquivado dende o orixinal o 06 de maio de 2021. Consultado o 16 de maio de 2024.

[1]

[2]

[3]

[4]

[5]