Fie x si b doua numere naturale, cu b 2. Notam prin [a] partea intreaga a unui numar real a, adica cel mai mare intreg mai mic sau egal cu a.
Propozitia 1: Restul impartirii lui x la b este x - b[x/b].
Demonstratie: Vom folosi proprietatea cunoscuta a partii intregi a unui numar real, si anume:
a R, a-1 < [a] a.
Conform acestei proprietati avem, pentru a = x/b,
x/b-1 < [x/b] x/b
si, inmultind aceasta dubla inegalitate cu b, gasim
x-b < b[x/b] x
de unde rezulta imediat ca
0 x - b[x/b] < b.
Conform teoremei impartirii cu rest, exista in mod unic doua numere c (cat) si r (rest), luand in cazul nostru:
c = [x/b] si r = x-b[x/b]
Catul si restul astfel alese verifica conditia de existenta.
Consideram un numar 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 impartirii 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. Notam 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 demonstreaza formula data.
Aplicatii:
1. Din scrierea lui x de mai sus se poate deduce ca fk reprezinta simbolurile numerice de reprezentare a numarului x in baza de numeratie b, in ordinea data. Asadar, daca f1, f2, , fn sunt aceste simboluri numerice, numarul x se mai poate scrie:
Se poate spune deci ca fk este a k-a cifra(simbol) de reprezentare in baza de numeratie b a numarului x, unde x,b N, 0 x bn-1, b 2 iar
fk = [x/bn-k]-b[x/bn-k+1], k = 1, 2, , n.
2. Functia fk este o cale mai scurta de a determina prin calcul simbolurile de reprezentare a unui numar intr-o baza de numeratie oarecare b.
. Ca amuzament matematic se poate concepe un algoritm simplu pentru a "ghici " un numar ales de cineva, urmand pasii urmatori:
P1: Fixati un numar natural b 2 si un numar natural n.
