Divisió euclidiana

De Viquipèdia
Dreceres ràpides: navegació, cerca

La divisió euclidiana o divisió entera és una operació matemàtica que, a dos nombres naturals anomenats dividend i divisor, els associa una altres dos naturals anomenats quocient i residu. Aquesta operació, definida inicialment per nombres naturals no nuls, es generalitza després per als enters i per als polinomis

Aquesta divisió és a la base de l'aritmètica modular i dóna lloc a la creació de les congruències sobre els enters.

Definicions[modifica | modifica el codi]

Divisió euclidiana en els naturals[modifica | modifica el codi]

\forall (a,b)\in\N\times\N^*, \exists ! (q, r)\in\N\times\N; a=b\cdot q+r \qquad 0 \leqslant r < b

A dos nombres naturals a i b, amb b no nul, la divisió euclidiana els associa un únic quocient q i un únic residu r, tots dos naturals, que verifiquen:

  • a = bq+r
  • 0 ≤ r < b

L'afirmació de l'existència i de la unicitat del residu i del quocient s'anomena el Teorema de la divisió euclidiana per als nombres naturals.


Divisió euclidiana en els enters[modifica | modifica el codi]

\forall (a,b)\in\Z\times\Z^*, \exists q, r\in\Z; a=b\cdot q+r \qquad |r| < |b|

A dos enters a i b, amb b no nul, la divisió euclidiana els associa un quocient q i un residu r, tos dos enters, que verifiquen:

  • a = bq+r
  • |r| < |b|

L'afirmació de l'existència del residu i del quocient s'anomena Teorema de la divisió euclidiana per als enters.

Si bé és possible de definir una divisió euclidiana tal que es garanteixi la unicitat del quocient i del residu, això seria incompatible amb el cas general de la divisió en els anells euclidians.


Divisió euclidiana en el conjunt dels polinomis[modifica | modifica el codi]

Article principal: Divisió de polinomis

La divisió euclidiana segons les potències decreixents existeix si l'anell dels polinomis està definit sobre un cos:

\forall (A,B)\in\mathbb{K}[X]\times\mathbb{K}[X]^*,\;\; \exists !Q, R\in\mathbb{K}[X],\; A=B \cdot Q+R \quad \mathrm{amb} \quad \operatorname{grau}(R) < \operatorname{grau}(B)

A dos polinomis A i B amb coeficients en un cos K amb B no nul, la divisió euclidiana els hi associa un únic quocient Q i un únic residu R, que verifiquen:

  • A=B \cdot Q+R\,
  • \operatorname{grau}(R) < \operatorname{grau}(B)

Aquí la unicitat està garantida però cal que K sigui un cos. Sinó de vegades la divisió encara és possible, per exemple si el coeficient del monomi de major grau de B és igual a 1, o de forma més general si el coeficient del monomi de major grau de B és invertible.

Divisió euclidiana en un anell[modifica | modifica el codi]

Article principal: Anell euclidià

En certs tipus d'anells commutatius unitaris íntegres, es pot definir una divisió euclidiana per

a = bq + r amb r = 0 o v(r) < v(b) essent v una aplicació de A ∖ {0} en ℕ anomenada norma euclidiana.

Si existeix una norma euclidiana sobre l'anell A, n'existeix una que verifica la propietat següent: si a i b són dos elements de A tals que b divideix a, llavors v(b) ≤ v(a). Un anell que admet una norma euclidiana s'anomena anell euclidià.

Algorismes de càlcul[modifica | modifica el codi]

Tot seguit s'estudia el càlcul de divisió euclidiana de dos enters, coneixent prèviament les operacions d'addició, de sostracció, de multiplicació, i de comparació, entre nombres enters. És fàcil transformar el problema al cas de dos enters positius, i l'estudi es restringeix a aquest cas.

Els algorismes que es descriuen més avall calculen el quocient de la divisió euclidiana; és clar que el residu se'n dedueix directament a partir del quocient. Atenció, el contrari no seria cert.

El primer mètode, natural però ingenu, requereix massa càlculs per a nombres grans. Després es presenten dos mètodes corrents, de complexitat semblant: el primera convé per a càlculs en base 2, i per tant per a una programació informàtica; el segon mètode, essencialment equivalent, és una adaptació per a la base de numeració habitual, la base decimal, i convé doncs per a càlculs a mà.

Mètode ingenu[modifica | modifica el codi]

Per calcular la divisió euclidiana de a entre b, es construeix una successió estrictament decreixent (a_i) definida per una relació de recurrència de pas 1: a_0=a \,, a_{i+1}=a_i-b=a-(i+1)\times b. Existeix per tant un nombre natural més petit I tal que a_I<b: és a dir a-I\times b<b\leq a-(I-1)\times b, que sèscriu 0\leq a-I\times b<b. El quocient de la divisió que es busca és per tant I, i el residu a-I\times b.

El nombre de passos d'aquest algorisme és per tant I=\frac{a}{b}; cada etapa requereix una substracció i una comparació; la complexitat algorísmica de càlcul creix linealment amb a, és a dir exponencialment amb la mida de a - si es convé en mesurar la mida d'un enter pel nombre de xifres que requereix el seu desenvolupament binari (o decimal si es prefereix, això no modifica les coses més que en una constant), aquesta mida és del ordre del logaritme de l'enter.

Mètode corrent, binari[modifica | modifica el codi]

Una simple millora consisteix a fer una cerca dicotòmica, sobre el quocient: en lloc de recórrer com anteriorment tots els nombres naturals des de 0 esperant arribar al quocient correcte, es comença per trobar ràpidament un enter del qual serà segur que és més gran que el quocient buscat; en la llista finita de quocients possibles restants, es farà una cerca dicotòmica.

El primer càlcul es fa simplement considerant la successió geomètrica 2^n. En tant que 2^n\times b \le a, s'incrementa n en 1 a cada etapa. Sigui N el més petit enter tal que 2^N\times b >a \,. El nombre d'etapes per trobar aquest enter és ordre de \log_2\left (\frac{a}{b}\right ). Cadascuna d'aquestes etapes no necessita més que una multiplicació per dos (encara més fàcil que una addició, en una escriptura binària), i una comparació.

Per al segon càlcul, es construeixen dues successions (\alpha_n) et (\beta_n); una emmagatzemarà les fites inferiors del quocient buscat, l'altre les fites superiors estrictes. Es comença amb \alpha_0=2^{N-1} i \beta_0=2^N, després per recurrència:

si \frac{\alpha_n+\beta_n}{2}\times b\le a, llavors es pot afinar la fita inferior, i es fa \alpha_{n+1}=\frac{\alpha_n+\beta_n}{2} i \beta_{n+1}=\beta_n\,
per altra banda, si \frac{\alpha_n+\beta_n}{2}\times b > a, es pot afinar la fita superior, i es fa \beta_{n+1}=\frac{\alpha_n+\beta_n}{2}, i \alpha_{n+1}=\alpha_n\,.

Es demostra fàcilment per recurrència que en cada etapa n d'aquest segon càlcul, \alpha_n i \beta_n són dos enters, tots dos múltiples de 2^{N-1-n} i la diferència val 2^{N-1-n}; aquesta observació permet sobretot mostrar que les successions estan ben definides fins a n=N-1, i que \alpha_{N-1} i \beta_{N-1} no difereixen més que d'1; ja que són respectivament una fita inferior i una fita superior estricta del quocient,  \alpha_{N-1} és el quocient que es busca.

El nombre màxim d'etapes per a aquest càlcul és de l'ordre de \log_2\left (\frac{a}{b}\right ) (una de les dicotomis pot haver donat el valor del quocient abans de l'etapa N - 1èssima etapa, és el cas d'igualtat en la comparació, en aquest cas es pot aturar l'algorisme abans), que cadascuna no exigeix més que una addició, una divisió entre dos (fàcil en escriptura binaria, no és evidentment una divisió euclidiana amagada), una multiplicació (que es pot evitar, gestionant més variables), i una comparació.

Concaténant els resultats dels dos càlculs, es veu que aquest algorisme té una complexitat que creix logarítmicament amb \frac{a}{b}, i per tant linealment amb la mida de a. La millora és doncs molt clara.

Mètode corrent, decimal[modifica | modifica el codi]

Siguin dos nombres naturals a i b\neq 0 dels quals es vol calcular la divisió. Es comença per trobar la potència més petita de 10 tal que b\times 10^{N_1+1}\geq a; llavors segons el teorema de la divisió euclidana, existeix un únic nombre natural 0\leq q_1<10 tal que : q_1\times 10^{N_1}\times b\leq a< (q_1+1)\times 10^{N_1}\times b. Això porta a fer la divisió de a-q_1\times 10^{N_1}\times b entre b; la desigualtat precedent mostra que la primera potència de 10 al que 10^{N_2}\times b sigui més gran que a-q_1\times 10^{N_1}\times b serà estrictament més petita que 10^{N_1+1}; se'l note 10^{N_2+1}. es construeix així una successió de nombres naturals (N_i) estrictament decreixent; per tant valdrà 0 en un cert moment; es construeix la successió d'enters 0\leq q_i< 10 associada de la mateixa manera que s'ha construït q_1. EL quocient que es busca serà \sum_i q_i10^{N_i}: en efecte la desigualtat que dóna q_r per a la primera ocurrència de N_r=0 serà: 0\leq a-b\times\sum_i q_i10^{N_i}<10^{N_r}\times b=b, que és la definició de quocient.

Fixeu-vos que aquest mètode es divideix com la precedent en dues etapes: la primera una cerca d'una potència prou gran, el que demana altre cop un nombre de càlculs logarítmic en a, és a dir lineal amb la mida de a; llavors un càlcul de tots els coeficients q_i associats a les diferents potències de 10 inferiors a la potència prou gran obtinguda. Per a cada càlcul de q_i, l'algorisme necessita un càlcul de divisió euclidiana intermèdia; però el quocient s'ha de buscar només entre els enters de 0 a 9; es fa doncs ràpidament utilitzant taules.

Vegeu també[modifica | modifica el codi]