Metodã de generare a resturilor unor împãrtiri succesive
Fie x si b douã numere naturale, cu b ? 2. Notãm prin [a] partea întreagã a unui numãr real a, adicã cel mai mare întreg mai mic sau egal cu a. Propozitia 1: Restul împãrtirii lui x la b este x - b[x/b]. Demonstratie: Vom folosi proprietatea cunoscutã a pãrtii întregi a unui numãr real, si anume:
? a? R, a-1 < [a] ? a.
Conform acestei proprietãti avem, pentru a = x/b,
x/b-1 < [x/b] ? x/b
si, înmultind aceastã dublã inegalitate cu b, gãsim
x-b < b[x/b] ? x
de unde rezultã imediat cã
0 ? x - b[x/b] < b.
Conform teoremei împãrtirii cu rest, existã în mod unic douã numere c (cât) si r (rest), luând în cazul nostru:
c = [x/b] si r = x-b[x/b]
Câtul si restul astfel alese verificã conditia de existentã.
Considerãm un numãr x? N, cu 0 ? x ? bn-1. Definitie: Expresia fk = [x/bn-k]-b[x/bn-k+1] se numeste restul de ordin k al împãrtirii succesive a lui x prin puteri ale lui b, k = 1, 2, ..., n. Propozitia 2: 0 ? fk ? b-1, ? k, k = 1, 2, ..., n. Demonstratie: Fie un k fixat, k = 1, 2, ..., n. Notãm cu yk = [x/bn-k]. Atunci fk = yk - b[yk/b] este un rest de ordin k conform definitiei si conform propozitiei 1 avem 0 ? fk ? b-1.
Propozitia 3: Pentru orice x natural cu 0 ? x ? bn-1 si b? 2 avem Demonstratie: Suma din dreapta se mai poate scrie:
f1bn-1 + f2bn-2 +...+ fn-1b1 + fnb0 = = ([x/bn-1]-b[x/bn])bn-1 + ([x/bn-2]-b[x/bn-1])bn-2 +...+ ([x/b]-b[x/b2])b + ([x/b0]-b[x/b])b0 = = [x] - bn[x/bn] = x - bn[x/bn].
Dar x ? bn-1 < bn, deci [x/bn] = 0, ceea ce demonstreazã formula datã.
Aplicatii:
1. Din scrierea lui x de mai sus se poate deduce cã fk reprezintã simbolurile numerice de reprezentare a numãrului x în baza de numeratie b, în ordinea datã. Asadar, dacã f1, f2, ..., fn sunt aceste simboluri numerice, numãrul x se mai poate scrie:
Se poate spune dec