Aratati ca:
a)

, n>0
b)

, n-compus
c)

, n>6
d)

, n>6
e)

, n-compus
unde

sunt, in ordine, numarul divizorilor lui n, suma divizorilor lui n si numarul de numere mai mici decat n si prime cu n (indicatorul lui Euler).

[Citat] Aratati ca: (a) , n>0 (b) , n-compus (c) , n>6 (d) , n>6 (e) , n-compus unde sunt, in ordine, numarul divizorilor lui n, suma divizorilor lui n si numarul de numere mai mici decat n si prime cu n (indicatorul lui Euler).

(a) Functia tau satisface "un fel de multiplicativitate", numita multipliativitate stricta, multiplicativitate aritmetica, ... sau pur si simplu doar multiplicativitate cand e vorba de functii aritmetice.
Anume:

Daca a si b sunt numere relativ prime intre ele, atunci
tau(ab) = tau(a) ta(b) .

Sa aratam mai intai inegalitatea pentru puteri de numere prime.
(Problema afirma ca are loc pentru ele. Cazul cel mai rau este cand avem o putere a lui doi. Ne descurcam destul de repede.)

(b) Sa plecam cu un n compus. Fie n=ab cu a,b doi divizori primi intre ei ai lui n. Desigur ca atunci unul din ei, b sa zicem, este strict mai mare ca celalalt, deci si ca radical(n).
Atunci ajunge sa adunam n cu b ca sa scapam de granita...

(c) Sa aratam mai intai inegalitatea pentru puteri de numere prime... Apoi avem de-a face cu un fel de multiplicativitate, cazul in care intervine 2 sau 4 ca putere a lui doi ce intra in n trebuie considerat la o parte.

(d) Ca si la (c)...

(e) Fie p cel mai mic numar prim ce divide n.
Atunci n/p este cel putin p, deoarece n este compus.
In orice caz,
p
este mai mic sau egal decat
radical(n)
care este mai mic sau egal decat
n/p .

n - phi(n) este numarul de numere "sub" n care nu sunt prime cu n.
Printre acestea se afla p, 2p, ... , np care sunt in numar de n/p, un numar mai mare decat radical(n).