Teoria liczb 2010, sem.IV,
B.Bajorska, O.Macedo«ska
Wykªad 12.
Funkcje arytmetyczne
1 Multiplikatywno±¢ funkcji arytmetycznych
De nicja 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.
De nicja 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.
De nicja 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.
De nicja 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.
De nicja 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.
De nicja 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 de nicji 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