n
Ã(n) Ã(n) = d.
d|n
p Ã(p) = p + 1
Ã(n) = 2n
6 = 1 + 2 + 3
n
Ä(n) Ä(n) = 1.
d|n
f
f F
F (n) = f(d).
d|n
f(n) = n2
F (15) = f(d) = f(1) + f(3) + f(5) + f(15) = 1 + 9 + 25 + 225 = 260.
d|15
f
m n
f(mn) = f(m)f(n).
m n
f
f(n) = n, g(n) = 1 h(n) = n2
1 2
s
f n = pa · pa · ... · pa
1 2 s
n
1 2 s
f(n) = f(pa ) · f(pa ) · ... · f(pa ).
1 2 s
f F
m n
f
F (mn) = f(k) = f(dd ) = f(dd ) =
k|mn dd |mn d|m d |n
f(d)f(d ) = f(d) f(d ) = F (m)F (n).
d|m d |n d|m d |n
f(n) = n2
F (15) = 260 f
F (3)F (5) = (f(1) + f(3))(f(1) + f(5)) = (1 + 9)(1 + 25) = 260.
à Ä
f(n) = n g(n) = 1
(i)
NW D(m, km + r) = NW D(m, r)
(ii) NW D(m, n) = 1
r, m + r, 2m + r, ..., (n - 1)m + r
n
(iii) t m n
mn
(i) NW D(km + r, m) = d d|km +r d|m r
d|r NW D(km+r, m) | NW D(m, r)
NW D(m, r) = d d|m d|r d|km + r
NW D(m, r) | NW D(km + r, m)
(ii) r, m + r, 2m + r, . . . , (n - 1)m + r,
n NW D(m, n) = 1
kim + r a" kjm + r (mod n). m(ki - kj) a" 0 (mod n).
n m(ki - kj) NW D(m, n) = 1
n ki-kj
(iii) NW D(t, m) = NW D(t, n) = 1 NW D(t, mn) = d > 1
d p p|mn p|m
p|n p|t p|NW D(t, m)
p|NW D(t, n)
Õ
m n
Õ(mn) = Õ(m)Õ(n)
mn n
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
mn
r NW D(m, r) = 1 Õ(m)
Õ(n)
r d" m r km + r
NW D(m, r) = d = 1 (i) NW D(m, km + r) = d = 1
0 d" k d" n - 1 m
mn
mn Õ(m)
NW D(m, r) = 1
(ii) n
n
Õ(n) n
Õ(n)
m (iii)
mn Õ(mn) = Õ(m)Õ(n)
Õ(12) = Õ(3)Õ(4) = 2(4 - 2) = 4
Õ(36) = Õ(4)Õ(9) = (4 - 2)(9 - 3) = 12.
p
k
1
Õ(pk) = pk 1 - .
p
1 2 k
n = pa · pa · . . . · pa
1 2 k
n
1 1 1
Õ(n) = n 1 - 1 - · · · 1 - .
p1 p2 pk
Õ
1 2 k
Õ(n) = Õ(pa ) · Õ(pa ) · ... · Õ(pa )
1 2 k
1 1 1
1 2 k
Õ(n) = p1a 1 - · p2a 1 - · · · pka 1 - =
p1 p2 pk
1 1 1
1 2 k
p1a p2a · · · pka 1 - 1 - · · · 1 - =
p1 p2 pk
1 1 1
n 1 - 1 - · · · 1 - .
p1 p2 pk
1 1
Õ(50) = Õ(2 · 52) = 50(1 - )(1 - ) = 20
2 5
1 1 1
Õ(360) = Õ(23325) = 360(1 - )(1 - )(1 - ) = 96
2 3 5
n Õ(n)
1 2
s
n = pa pa . . . pa
1 2 s
n,
s s
pi - 1
i i-1
Õ(n) = pa = pa (pi - 1).
i i
pi
i=1 i=1
1
n = 2a Õ(n) pi - 1
1
n = 2a n > 2 a1 > 1.
1 1-1
Õ(2a ) = 2a (2 - 1)
F Õ F (6) = Õ(1)+
Õ(2)+Õ(3)+Õ(6) = 1+1+2+2 = 6 F (8) = Õ(1)+Õ(2)+Õ(4)+Õ(8) =
1 + 1 + 2 + 4 = 8.
n
F (n) := Õ(d) = n.
d|n
n a <" b
NW D(a, n) = NW D(b, n) NW D
d|n NW D(d, n) = d
d n
n
a n
a " [d] NW D , = 1
d d
n
[d] Õ
d
n
n = Õ
d
d|n
n
d n
d
n
n = Õ = Õ(d)
d
d|n d|n
n = 36 {1, 2, 3, ..., 36}
[d] d 36 [d]
a NW D(a, 36) = d
[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}.
[d] Õ(36/d)
[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.
12 + 6 + 4 + 6 + 2 + 2 + 2 + 1 + 1 = 36
36 = Õ(36)+Õ(18)+Õ(12)+Õ(9)+Õ(6)+Õ(4)+Õ(3)+Õ(2)+Õ(1) = Õ(d).
d|36
Wyszukiwarka
Podobne podstrony:
ustawa 12 2010 zm ustawy o stos P do KK13 12 20108 Systemy Operacyjne 21 12 2010 Zarządzanie Pamięcią Operacyjnąwyklad 10 14 12 2010zajecia1 12 2010recepty z 13,12,2010rozklad kanalow 12 2010FM wyklad 8 1 12 201006 12 201012 Budowa i funkcje układu krwionośnego cz1 Krew 2014nmgFM wyklad 9 9 12 2010Systemy Operacyjne 07 12 2010 Kontekst i jego połączeniewięcej podobnych podstron