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  e , con , existen números enteiros únicos  e  tal que



e

 ,

onde  denota o valor absoluto de .

No teorema anterior, cada un dos catro enteiros ten un nome propio:  chámase ,  chámase ,  chámase  e  chámase .

 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  substitúense por



onde  denota o grao do polinomio.

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



onde  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  como divisor,  o resto pertence ao intervalo  de lonxitude . Poderase utilizar calquera outro intervalo da mesma lonxitude. Por exemplo, dados os enteiros , ,  con , existen números enteiros únicos  e  con  tal que .

En particular, se  entón . Esta división chámase división centrada e o seu resto  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  ,  e  con  e  sexa  o inverso multiplicativo modular de  (é dicir,  con  sendo múltiplo de ), entón existen números enteiros únicos  e  con  tal que . Este resultado xeneraliza a división impar de Hensel (1900).

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

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

 Dados un elemento  e un elemento distinto de cero  nun dominio euclidiano  equipado cunha función euclidiana  (tamén coñecida como valoración euclidiana  ou función de grao  ), existen  e  en  tal que  e a maiores  ou .

Non se require a unicidade de  e .  Ocorre só en casos excepcionais, normalmente para polinomios univariados, e para números enteiros, se se engade a condición adicional .

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 


 Véxase tamén 

 Bibliografía 



 Outros artigos 
 Lema de Euclides
 Algoritmo de Euclides
 Algoritmo de Euclides estendido

Categoría:Teoría de números
Categoría:Álxebra
Categoría:Wikipedia:Páxinas con traducións non revisadas