Teoria liczb 2010, sem.IV,

B.Bajorska, O.Macedo«ska

Wykªad 12.

Funkcje arytmetyczne

1 Multiplikatywno±¢ funkcji arytmetycznych

Denicja 1. Funkcj¡ arytmetyczn¡ nazywamy dowoln¡ funkcj¦ okre±lon¡ na

zbiorze liczb naturalnych o warto±ciach w zbiorze liczb caªkowitych.

Przykªad Funkcj¡ arytmetyczn¡ jest np funkcja Eulera (Wykªad 6, Roz.4).

W drugiej cz¦±ci wykªadu omówimy kilka wªasno±ci tej funkcji oraz przedsta-

wimy pomini¦ty wcz¦sniej dowód postaci funkcji Eulera (Wykªad 6, Tw.4).

Omówimy pokrótce kilka innych znanych funkcji arytmetycznych.

Denicja 2. Funkcj¦ Sumy Dzielników dla liczby naturalnej n okre±la si¦

jako sum¦ wszystkich dodatnich dzielników tej liczby. Oznaczamy j¡ przez
σ(n)

i wyra»amy wzorem: σ(n) =

P

d|n

d.

Przykªad Dla dowolnej liczby pierwszej p mamy σ(p) = p + 1.

Denicja 3. Liczb¦ naturaln¡ speªniaj¡c¡ warunek σ(n) = 2n nazywamy

liczb¡ doskonaª¡.

Przykªad Najmniejsz¡ liczb¡ doskonaª¡ jest 6, bo 6 = 1 + 2 + 3. Kolejn¡

jest 28.
Denicja 4. Funkcj¦ Liczby Dzielników dla liczby naturalnej n okre±la

si¦ jako liczb¦ wszystkich dodatnich dzielników tej liczby. Oznaczamy j¡ przez
τ (n)

i wyra»amy wzorem: τ(n) =

P

d|n

1.

Denicja 5. Niech f b¦dzie funkcj¡ arytmetyczn¡. Sumatorem (lub funkcj¡

sumuj¡c¡) funkcji f nazywamy funkcj¦ arytmetyczn¡ F okre±lon¡ wzorem

F (n) =

X

d|n

f (d).

Przykªad Niech f(n) = n

2

. Wtedy np.

F (15) =

X

d|15

f (d) = f (1) + f (3) + f (5) + f (15) = 1 + 9 + 25 + 225 = 260.

Denicja 6. Funkcj¦ arytmetyczn¡ f nazywamy multiplikatywn¡, je±li dla

ka»dej pary wzgl¦dnie pierwszych liczb naturalnych m i n zachodzi równo±¢

f (mn) = f (m)f (n).

Je±li powy»szy warunek jest speªniony dla ka»dej pary liczb naturalnych m i n,

to funkcj¦ f nazywamy caªkowicie multiplikatywn¡.

1

Przykªad Funkcje f(n) = n, g(n) = 1, oraz h(n) = n

2

s¡ caªkowicie

multiplikatywne.

Z powy»szej denicji indukcyjnie wynika natychmiast nast¦puj¡cy

Wniosek 1. Je±li f jest funkcj¡ multiplikatywn¡ i je±li n = p

a

1

1

· p

a

2

2

· ... · p

a

s

s

jest rozkªadem kanonicznym liczby naturalnej n, to

f (n) = f (p

a

1

1

) · f (p

a

2

2

) · ... · f (p

a

s

s

).

Twierdzenie 1. Je±li f jest funkcj¡ multiplikatywn¡ to jej sumator F te»

jest funkcj¡ multiplikatywn¡.
Dowód. Niech m, n b¦d¡ wzgl¦dnie pierwszymi liczbami naturalnymi. Wte-

dy z multiplikatywno±ci funkcji f mamy:

F (mn) =

X

k|mn

f (k) =

X

dd

0

|mn

f (dd

0

) =

X

d|m

X

d

0

|n

f (dd

0

) =

X

d|m

X

d

0

|n

f (d)f (d

0

) =

X

d|m

f (d)

X

d

0

|n

f (d

0

) = F (m)F (n).

Przykªad Jak obliczyli±my wy»ej, dla funkcji f(n) = n

2

, mamy np.

F (15) = 260

. Poniewa» f jest funkcj¡ multiplikatywn¡, to ten sam wynik

otrzymamy korzystaj¡c z powy»szego twierdzenia:

F (3)F (5) = (f (1) + f (3))(f (1) + f (5)) = (1 + 9)(1 + 25) = 260.

Wniosek 2. Funkcja Sumy Dzielników σ i Funkcja Liczby Dzielników τ s¡

multiplikatywne.
Dowód. Zauwa»my, »e funkcje Sumy Dzielników i Liczby Dzielników s¡ su-

matorami funkcji multiplikatywnych  odpowiednio f(n) = n i g(n) = 1 

zatem z Twierdzenia 1 wynika, »e s¡ multiplikatywne.

2 Funkcja Eulera

Udowodnimy twierdzenie o warto±ciach funkcji Eulera (Wykªad 6, Tw.4),

wykorzystuj¡c funkcje arytmetyczne. Dla dalszych rozwa»a« przypomnijmy

nast¦puj¡ce fakty
Lemat 1. (i) Dla dowolnego caªkowitego k zachodzi równo±¢

NW D(m, km + r) = NW D(m, r)

.

(ii)

Je±li NW D(m, n) = 1, to liczby:

r, m + r, 2m + r, ..., (n − 1)m + r

tworz¡ peªny ukªad reszt modulo n.
(iii)

Je±li liczba t jest wzgl¦dnie pierwsza z m i z n, to te» jest wzgl¦dnie

pierwsza z mn.

2

Dowód. (i) Je±li NW D(km+r, m) = d, to d|km+r i d|m. Poniewa» r jest

kombinacj¡ liniow¡ tych liczb, wi¦c d|r a st¡d NW D(km+r, m) | NW D(m, r).

Je±li NW D(m, r) = d, to d|m d|r, wi¦c w szczególno±ci d|km + r, a zatem
NW D(m, r) | NW D(km + r, m)

. St¡d mamy równo±¢.

(ii)

Wystarczy pokaza¢, »e liczby r, m + r, 2m + r, . . . , (n − 1)m + r,

s¡ ró»ne modulo n wiedz¡c, »e NW D(m, n) = 1. Zaªó»my przeciwnie, »e
k

i

m + r ≡ k

j

m + r (mod n).

Odejmuj¡c mamy m(k

i

− k

j

) ≡ 0 (mod n).

St¡d

wynika, »e n dzieli m(k

i

− k

j

)

, a ze wzgl¦du na zaªo»enie NW D(m, n) = 1

mamy z Lematu Euklidesa (Wykªad 3, Lem.2), »e n dzieli k

i

−k

j

, sprzeczno±¢.

(iii)

Zaªó»my, »e NW D(t, m) = NW D(t, n) = 1 oraz NW D(t, mn) = d > 1.

Liczba d ma dzielnik pierwszy p (Wykªad 5, Lem.1). St¡d p|mn a wi¦c p|m

lub p|n (Wykªad 6, Lem.1). Poniewa» mamy tak»e p|t, to p|NW D(t, m) lub
p|NW D(t, n)

, sprzeczno±¢.

Teraz udowodnimy, »e funkcja ϕ jest multiplikatywna.

Twierdzenie 2. Niech m, n b¦d¡ wzgl¦dnie pierwszymi liczbami naturalnymi.

Wtedy ϕ(mn) = ϕ(m)ϕ(n).

Dowód. Zapiszemy liczby naturalne nie wi¦ksze od mn w n kolumnach:

1 m + 1 2m + 1 . . . (n − 1)m + 1

2

m + 2 2m + 2 . . . (n − 1)m + 2

...

...

...

...

...

r

m + r 2m + r . . . (n − 1)m + r

...

...

...

...

...

m

2m

3m

. . .

mn

Ide¡ dowodu jest to, by pokaza¢, »e liczby wzgl¦dnie pierwsze z mn stoj¡

tylko w wierszach z numerem r, gdzie NW D(m, r) = 1, czyli w ϕ(m) wier-

szach, w ka»dym po ϕ(n) takich liczb.

Z tabeli wida¢, »e r ≤ m, a r-ty wiersz skªada si¦ z liczb km + r. Je±li

NW D(m, r) = d 6= 1

to z Lematu 1(i) mamy NW D(m, km + r) = d 6= 1,

0 ≤ k ≤ n − 1

, wi¦c liczby w tym wierszu nie s¡ wzgl¦dnie pierwsze z m, a

wi¦c tym bardziej nie s¡ wzgl¦dnie pierwsze z mn.

Zatem liczby wzgl¦dnie pierwsze z mn le»¡ tylko w ϕ(m) wierszach gdzie

NW D(m, r) = 1

. Wi¦c wybieramy te wiersze.

Na podstawie Lematu 1(ii), n liczb naturalnych w ka»dym wierszu przed-

stawia peªny ukªad reszt modulo n. A wi¦c w ka»dym wierszu jest dokªadnie
ϕ(n)

liczb wzgl¦dnie pierwszych z n.

Poniewa» w wybranych wierszach te ϕ(n) liczb naturalnych s¡ te» wzgl¦d-

nie pierwsze z m, wi¦c na podstawie Lematu 1(iii) tak»e s¡ one wzgl¦dnie

pierwsze z mn. St¡d ϕ(mn) = ϕ(m)ϕ(n).

Przykªad ϕ(12) = ϕ(3)ϕ(4) = 2(4 − 2) = 4;

ϕ(36) = ϕ(4)ϕ(9) = (4 − 2)(9 − 3) = 12.

3

Przypomnimy jeszcze, »e dla dowolnej liczby pierwszej p oraz dowolnej

liczby naturalnej k mamy (Wykªad 6, Lem.4)

ϕ(p

k

) = p

k

µ

1 −

1
p

¶

.

(1)

Twierdzenie 3. Niech n = p

a

1

1

· p

a

2

2

· . . . · p

a

k

k

b¦dzie rozkªadem kanonicznym

liczby naturalnej n. Wtedy

ϕ(n) = n

µ

1 −

1

p

1

¶ µ

1 −

1

p

2

¶

· · ·

µ

1 −

1

p

k

¶

.

Dowód. Poniewa» z Twierdzenia 2 wiadomo, »e ϕ jest multiplikatywna, to

z Twierdzenia 1 mamy:

ϕ(n) = ϕ(p

a

1

1

) · ϕ(p

a

2

2

) · ... · ϕ(p

a

k

k

)

sk¡d na podstawie wzoru (1) mamy

ϕ(n) = p

1

a

1

µ

1 −

1

p

1

¶

· p

2

a

2

µ

1 −

1

p

2

¶

· · · p

k

a

k

µ

1 −

1

p

k

¶

=

p

1

a

1

p

2

a

2

· · · p

k

a

k

µ

1 −

1

p

1

¶ µ

1 −

1

p

2

¶

· · ·

µ

1 −

1

p

k

¶

=

n

µ

1 −

1

p

1

¶ µ

1 −

1

p

2

¶

· · ·

µ

1 −

1

p

k

¶

.

Przykªad ϕ(50) = ϕ(2 · 5

2

) = 50(1 −

1
2

)(1 −

1
5

) = 20

;

ϕ(360) = ϕ(2

3

3

2

5) = 360(1 −

1
2

)(1 −

1
3

)(1 −

1
5

) = 96

.

Omówimy jeszcze dwie ciekawe wªasno±ci funkcji Eulera.

Twierdzenie 4. Niech n b¦dzie liczb¡ naturaln¡ wi¦ksz¡ od 2. Wtedy ϕ(n)

jest liczb¡ parzyst¡.

Dowód. Zaªó»my, »e n = p

a

1

1

p

a

2

2

. . . p

a

s

s

jest rozkªadem kanonicznym liczby

n,

. Wtedy z Twierdzenia 3 mamy

ϕ(n) =

s

Y

i=1

p

a

i

i

µ

p

i

− 1

p

i

¶

=

s

Y

i=1

p

a

i

−1

i

(p

i

− 1).

Je±li n 6= 2

a

1

to ϕ(n) jest parzysta, poniewa» pewien czynnik p

i

− 1

jest

parzysty. Jesli n = 2

a

1

, to poniewa» n > 2, to mamy a

1

> 1.

Wtedy

ϕ(2

a

1

) = 2

a

1

−1

(2 − 1)

jest parzysta.

Zauwa»my, »e dla sumatora F funkcji ϕ mamy na przykªad F (6) = ϕ(1)+

ϕ(2)+ϕ(3)+ϕ(6) = 1+1+2+2 = 6

oraz np F (8) = ϕ(1)+ϕ(2)+ϕ(4)+ϕ(8) =

1 + 1 + 2 + 4 = 8.

Okazuje si¦, »e te wyniki nie s¡ przypadkowe.

4

Twierdzenie 5. Niech n b¦dzie liczb¡ naturaln¡. Wtedy

F (n) :=

X

d|n

ϕ(d) = n.

Dowód W zbiorze liczb naturalnych od 1 do n wprowadzimy relacj¦: a ∼ b

je±li NW D(a, n) = NW D(b, n). Z wªasno±ci NW D wynika, »e jest to relacja

równowa»no±ci. Poniewa» d|n wtedy i tylko wtedy, gdy NW D(d, n) = d, to

ka»dy dzielnik d liczby n wyznacza inn¡ klas¦ abstrakcji. Zatem ilo±¢ klas

jest równa ilo±ci dzielników, a suma ilo±ci elementów wszystkich klas jest n.

Zauwa»my, »e a ∈ [d] wtedy i tylko wtedy gdy NW D

¡

a
d

,

n

d

¢

= 1

(Wy-

kªad 3, Wn.3). St¡d wynika, »e ilo±¢ elementów w klasie [d] jest równa ϕ

¡

n

d

¢

,

a wi¦c z powy»szych rozwa»a« mamy

n =

X

d|n

ϕ

³n

d

´

Skoro d przebiega wszystkie dzielniki liczby n, wi¦c

n

d

równie». St¡d

n =

X

d|n

ϕ

³n

d

´

=

X

d|n

ϕ(d)

Przykªad Niech n = 36. Zbiór {1, 2, 3, ..., 36} jest sum¡ dziewi¦ciu klas

[d]

, gdzie d jest dzielnikiem liczby 36. Klasa [d] zawiera te liczby naturalne

a

, dla których NW D(a, 36) = d. Mamy wi¦c:

[1] = {1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35};
[2] = {2, 10, 14, 22, 26, 34};
[3] = {3, 15, 21, 33};
[4] = {4, 8, 16, 20, 28, 32};
[6] = {6, 30};
[9] = {9, 27};
[12] = {12, 24};
[18] = {18};
[36] = {36}.
Widzimy, »e klasa [d] zawiera ϕ(36/d) liczb naturalnych:

¯

¯

¯

¯[1]

¯

¯

¯

¯ = ϕ(36/1) = ϕ(36) = 12;

¯

¯

¯

¯[2]

¯

¯

¯

¯ = ϕ(36/2) = ϕ(18) = 6;

¯

¯

¯

¯[3]

¯

¯

¯

¯ = ϕ(36/3) = ϕ(12) = 4;

¯

¯

¯

¯[4]

¯

¯

¯

¯ = ϕ(36/4) = ϕ(9) = 6;

ϕ(36/6) = 2; ϕ(36/9) = 2; ϕ(36/12) = 2; ϕ(36/18) = 1; ϕ(36/36) = 1.

Zauwa»my, »e 12 + 6 + 4 + 6 + 2 + 2 + 2 + 1 + 1 = 36, to znaczy

36 = ϕ(36)+ϕ(18)+ϕ(12)+ϕ(9)+ϕ(6)+ϕ(4)+ϕ(3)+ϕ(2)+ϕ(1) =

X

d|36

ϕ(d).

5