División euclidiana

miniatura| Dividimos 17 en 3 grupos de 5, quedando 2. Aquí, o dividendo é 17, o divisor é 3, o cociente é 5 e o resto é 2 (que é estritamente menor que o divisor 3), ou máis simbólicamente, 17 = (3 &#xD7; 5) + 2.
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 0\le r substitúense por

: \deg r 

onde \deg denota o grao do polinomio.

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

: f(r) 

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  como divisor,  o resto pertence ao intervalo  de lonxitude . 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 \le r  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 \le r . 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 con R^{-1}R-1 sendo múltiplo de m), entón existen números enteiros únicos q e r con 0 \le r  tal que  a = mq+R^{-1} \cdot r . Este resultado xeneraliza a división impar de Hensel (1900).

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**)  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