Viii bob. Taqqoslamalar §. Taqqoslamalar va ularning xossalari

a + b = b + a;

a ■ b = b ■ a;

a + (b + c) = (a + b) + c;

a ■ (b ■ c) = (a ■ b) ■ c;

a ■ (b + c) = a ■ b + a ■ c.

Hosil qilingan chegirmalar sinflari uchun quyidagi xossalar o‘rinli.

13. 
    xossa. a) agar sinfdagi biror son m bilan o‘zaro tub bo‘lsa, u holda bu sinfdagi barcha sonlar bilan ham o‘zaro tub bo‘ladi;
    

2. 
   juft-jufti bilan m modul bo‘yicha taqqoslanmaydigan ixtiyoriy m ta y, y₂,y_m sonlari uchun Z_m = {y₁,y₂,...,y_m);
   
3. 
   agar (a,m) = 1 bo‘lsa, jl-a,2-a,...,/w-aj = Z_m.
   

37. 
    - §. Mutiplikativ funksiyalar. Eyler va Ferma teoremalari
    

[x] va {x} funksiyalar sonlar nazariyasida muhim o‘rin egallaydigan funksiyalar hisoblanadi.

1. 
   ta’rif. Haqiqiy x sonini x dan oshmaydigan eng katta butun songa mos qo‘yuvchi funksiya x ning butun qismi deyiladi va [ x] kabi belgilanadi.
   
2. 
   ta’rif. Haqiqiy x sonini x — [x] ga mos qo‘yuvchi funksiya x ning kasr qismi deyiladi va {x} kabi belgilanadi.
   

Misol 38.1. [2,6] = 2; [—4,75] = —5;{2,6} = 0,6; {—4,75} = 0,25.
[x] funksiyaning foydali jihatlaridan birini quyidagi teorema orqali bilib olamiz.

3. 
   teorema. n! ko‘paytmada p < n tub sonning darajasi quyidagi songa teng:
   

n		n		n
—	+		+
p		p~		p^J

Isbot. Ravshanki, n! ko‘paytmaning ko‘paytuvchilari orasida

tasi p ga

n	tasi p ga,	n	tasi p ^2 ga va hakazo	n
		2		к
_ p _		_ p _		_ p _

bo‘linadi. Ushbu sonlar yig‘indisi n! ko‘paytmaga bo‘linishi mumkin bo‘lgan p ning eng yuqori darajasiga teng bo‘ladi. □
Misol 38.2. 40! soni ko‘pi bilan 3 ning nechanchi darajasiga bo‘linishini aniqlasak,

261

40		40		40
	+		+
3		9		27

= 13 + 4 +1 = 18.

Demak, 40! soni 3¹⁸ ga qoldiqsiz bo‘linadi.
Multiplikativ funksiyalar ham sonlar nazariyasida muhim o‘rin egallaydi.

4. 
   ta’rif. Quyidagi shartlarni qanoatlantirsa 0(a) funksiya multiplikativ funksiya deyiladi:
   

1. 
   0(a) funksiya barcha musbat butun a lar uchun aniqlanib, ko‘pi bilan bitta qiymati 0 ga teng va barcha qolgan qiymatlari 0 dan farqli;
   
2. 
   ixtiyoriy o‘zaro tub a va a₂ musbat butun sonlar uchun
   

0(aa) = 0(^a\ )0(a).
Misol 38.3 0(a) = a^s, seR funksiya mutiplikativ funksiya bo‘ladi.
Multiplikativ funksiyalarning ayrim xossalarini keltirib o‘tamiz.

5. 
   xossa. Multiplikativ funksiyalar uchun quyidagi xossalar o‘rinli:
   

1. 
   ixtiyoriy multiplikativ funksiya uchun 0(1) = 1;
   
2. 
   0 (a) va 0₂(a) multiplikativ funksiyalar bo‘lsin, u holda
   

0_O (a) = 0 (a)0₂ (a) ham multiplikativ funksiya bo‘ladi.
Isbot. a) aytaylik, 0(a_o) ф 0 bo‘lsin, u holda mutiplikativ funksiyaning ikkinchi shartiga asosan
0(a0) = 0(1- a,) = 0(1) -0(a_o),
ya’ni, 0(1) = 1.

2. 
   ravshanki, 0_O (1) = 0 (1)0 (1) = 1. Bundan tashqari, (a, a₂ ) = 1 sonlar uchun:
   

0_O (aa) = 0 (aa )0 (aa ) = 0 (a )0 (a )0 (a )0 (a) =
= 01 Ц02 Ц )0 («2 )02 (^a2 ) = 00 (^a1 )00 (^a2 ).

Bizga 9(a) multiplikativ funksiya va a sonining kanonik ko‘rinishi a = p2p2² ..p2^k berilgan bo‘lsin. ^9(d) orqali a soni-
d\a
ning barcha bo‘luvchilari bo‘yicha olingan yig‘indini belgilaymiz.

6. 
   xossa.
   

J9(d) = (1 + 0(_A) +... + 9(p2)) •... • (1 + 9( p_k) +... + 9(p;^k)). (38.1)
d\a
Isbot. Xossani isbotlash uchun (38.1) tenglikning o‘ng tomonini ochib chiqamiz. U holda yig‘indi hadlari quyidagi ko‘rinishda bo‘ladi:
9(p?)•9(p?²)•...•9(p?^k) = 9(p? • p?² •...• p?^k), bu yerda 0 < P_x<2_x , 0 < ? < 2₂,..., 0 < ?< 2_k.
Ushbu p?¹ • p?² •... • p?^k sonlar a sonining barcha bo‘luvchilarini beradi, hamda yig‘indida hech bir had ikki marta takrorlanmaydi, demak tenglikning o‘ng tomoni aynan chap tomoniga teng. □
Ushbu xossadan quyidagi natijalar kelib chiqadi.

7. 
   natija. a = p² • p² •...• p² sonining bo‘luvchilari soni quyidagiga teng:
   

⁽¹ + ²₁⁾ •⁽¹ + ²₂⁾ •... •⁽¹ + ²k⁾.
Isbot. 38.6-xossani 9(a) = 1 multiplikativ funksiya uchun qo‘llasak, (38.1) tenglikning chap tomoni a sonining bo‘luvchilari sonini, o‘ng tomoni esa (1 + 2) • (1 + 2) •... • (1 + 2) ifodani beradi.

8. 
   natija. a = p² • p²² •...• pl^k sonining bo‘luvchilari yig‘indisi quyidagiga teng:
   

2+1 -1 2+1 л 2+1-1
p^{2 — 1} p2 ^{— 1} p.^{2 — 1} A ^{— 1} p₂ ^{— 1} ". pк ^{— 1} .
Isbot. 38.6-xossani 9(a) = a multiplikativ funksiya uchun qo‘llasak, (38.1) tenglikning chap tomoni a sonining bo‘luvchilari

263

а+1 сц+1 а, +1 ^ . р? -1 p₂² -1 р_к^к -1 .. , . yig indisini, o ng tomoni esa —^{1 2} ...■—^к ifodani
P1 ^-1 P2 ^-1 Pk ^-1 beradi. □
a sonining bo‘luvchilari sonini r(a), bo‘luvchilari yig‘indisi esa S (a) kabi belgilanadi.
Misol 38.4. 720 sonining bo‘luvchilari soni va bo‘luvchilari yig‘indisini toping.
г(720) = t(2⁴ ■ 3² ■ 5) = (4 +1) ■ (2 +1) ■ (1 +1) = 30;
2⁴+¹ _-1 3²+¹ _-1 5¹+¹ _-1
S(720) = S(2⁴ ■ 3² ■ 5) = ^{2 1 1 1} = 2418.

2. 
   -1 3 -1 5-1
   

9. 
   ta’rif. Musbat sonlar ustida aniqlangan, hamda a soniga
   

1,2,..., a-1
sonlar ichida a bilan o‘zaro tub bo‘lgan sonlar sonini mos qo‘yuvchi funksiya Eyler funksiyasi deyiladi. Eyler funksiyasi (p(a) kabi belgilanadi.
Misol 38.5.
p(1) = 1, p(2) = 1, p(3) = 2, p(4) = 2, p(5) = 4, p(6) = 2.
Eyler funksiyasining qiymatini berilgan a sonining
a = p^a ■ pI² ■...■ p^ kanonik yoyilmasidan foydalanib, hisoblaydigan formula keltiramiz.

10. 
    tasdiq. p(a) = a
    

1—
V P2 J

1 ^-1

0. 
   

V P1 J
Isbot. Avval a tub son bo‘lgan holni qaraymiz, ya’ni a = p biror tub songa teng bo‘lsin. U holda p tub son ekanligidan 1,2,3,..., p-1 sonlarni xar biri bilan o‘zaro tub bo‘ladi. Demak, P( P ) = P-1.
Endi a biror tub sonning darajasi ko‘rinishida bo‘lsin ya’ni a = p^a. U holda
^{{1, 2, 3,}...^,p^{a 2}p^{, 3}p^, ...^,(p“^{-1 -1)}■ p^} sonlarning barchasi p^a bilan o‘zaro tub, ya’ni p(p^a) = p^a - p^a1.

Aytaylik, a = p • p₂ ko‘rinishda bo‘lsin, bu yerda p_x, p₂ tub sonlar. Umumiylikka ziyon yetkazmagan holda p_x < p₂ deb olib,

{^1,2,...^, p,p 2 ^—1} \ ^_JPl^,2 p₁^,^.p₁^,...^,( p₂ ^— Г) p₁^, P2^,2 p2^,^,p2^,..^,( Л ^—x) p2^} sonlarni qaraymiz. Bu sonlarning barchasi pjp₂ bilan o‘zaro tub bo‘ladi, ya’ni
P⁽p,p2⁾ = № ^— p, ^— p2 + ¹ = ⁽p, ^—1)(p2 ^{— X)} = P⁽p,⁾ • P⁽p2⁾ . Demak, o‘zaro tub bo‘lgan ikkita natural son uchun p( pp) = P( p ) • P( p2 ) ekanligi kelib chiqdi.
Shuningdek, juft-jufti bilan o‘zaro tub bo‘lgan к ta natural son uchun
p⁽pi • p2 • .. • p.⁾ = p⁽p,⁾• P⁽p2⁾ • .. • p⁽p.⁾
ekanligini hosil qilish mumkin ([3] ga qarang).
Yuqorida berilganlardan foydalanib,
p⁽p? • p2² •... • pk⁾ = p⁽p^⁾ • p⁽p2²⁾ •... • p⁽p?⁾ =
( p? — p^^l) • ( p2² — p?1 •... • (X — p?^—1)

tenglikni hosil qilamiz, bundan

p(a) = a

\—
pi

'l —^
^pk

formulaga ega bo‘lamiz.

11. 
    teorema (Eyler teoremasi). O‘zaro tub bo‘lgan a va m(m > 1) sonlari uchun quyidagi munosabat o‘rinli:
    

a ^p(m) = i (_mod m). (38.2)
Isbot. Aytaylik, p(m) = c bo‘lsin. m dan kichik va m bilan o‘zaro tub bo‘lgan turli r, Г, . ., Г sonlari uchun ar_x, ar₂,..., ar_c sonlarni qaraymiz. U holda
ar = Sj (mod m), ar₂ = s₂ (mod m), ..., ar_c = s_c (mod m).
Bu yerda Sj, s₂,..., s_c lar o‘zaro teng bo‘lmagan sonlar. Haqiqatan, s_f = s. bo‘lsa, u holda