Divisió euclidiana

La divisió euclidiana o divisió entera és una operació matemàtica que, a dos nombres naturals anomenats dividend i divisor, els associa uns 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.^[1]^[2]^[3]

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

Definicions

Divisió euclidiana en els naturals

$\forall (a,b)\in \mathbb {N} \times \mathbb {N} ^{*},\exists !(q,r)\in \mathbb {N} \times \mathbb {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=b\cdot q+r$
$0\leq 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.

Demostració

Siguin a i b dos enters positius amb b no nul.

Existència

Es considera el conjunt E definit per:

E:=\left\{x\in \mathbb {N} \;|\;\exists z\in \mathbb {N} :\;x=a-bz\right\}

E no és buit perquè conté a. Com que E és un subconjunt no buit de N, per la propietat que el conjunt dels naturals està ben ordenat el mínim de E existeix. Sigui r aquest mínim i q el nombre que el defineix, és a dir el que verifica la igualtat $a-b\cdot q=r$ , Per construcció r és un nombre natural. L'enter r - b no pot ser un element de E i per tant és estrictament negatiu, això demostra que r és estrictament més petit que b. Amb això queda demostrada l'existència.

Unicitat

Se suposa que existeixen quatre naturals q₁,q₂, r₁ i r₂ que formen dues parelles de solucions. Per diferència,

(q_{1}-q_{2})\cdot b+(r_{1}-r_{2})

és nul. Aquesta igualtat demostra que b divideix

r_{1}-r_{2}

. Com que r₁ i r₂ són estrictament més petits que b i positius,

r_{1}-r_{2}

està estrictament comprès entre - b i b. L'únic múltiple de b possible per

r_{1}-r_{2}

és per tant zero. En conclusió r₁ és igual a r₂ per tant q₁ és també igual a q₂.

Divisió euclidiana en els enters

$\forall (a,b)\in \mathbb {Z} \times \mathbb {Z} ^{*},\exists q,r\in \mathbb {Z} ,r>0;a=b\cdot q+r\qquad r<|b|$ ^[4]

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=b\cdot q+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.

Demostració

La definició de la divisió euclidiana sobre els naturals permet provar l'existència de dos naturals q₁ i r₁ tals que

|a|=|b|q_{1}+r_{1}

amb

r_{1}<|b|

Un petit estudi sobre els signes respectius de a i b permet donar per a la divisió euclidiana de a entre b

per a i b negatius, quocient q₁ i residu -r₁

per a negatiu i b positiu, quocient -q₁ i residu -r₁

per a positiu i b negatiu, quocient -q₁ i residu r₁

per a i b positius, quocient q₁ i residu r₁

Però la unicitat no és sempre guanyada si no s'imposa r positiu o nul. En efecte si a = bq + r amb r estrictament positiu llavors

a=b(q+1)+r-b

amb el qual

|r-b|<|b|

dona un altre parella solució.

Divisió euclidiana en el conjunt dels 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 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

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

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

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'escriu $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 subtracció 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 de l'ordre del logaritme de l'enter.

Mètode corrent, binari

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\leq 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\leq 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 dicotomies 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ó.

Concatenant 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

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ó euclidiana, 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_{i}10^{N_{i}}$ : en efecte la desigualtat que dona $q_{r}$ per a la primera ocurrència de $N_{r}=0$ serà: $0\leq a-b\times \sum _{i}q_{i}10^{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.

Referències

↑ «Euclid's Division Algorithm - Definition, Statement, Examples» (en anglès). [Consulta: 16 febrer 2022].
↑ «What does Euclidean algorithm mean?». [Consulta: 16 febrer 2022].
↑ «Division and Euclidean algorithms». Arxivat de l'original el 2021-05-06. [Consulta: 16 febrer 2022].
↑ Enzo Gentile: Aritmética elemental; ediciones OEA

Vegeu també

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Divisió euclidiana

[1] «Euclid's Division Algorithm - Definition, Statement, Examples» (en anglès). [Consulta: 16 febrer 2022].

[2] «What does Euclidean algorithm mean?». [Consulta: 16 febrer 2022].

[3] «Division and Euclidean algorithms». Arxivat de l'original el 2021-05-06. [Consulta: 16 febrer 2022].

[4] Enzo Gentile: Aritmética elemental; ediciones OEA

[1]

[2]

[3]

[4]