365605320

dzielona na nieparzystą liczbę, w zależności czy kjest parzyste lub nieparzyste. Stąd E(n) - 0(n) = 0, chyba że _n _    ± fc) * kiedy E(n) - 0(n) = (-l)^k. Daje nam to twierdzenie Eulera

Teraz z

\'p(n)xⁿ( 1 — x — x² + x⁶ + x⁷ — x¹² — ■■•) = ! otrzymujemy relację rekurencyjną dla p(n),mianowicie

p(n) — p(n — 1) + p(n — 2) — p(n — 5) — p(n — 7) + p(n — 12) 4- • • •

II. funkcje “Arytmetyczne

Kolejnym tematem jakim się zajmiemy są funkcje arytmetyczne. Stanowią one główne obiekty zainteresowania w teorii liczb. Zajmiemy się teraz następującymi funkcjami

7r(n) —    1

p<n

um = 'E¹

p\n

Si(n) =    1

Pⁱ|«

Liczba liczb pierwszych nie przekraczających n Liczba różnych liczb pierwszych stopnia n

Liczba liczb pierwszych o współczynniku moc n

r(n) = Ei Liczba dzielników liczby n

d\n

(r{n) = d Suma dzielników liczby n -

d\n

ip(n) =    1 Funkcja totient Eulera

(a,n)=l

l<a<n

Funkcja Eulera (tocjent) zlicza liczbę liczb całkowitych < n i względnie pierwszych dla n. Tu skupimy się szczególnie na funkcjach t (n), o(n) i <p(n). Mają one ważną właściwość, taką,że jeśli

n = ab and (a; b) = 1

wtedy

f(ab) = f(a)f(b)

Dowolna funkcja spełniająca ten warunek jest nazywana słabo multiplikatywną lub po prostu mul tipi i kąty wną