División euclidiana

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

Modelo:Math

e

Modelo:Math,

onde Modelo:Math denota o valor absoluto de Modelo:Math.

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

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

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

onde $\mathrm{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 Modelo:Mvar como divisor, o resto pertence ao intervalo Modelo:Math de lonxitude Modelo:Math. 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<m+d$ tal que $a=mq+r$.

En particular, se $d=-\lfloor \frac{m}{2}\rfloor$ entón $-\lfloor \frac{m}{2}\rfloor \le r<m-\lfloor \frac{m}{2}\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\le r<m$ 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 Modelo:Math e un elemento distinto de cero Modelo:Math nun dominio euclidiano Modelo:Math equipado cunha función euclidiana Modelo:Math (tamén coñecida como valoración euclidiana ou función de grao ), existen Modelo:Math e Modelo:Math en Modelo:Math tal que Modelo:Math e a maiores Modelo:Math ou Modelo:Math.

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

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.

Véxase tamén

Bibliografía

• Modelo:Cita libro
• Modelo:Cita libro

Outros artigos

• Lema de Euclides
• Algoritmo de Euclides
• Algoritmo de Euclides estendido

Modelo:Control de autoridades