Algorithmus Divisionis

In hac lectione evolvemus algorithmum divisionis ut principium quod, pro numeris integris, decompositionem unicam formalizat b=qa+r cum 0\le r<|a|. Primum demonstratur existentia quocientis et reliqui, deinde eorum unicitas. Denique interpretatur significatio reliqui, coniungitur theoria cum algorithmo longo divisionis ut ratione calculi, atque praevidetur eius naturalis connexio cum arithmetica modulari et applicationibus computatoriis.

Proposita Discendi

Hac lectione confecta, discipulus erit idoneus ad:

1. Identificare notiones et partes fundamentales divisionis integrae (dividendus, divisor, quociens, reliquum) atque notionem divisibilitatis ut casum exactum.
2. Explicare enuntiationem algorithmi/theorematis divisionis Euclideae, inclusis condicionibus quae reliquum determinant (0\le r<|a|) et earum fine ad ambiguitates vitandas.
3. Applicare decompositionem Euclideam b=qa+r ad determinanda q et r in exemplis concretis, terminum reliqui comprobans.
4. Analyzare tractationem casuum secundum signum dividendi et divisoris, iustificans cur conventio Euclidea reliquum non negativum servet.
5. Exsequi algorithmum longum divisionis ut processum mechanicum in repraesentatione positionali fundatum ad obtinenda q et r.

INDEX RERUM:
Divisio et divisibilitas
Theorema divisionis Euclideae
Demonstratio divisionis Euclideae
Interpretatio quocientis et reliqui
Algorithmus longus divisionis
Conclusio
Exercitia proposita et soluta

Divisio et divisibilitas

In arithmetica, divisibilitas casum «exactum» describit: a\mid b significat b exacte scribi ut multiplex a. Attamen, quamquam non semper est divisibilitas inter duos integros quoscumque, tamen quaerere possumus «quoties unus numerus intra alterum conveniat et, si non exacte conveniat, quid supersit». Hic est contextus in quo oritur algorithmus divisionis, qui praestat ut integer quilibet b scribi possit ut multiplex a addito «reliquo».

Exempli gratia, consideremus a=3 et b=16. Manifestum est 3 non dividere 16. Tamen possibile est invenire quocientem et reliquum pro operatione divisionis, quoniam

16 = 5\cdot 3 + 1

Quapropter, diviso b=16 per a=3 (ubi b est dividendus et a est divisor), quod repraesentatur per 16/3 vel 16\div 3, obtinetur ut quociens q=5 et ut reliquum r=1. In universum, algorithmus divisionis affirmat quod, pro quibuscumque numeris integris a (divisore) et b (dividendo) cum a\neq 0, exsistunt integri unici q et r tales ut

b=qa+r,\qquad 0\le r<|a|

In hoc exemplo, 16=3\cdot 5+1, et condicio 0\le r<|a| impletur, quoniam 0\le 1<3. Haec formatio ambiguitates vitat, cum divisor (vel dividendus) negativus esse possit, atque praestat ut reliquum semper sit non negativum et stricte minus quam valor absolutus divisoris.

Theorema divisionis Euclideae

Effectus applicationis algorithmi divisionis est id quod divisio Euclidea appellatur, atque innititur sequenti enuntiato.

Theorema: Sint a,b\in\mathbb{Z} cum a\neq 0. Tunc exsistunt q,r\in\mathbb{Z} unici tales ut

b=qa+r,\qquad 0\le r<|a|.

Integer q quociens vocatur, et r reliquum divisionis b per a.

Demonstratio divisionis Euclideae

Haec demonstratio in duas partes dividitur: primum ostenditur quocientem et reliquum exsistere; deinde, dato quod exsistant, eos esse unicos.

Existentia

Sint a,b\in\mathbb{Z} cum a\neq 0, et definiamus d=|a|, ita ut d>0. Primum probabimus casum b\ge 0: ostendemus exsistere q,r\in\mathbb{Z} tales ut b=dq+r et 0\le r<d. Deinde tractabimus casum b<0. In fine, substituemus d pro |a|, ut obtineatur forma b=qa+r cum 0\le r<|a|.

Pro b\in\mathbb{Z} cum b\ge 0, statuimus propositionem P(b): «exsistunt q,r\in\mathbb{Z} tales ut b=dq+r et 0\le r<d». Per inductionem demonstrabimus P(b) valere pro omni b\ge 0.

Casus basalis: Pro b=0, sumptis q=0 et r=0, obtinetur 0=d\cdot 0+0 et 0\le 0<d. Ergo P(0) vera est.

Gradus inductivus: Sit k\ge 0 et supponamus P(k) veram esse. Tunc exsistunt q,r\in\mathbb{Z} tales ut

k=dq+r,\qquad 0\le r<d.

Addito 1 utrique lateri obtinetur

k+1=dq+(r+1).

Praeterea, ex 0\le r<d sequitur r+1\le d. Quapropter tantum evenire possunt casus r+1<d vel r+1=d.

Casus 1: Si r+1<d, definimus q'=q et r'=r+1. Tunc

k+1=dq'+r',\qquad 0\le r'<d.

Casus 2: Si r+1=d, tunc k+1=dq+d=d(q+1)+0. Definimus q'=q+1 et r'=0, atque valet

k+1=dq'+r',\qquad 0\le r'<d.

In utroque casu integros q',r' construximus tales ut k+1=dq'+r' et 0\le r'<d. Ergo P(k+1) vera est. Concludimus per inductionem P(b) valere pro omni b\ge 0.

Nunc consideremus casum b<0. Tunc -b>0. Applicato superiore effectu ad -b, exsistunt q,r\in\mathbb{Z} tales ut

-b=dq+r,\qquad 0\le r<d.

Multiplicando per -1 obtinetur

b=-dq-r.

Si r=0, satis est sumere q_1=-q et r_1=0, quo fit b=dq_1+r_1 et 0\le r_1<d.

Si r>0, definimus q_1=-q-1 et r_1=d-r. Cum 0<r<d, habetur 0<d-r<d, id est 0\le r_1<d. Praeterea,

dq_1+r_1=d(-q-1)+(d-r)=-dq-d+d-r=-dq-r=b.

Quapropter, pro omni b\in\mathbb{Z} exsistunt q_1,r_1\in\mathbb{Z} tales ut b=dq_1+r_1 et 0\le r_1<d.

Denique, meminerimus d=|a|. Si a>0, tunc d=a, et aequalitas b=dq_1+r_1 scribitur ut b=aq_1+r_1, cum 0\le r_1<|a|.

Si a<0, tunc d=-a, et b=dq_1+r_1=(-a)q_1+r_1=a(-q_1)+r_1. Definito q=-q_1 et r=r_1, obtinetur

b=qa+r,\qquad 0\le r<|a|.

His ita demonstrata est existentia q et r pro quibuscumque a,b\in\mathbb{Z} cum a\neq 0.

Unicitas

Supponatur exsistere q,q',r,r'\in\mathbb{Z} tales ut

b=qa+r=q'a+r',\qquad 0\le r,r'<|a|.

Subtrahendo utrasque expressiones obtinetur

a(q-q')=r'-r.

Quoniam 0\le r,r'<|a|, valet |r'-r|<|a|. At vero membrum sinistrum est multiplex a, atque ideo etiam multiplex |a|. Unicum multiplex integrum |a| cuius valor absolutus stricte minor est quam |a| est 0; etenim, si |a| m \neq 0 cum m\in\mathbb{Z}, tunc \big| |a| m \big| \ge |a| . Quare r'-r=0, id est r=r', atque substituendo in b=qa+r deducitur q=q'. Propterea decompositio unica est.

Interpretatio quocientis et reliqui

• Quid significet «reliquum». Si b=qa+r, tunc r=b-qa est id quod «superest» postquam a b removetur multiplex qa. Aliis verbis, r est residuum adaequationis b ad reticulum multiplicium a.
• Cur exigatur 0\le r<|a|. Sine hac condicione, par (q,r) unicum non esset. Nam, si b=qa+r, tunc etiam b=a(q+1)+(r-a). Condicio 0\le r<|a| cogit reliquum intra fenestram fixam \{0,1,2,\dots,|a|-1\} consistere, atque ita infinitas «re-nominationes» eiusdem numeri impedit.
• Quid accidat si a negativus est. Theorema sine mutationibus valet: reliquum manet non negativum et limite |a| terminatum. Hoc interest, quoniam nonnulli linguarum programmandi truncationem ad zerum adhibent et reliqua negativa producere possunt, dum in mathematicis conventio 0\le r<|a| adhibetur, ut reliquum sit repraesentans «normatum».

  Praeterea, cum a>0, quociens cum pavimento congruit:

  q=\left\lfloor \frac{b}{a}\right\rfloor,\qquad r=b-a\left\lfloor \frac{b}{a}\right\rfloor.

Algorithmus longus divisionis

Ex divisione Euclidea fieri potest ut algorithmus longus divisionis impleatur, adhibita repraesentatione positionali numerorum. Hic algorithmus est ars calculandi quae sinit valores q et r celeriter inveniri, cum computare velimus b\div a cum a,b\in\mathbb{Z} et a\neq 0.

Ad eum describendum, prius nonnulla exempla inspiciamus quae processum et varias condiciones in cursu algorithmi ostendunt.

1. Supponamus nos velle computare 57\div 4. Hic 57 est dividendus et 4 divisor. Ad hoc efficiendum, sequentem computationum seriem peragemus:

   \begin{array}{rll} (1) & \color{red}57 \div 4 =\color{black} \\ & \text{Operationem divisionis scribere.} \\ \\ (2) & \color{red}5'\color{black}7 \div 4 = \\ & \text{Primum praefixum (a sinistra) dividendi separare quod}\\ &\text{maiorem vel aequalem sit divisori, hoc in casu 5.} \\ \\ (3) & 5'7 \div 4 = \color{red}1\color{black} \\ & \text{Cogitare maximum numerum qui, multiplicatus per $4$,}\\ &\text{minor vel aequalis sit quam $5$, eumque ad dextram aequalitatis scribere. Est 1.} \\ \\ (4) & \begin{array}{ll}\phantom{-|}5'7 \div 4 &= 1 \\ \color{red}-|\underline{4}\color{black} & \\ \color{red}\phantom{-|}1\color{black} & \end{array} \\ & \text{Resultatum per divisorem multiplicare et a valore selecto subtrahere.} \\ \\ (5) & \begin{array}{ll}\phantom{-|}5'\color{red}7'\color{black} \div 4 &= 1 \\ -|\underline{4} & \\ \phantom{-|}1\color{red}7\color{black} & \end{array} \\ & \text{Sequentem digitum seligere et «demittere».} \\ \\ (6) & \begin{array}{ll}\phantom{-|}5'7' \div 4 &= 1\color{red}4\color{black} \\ -|\underline{4} & \\ \phantom{-|}17 & \\ \color{red}-|\underline{16}\color{black} & \\ \color{red}\phantom{-|}1\color{black} \end{array} \\ & \text{Seriem cum ultimo numero obtento iterare.} \end{array}

   Algorithmus desinit cum digiti ad «demittendum» exhausti sunt, tradens ut eventum quocientem q=14 et reliquum r=1. Praesertim, reliquum semper erit minus quam divisor.

2. Supponamus nos velle computare 132\div 5. Ad hoc efficiendum, sequentem computationum seriem peragemus:

   \begin{array}{rl} (1) &1'32 \div 5 = \\ & \text{Primum praefixum dividendi separare et quaerere aliquem naturalem qui,}\\ & \text{multiplicatus per 5, minor vel aequalis sit eo. Si id fieri non potest,}\\ & \text{sequentem digitum adiungere donec fieri possit.} \\ \\ (2) &\begin{array}{ll}\phantom{-|}13'2 \div 5 &= 2 \\ -|\underline{10} & \\ \phantom{-|1}3 & \end{array}\\ & \text{Cum gradus superior succedat, algorithmum more solito exsequi.} \\ \\ (3) &\begin{array}{ll}\phantom{-|}13'2' \div 5 &= 26 \\ -|\underline{10} & \\ \phantom{-|1}32 & \\ \phantom{\,} -|\underline{30} & \\ \phantom{-|30} 2 & \end{array} \end{array}

3. Si dividendus plures digitos habet, processus eodem modo exsequitur. Exempli gratia, computando 3521\div 12 obtinetur:

   \begin{array}{ll} \phantom{-|}35'2'1' \div 12 & = 293 \\ -|\underline{24} & \\ \phantom{-|}112 & \\ -|\underline{108} & \\ \phantom{-|10}41 & \\ \phantom{0}-|\underline{36} & \\ \phantom{10-|}5 & \\ \end{array}

4. Si unus numerorum negativus est, duae formae acceptabiles ad eventum exhibendum exstant. Attamen, forma normata in theoria numerorum est illa in qua reliquum est positivum atque ideo cum divisione Euclidea congruens. Exempli gratia, si computamus -598\div 21, sequentes progressus possibiles habentur, ambo recti ut identitates:

   • Cum reliquo negativo: Hoc obtinetur signo in initio operationis remoto et in fine restituto.

     \begin{array}{ll} \phantom{-}59'8' \div 21 &= 28 \\ -|\underline{42} & \\ \phantom{-|'}178 & \\ \phantom{\,}-|\underline{168} & \\ \phantom{-|00}10 & \\ \end{array}

     Ex hoc sequitur:

     598 = 21 \times 28 + 10

     Deinde, si totam aequalitatem per -1 multiplicamus, obtinetur:

     -598 = 21 \times (-28) - 10

     Itaque, hac repraesentatione, eventus -598\div 21 est quociens q=-28 et reliquum r=-10.

     Et si rursus totam aequalitatem per -1 multiplicamus, obtinetur:

     598 = (-21)\times(-28) + 10

     Itaque eventus computationis 598\div (-21) est quociens q=-28 et reliquum r=10.

   • Cum reliquo positivo et cum divisione Euclidea congruente: Ex superiore progressu habetur:

     -598 = 21 \times (-28) - 10

     Deinde, addito 0=21-21 in latere dextro huius aequalitatis, obtinetur:

     -598 = 21 \times (-28) - 10 \color{red}+ 21 - 21\color{black} = 21\times(-29) + 11

     Quapropter, divisioni Euclideae consentientes, eventus computationis -598\div 21 est quociens q=-29 et reliquum r=11.

   Quoad id quod est conventionale in divisione Euclidea, solus eventus cum reliquo positivo ad quocientem et reliquum Euclidea pertinet. Attamen, utraque expressio identitates rectae sunt atque in diversis contextibus utiles esse possunt. Quamvis algorithmus longus divisionis reliqua negativa producere possit, hoc utile est ad eventus mechanice obtinendos et ad manipulationes algebraicas sine gradibus additicis perficiendas. Ex altera parte, eventus cum reliquo positivo, divisioni Euclideae congruentes, permittunt repraesentantem canonicum cuiusque classis residualis (exempli gratia in \{0,1,\dots,n-1\}) statui, quo integeres modo accurato et ab ambiguitate libero designentur. Notandum est etiam alias repraesentantium conventiones exsistere, ut residua symmetrica, quae aeque validae sunt, semel regula constituta.

Conclusio

Algorithmus divisionis praestat ut omnis divisio integra unico modo exprimi possit ut b=qa+r cum 0\le r<|a|, quo criterium normatum ad quocientem et reliquum interpretandos statuitur, etiam cum numeri negativi intersint. Algorithmus longus divisionis nihil aliud est nisi implementatio practica huius decompositionis, in repraesentatione positionali innixa, quae sinit q et r mechanice computari. Denique, haec forma Euclidea non solum ambiguitates vitat, sed etiam naturaliter cum arithmetica modulari coniungitur: reliquum r agit ut repraesentans canonicus classis residualis b modulo a, quod fundamentum est multarum technicarum in theoria numerorum et in applicationibus computatoriis, quae in proximis expositionibus tractabuntur.

Exercitia proposita et soluta

Divisio Euclidea

1. (solutum) Inveni q et r tales ut

   137 = 9q + r,\qquad 0\le r\lt 9.

   Solutio: Quaere numerum maximum qui, multiplicatus per 9, 137 non superet. Habemus 15\times 9 = 135 et 16\times 9 = 144; igitur quociens quaesitus est q=15. Nunc computa reliquum r=137-9q et verifica 0\le r\lt 9. Verificatione facta habetur:

   r=137-9\cdot 15=137-135=2.

   Igitur 137=9\cdot 15+2 cum 0\le 2\lt 9.

2. (solutum) Inveni q et r tales ut

   2025 = 37q + r,\qquad 0\le r\lt 37.

   Solutio: Quaere numerum maximum qui, multiplicatus per 37, 2025 non superet. Observa 37\times 54 = 1998 et 37\times 55 = 2035; igitur quociens quaesitus est q=54. Nunc computa reliquum r=2025-37q et verifica 0\le r\lt 37. Verificatione facta habetur:

   r=2025-37\cdot 54=2025-1998=27.

   Igitur 2025=37\cdot 54+27 cum 0\le 27\lt 37.

3. Inveni q et r tales ut

   745 = 23q + r,\qquad 0\le r\lt 23.

4. Inveni q et r tales ut

   -314 = 11q + r,\qquad 0\le r\lt 11.

5. Inveni q et r tales ut

   598 = (-21)q + r,\qquad 0\le r\lt |-21|.

6. Reliquum fixum et inquisitio integrorum. Sit a=12.

   (a) Describe collectionem omnium integrorum b quorum divisio Euclidea per 12 reliquum r=5 habet.

   (b) Inveni minimum integrum b\gt 1000 quod hoc impleat, atque determina quocientem q correspondentem.

Algorithmus longus divisionis

In singulis casibus, algorithmum longum divisionis adhibe ut quocientem q et reliquum r computetur. Eventum in divisionem Euclideam converte, cum algorithmus reliquum negativum praebeat.

1. 84\div 6.
2. 197\div 8.
3. 1256\div 7.
4. -3521\div 12.
5. -98765\div 24.
6. 845\div -13.
7. -12345\div -37.