Divisió euclidiana: diferència entre les revisions
Contingut suprimit Contingut afegit
m neteja i estandardització de codi |
m neteja i estandardització de codi |
||
Línia 38:
: <math>|a| = |b|q_1 + r_1</math> amb <math>r_1< |b|</math>
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''<sub>1</sub> i residu -''r''<sub>1</sub>
: per ''a'' negatiu i ''b'' positiu, quocient -''q''<sub>1</sub> i residu -''r''<sub>1</sub>
: per ''a'' positiu i ''b'' negatiu, quocient -''q''<sub>1</sub> i residu ''r''<sub>1</sub>
Línia 82:
Per al segon càlcul, es construeixen dues successions <math>(\alpha_n)</math> et <math>(\beta_n)</math>; una emmagatzemarà les fites inferiors del quocient buscat, l'altre les fites superiors estrictes. Es comença amb <math>\alpha_0=2^{N-1}</math> i <math>\beta_0=2^N</math>, després per recurrència:
: si <math>\frac{\alpha_n+\beta_n}{2}\times b\le a</math>, llavors es pot afinar la fita inferior, i es fa <math>\alpha_{n+1}=\frac{\alpha_n+\beta_n}{2}</math> i <math>\beta_{n+1}=\beta_n\,</math>
: per altra banda, si <math>\frac{\alpha_n+\beta_n}{2}\times b > a</math>, es pot afinar la fita superior, i es fa <math>\beta_{n+1}=\frac{\alpha_n+\beta_n}{2}</math>, i <math>\alpha_{n+1}=\alpha_n\,</math>.
Línia 100:
* [[Aritmètica modular]].
* [[Anell euclidià]].
== Referències ==
{{referències}}
| |||