Taqqoslamalar va ularning xossalari

38 - §. Mutiplikativ funksiyalar. Eyler va Ferma teoremalari

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

egallaydigan funksiyalar hisoblanadi.
38.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.

38.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.

38.3-teorema. n!

quyidagi songa teng:

ko‘paytmada ^{p  n}

tub sonning darajasi

^ n ^ _ ^ n



^ _ ^ n
^  ...

p p² p³
     
     

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

^{ n } tasi p ga, ^{ n } tasi p² ga va hakazo ^{ n } tasi



p^k ga bo‘linadi.

p

_p2

_pk
     
     
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,



^{ 40 }  ^{ 40 }  ^{ 40 } = 13  4 1 = 18.
_ ₃ _{ } ₉ _ _{ 27} _

Demak, 40! soni
₃18
ga qoldiqsiz bo‘linadi.

Multiplikativ funksiyalar ham sonlar nazariyasida muhim o‘rin egallaydi.

38.4-ta’rif. Quyidagi shartlarni qanoatlantirsa
multiplikativ funksiya deyiladi:
 (a)
funksiya

1)  (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

 (a₁a₂ ) =  (a₁) (a₂ ).

Misol 38.3

bo‘ladi.
 (a) = a^s ,
s  funksiya mutiplikativ funksiya

Multiplikativ funksiyalarning ayrim xossalarini keltirib o‘tamiz.
38.5-xossa. Multiplikativ funksiyalar uchun quyidagi xossalar o‘rinli:

1. 
   ixtiyoriy multiplikativ funksiya uchun  (1) = 1;
   

b) ₁ (a)
va ₂ (a)
mutiplikativ funksiyalar bo‘lsin, u holda

₀ (a) = ₁ (a)₂ (a)
ham multiplikativ funksiya bo‘ladi.

Isbot. a) aytaylik,
 (a₀ )  0
bo‘lsin, u holda mutiplikativ

funksiyaning ikkinchi shartiga asosan

 (a₀ ) =  (1 a₀ ) =  (1)  (a₀ ),
ya’ni,  (1) = 1.

b) ravshanki, ₀ (1) = ₁ (1)₂ (1) = 1.
sonlar uchun:
Bundan tashqari,
(a₁, a₂ ) = 1

₀ (a₁a₂ ) = ₁ (a₁a₂ )₂ (a₁a₂ ) = ₁ (a₁ )₁(a₂ )₂ (a₁)₂ (a₂ ) 
= ₁ (a₁ )₂ (a₁ )₁ (a₂ )₂ (a₂ ) = ₀ (a₁)₀ (a₂ ).


Bizga
 (a)
multiplikativ funksiya va a sonining kanonik

1 2 k 

ko‘rinishi ^{a =
p1 p2 ... p}^k berilgan bo‘lsin.  (d ) orqali a soni-ning
d|a

barcha bo‘luvchilari bo‘yicha olingan yig‘indini belgilaymiz.

38.6-xossa.

_ (d ) = (1  ( p ) ...   ( p^1 )) ... (1  ( p ) ...   ( p^k )).
(38.1)

1 1 k k
d|a


Isbot. Xossani isbotlash uchun (38.1) tenglikning o‘ng tomonini ochib chiqamiz. U holda yig‘indi hadlari quyidagi ko‘rinishda bo‘ladi:
^{ ( p1 )  ( p2 ) ... ( pk ) =  ( p1  p2 ... pk )} ,
1 2 k 1 2 k

bu yerda
0  ₁  ₁, 0  ₂  ₂ , ..., 0  _k
 _k .

Ushbu
p^1  p^2 ... p^k
sonlar a sonining barcha bo‘luvchilarini

1 2 k
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.

38.7-natija.

a = p^1  p^2 ... p^k
sonining bo‘luvchilari soni

quyi-dagiga teng:
1 2 k

(1 ₁ )  (1 ₂ ) ... (1 _k ) .

Isbot. 38.6-xossani
 (a) = 1
multiplikativ funksiya uchun

qo‘llasak, (38.1) tenglikning chap tomoni a sonining bo‘luvchilari

sonini, o‘ng tomoni esa
(1 ₁ )  (1 ₂ ) ... (1 _k )
ifodani beradi.


38.8-natija. ^{a = p1  p2 ... pk}
sonining bo‘luvchilari

1 2 k
yig‘indisi quyidagiga teng:
_p₁1 _{1 p}₂ 1 _{1 p}_k 1 _1
¹  ² ... ^k .

p₁ 1
p₂ 1
p_k 1

Isbot. 38.6-xossani
 (a) = a
multiplikativ funksiya uchun

qo‘llasak, (38.1) tenglikning chap tomoni a sonining bo‘luvchilari
_p₁1 _{1 p}₂ 1 _{1 p}_k 1 _1

yig‘indisini, o‘ng tomoni esa
¹  ² ... ^k
ifodani

p₁ 1
p₂ 1
p_k 1

beradi. 

S(a)
a sonining bo‘luvchilari sonini  (a),
kabi belgilanadi.
bo‘luvchilari yig‘indisi esa

Misol 38.4. 720 sonining bo‘luvchilari soni va bo‘luvchilari yig‘indisini toping.
 (720) =  (2⁴  3²  5)  (4 1)  (2 1)  (11) = 30;
4 2 ₂41 _{1 3}21 _{1 5}11 _1

S(720) = S(2
 3  5)   
2 1 3 1 5 1
= 2418.

38.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 belgilanadi.

Misol 38.5.

(a)
kabi

(1) = 1,
(2) = 1,
(3) = 2,
(4) = 2,
(5) = 4,
(6) = 2.

Eyler funksiyasining qiymatini berilgan a sonining

a = p^1  p^2 ... p^k
kanonik yoyilmasidan foydalanib, hisoblaydigan

1 2 k

formula keltiramiz.



 ₁   ₁   ₁ 

38.10-tasdiq.

(a) = a _1  _{p }  _1  _{p } ... _1 _{p }

 1   2   k 
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 1.
Endi a biror tub sonning darajasi ko‘rinishida bo‘lsin ya’ni

a = p^ .
U holda
{1, 2, 3, ..., p^


1}\{ p, 2 p, 3 p, ...,( p^1 1)  p}

sonlarning barchasi p^ bilan o‘zaro tub, ya’ni ( p^ )  p^
_{ p} 1_.

Aytaylik,
a = p₁  p₂
ko‘rinishda bo‘lsin, bu yerda
p₁, p₂
tub

sonlar. Umumiylikka ziyon yetkazmagan holda
p₁ < p₂
deb olib,

{1, 2,..., p₁ p₂ 1}\{p₁, 2 p₁,3 p₁,...,( p₂ 1) p₁, p₂ , 2 p₂ ,3 p₂ ,...,( p₁ 1) p₂}

sonlarni qaraymiz. Bu sonlarning barchasi bo‘ladi, ya’ni
p₁ p₂
bilan o‘zaro tub

( p₁ p₂ ) = p₁ p₂  p₁  p₂ 1 = ( p₁ 1)( p₂ 1) = ( p₁) ( p₂ ) .

Demak, o‘zaro tub bo‘lgan ikkita natural son uchun

( p₁ p₂ ) = ( p₁ ) ( p₂ )
ekanligi kelib chiqdi.

Induksiyadan foydalangan holda juft-jufti bilan o‘zaro tub bo‘lgan k ta natural son uchun
( p₁  p₂ ... p_k )  ( p₁) ( p₂ ) ...( p_k )
ekanligini osongina hosil qilish mumkin. Yuqorida berilganlardan foydalanib,

( p^1  p^2 ... p^k ) = ( p^1 ) ( p^2 ) ...( p^k ) 
1 2 k 1 2 k

( p^1  p^11 )  ( p^2
 p^{2 1} ) ... ( p^k
_{ p}_k 1 ₎

1 1 2 2 k k

tenglikni hosil qilamiz, ya’ni

_  ₁   ₁   ₁ 

(a) = a _1  _{p }  _1  _{p } ... _1  _{p }.

 1   2   k 

38.11-teorema (Eyler teoremasi). O‘zaro tub bo‘lgan a va
m(m > 1) sonlari uchun quyidagi munosabat o‘rinli:

_a (m)
 1(mod m).
(38.2)

Isbot. Aytaylik, (m)  c bo‘lsin. m dan kichik va m bilan o‘zaro

tub bo‘lgan turli qaraymiz. U holda
r₁, r₂ , ..., r_c
sonlari uchun
ar₁, ar₂ , ..., ar_c
sonlarni

ar₁  s₁(mod m),
ar₂
 s₂ (mod m),
ar_c
 s_c (mod m).

Bu yerda
s₁, s₂ , ..., s_c
lar o‘zaro teng bo‘lmagan sonlar.

Haqiqatan,
s_i  s _j
bo‘lsa, u holda

ekanligidan
ar_i
 s_i (mod m),
ar_j
 s_j (mod m)

ar_i  ar_j  (s_i  s_j )(mod m)  0(mod m)

kelib chiqadi. (a, m)  1
bo‘lganligi uchun
r_i  r_j
 0(mod m),
ya’ni

r_i = r_j . ^{Bu esa r}_k
sonlarining turli ekanligiga zid.

Shuningdek,
s₁, s₂ , ..., s_c
sonlarning barchasi m bilan o‘zaro tub

ekanligini ko‘rish qiyin emas. Bundan esa
tenglik kelib chiqadi.
r₁  r₂ ... r_c
= s₁  s₂ ... s_c

ar_i
 s_i (mod m)
taqqoslamalarni hadma-had ko‘paytirsak,

a^cr  r ... r  s  s ... s
(mod m)

1 2 c 1 2 c

munosabatga ega bo‘lamiz. Demak,
a^c  1(mod m). 

Agar Eyler teoremasida m soni o‘rniga biror p tub olinsa, u holda (38.2) tenglik quyidagi ko‘rinishga keladi:
a^p1  1(mod p).
Ushbu teglikning ikkala tomonini a ga ko‘paytirsak,
a^p  a(mod p)

tenglikka ega bo‘lamiz. Bu tenglik Fermaning kichik teoremasi

deyiladi.

39 - §. Birinchi darajali taqqoslamalar.

Qoldiqlar haqidagi Xitoy teoremasi

Biz 37-mavzuda
_m = _0, 1, ..., m 1_

to‘plamni aniqlab, bu

to‘plamda qo‘shish va ko‘paytirish amallarini kiritgan edik.

Ushbu mavzuda
to‘plamda berilgan





a  x = b

bir noma’lumli birinchi darajali tenglamani yechish masalasi bilan shug‘ullanamiz.

Ma’lumki,
da keltrilgan bir noma’lumli tenglama
ax  b(mod m)

bir noma’lumli birinchi darajali taqqoslamaga teng kuchlidir, bu yerda

a,b  ^{x noma’lum butun son.}
Demak, dagi bir noma’lumli birinchi darajali tenglamani
yechish masalasi bir noma’lumli birinchi darajali taqqoslamani yechish masalasiga ekvivalent.
Bir noma’lumli birinchi darajali taqqoslamalarni quyidagi uchta holatga ajratish mumkin:

a) (a, m) = 1;
b) (a, m) = d > 0
c) (a, m) = d > 0

bo‘lib, b soni d ga bo‘linmaydi; bo‘lib, b soni d ga bo‘linadi.

39.1-tasdiq.

ax  b(mod m)
bir noma’lumli birinchi darajali

taqqoslama tenglama uchun quyidagilar o‘rinli:

a) (a, m)  1
yagonadir;
bo‘lsa, taqqoslamaning yechimi mavjud va

b) (a, m)  d > 0
emas;
c) (a, m)  d > 0
yechimga ega.
bo‘lib, b soni d ga bo‘linmasa, yechim mavjud bo‘lib, b soni d ga bo‘linsa, taqqoslama d ta

Isbot. Dastlab, (a, m)  1 bo‘lgan holni qaraymiz. 37.13-xossaga

asosan ^{a  x}
ko‘rinishidagi elementlardan tashkil topgan to‘plam

bilan ustma-ust tushib, ^x ning turli qiymatlarida ^{a  x}
ham turli

qiymatlarni qabul qiladi. Demak, ixtiyoriy b  uchun yagona ^x
topiladi, ya’ni taqqoslama yagona yechimga ega.

Aytaylik, (a, m)  d
bo‘lsin, ya’ni
a = a₁d,
m = m₁d . 37.10-

xossaga asosan
ax  b(mod m)
yechimga ega bo‘lishi uchun b sonining

ham d ga bo‘linishi zarur va yetarli, ya’ni
b = b₁d .

Taqqoslamaning xar bir hadi va modulini d ga bo‘lib,
a₁x  b₁ (mod m₁ )

tenglamani hosil qilamiz. yagona yechimga ega.
(a₁, m₁ )  1
bo‘lganligi uchun bu tenglama

Aytaylik,
x₁ soni tenglama yechimining eng kichik nomanfiy

elementi bo‘lsin. U holda
x = x₁  m₁,


x₁  2m₁,


x₁  (d 1)m₁

sonlari ham berilgan tenglamaning yechimi bo‘ladi. Ya’ni, ushbu holda tenglama d ta yechimga ega. 

Bir noma’lumli tenglamalarni yechishning bir qancha usullari mavjud.

Tanlash usuli.

to‘plam chekli bo‘lganligi uchun



a  x = b

tenglamaga dagi elementlarini birma-bir olib kelish qo‘yish
mumkin. Agar ularning birortasida tenglama ayniyatga aylansa, demak bu element tenglamaning yechimi bo‘ladi.

Masalan,



to‘plamda ^{5  x = 4}
tenglamani qaraymiz.

No‘malumning o‘rniga quyidagilarni hosil qilamiz:
ning elemetlarini olib borib qo‘ysak,

5 1 = 5, ^{5  2 = 4} , ^{5  3 = 3}, ^{5  4 = 2} , ^{5  5 = 1}.

Demak, ^{5  x = 4}
tenglamaning yechimi



x₀ = 2
bo‘ladi.

Sonlarning EKUBi orqali yechish usuli. Aytaylik, ^{a  x = b}
tenglamada (a, m)  1 bo‘lsin. U holda u,v  sonlari topilib,

bo‘ladi. Bu tenglikdan
au  mv = 1





^{a  u =1} ekanligini hosil qilamiz.

a  x = b



tenglamaning ikkala tomonini ^u ga ko‘paytirsak,
u  a  x = u  b, (u  a)x = u  b, 1 x = u  b,
x = u  b.

Demak,


x = u  b
berilgan tenglamaning yechimi bo‘ladi.

Misol 39.1. ^{7  x  9}
tenglamani
da yeching. Bu yerda
a  7,

b  9 va
m  10
bo‘lib, (7,10) = 1. Yevklid algoritmidan foydalanib

7  3 10  (2)  1 ekanligini hosil qilamiz, ya’ni Demak,
u  3,
v  2.

x = 3  9 = 3  9 = 27 = 7

tenglamaning yechimi bo‘ladi.

Eyler teoremasidan foydalanib yechish usuli. Ma’lumki,

(a, m)  1
bo‘lsa,
_a (m)
 1(mod m)



bo‘ladi. Endi a  x  b
tengla-

maning ikkala tomonini
_a (m)1
ga ko‘paytirsak,

_a (m)1 _{ a  x  a} (m)1 <sub> b,




a</sub> (m) _{ x  a} (m)1 _{ b,}




1 x  a^(m)1  b ,



_{x  a} (m)1 _{ b.}

hosil bo‘ladi. Topilgan ^x element tenglamaning yechimi bo‘ladi.

Misol 39.2. ^{3  x  7}
tenglamani
da yeching. Ushbu

tenglamada (3,11)  1
bo‘lganligi uchun yuqorida keltirilgan usuldan

foydalanamiz. (11)  10
ekanligi uchun

bo‘ladi.

x  3⁹  7  27³  7  5³  7  125  7  4  7  28  6

FOYDALANILGAN ADABIYOTLAR RO‘YHATI

1. 
   Dixon M.R., Kurdachenko L.A., Subbotin I.Ya., Algeba and Number theory. 2010. – 523 p.
   
2. 
   Everest G., Ward T. An Introduction to Number Theory. 2006. – 297 p.
   
3. 
   Kuttler K. Elementary linear algebra. 2012. – 433 p.
   
4. 
   Strang G. Introduction to Linear algebra. 2016. – 584 p.
   
5. 
   Бухштаб А.А. Теория чисел. 1966. – 386 с.
   
6. 
   Веретенников Б.М., Михалева М.М., Алгебра и теория чисел. Учебное пособие. 2014. – 52 с.
   
7. 
   Виноградов И.М. Основы теории чисел. 1948. – 178 c.
   
8. 
   Гельфанд И.М. Лекции по линейной алгебре. 1998. – 320 с.
   
9. 
   Кострикин А.И. Введение в алгебру. Часть I. Основы алгебры. 2000. – 272 с.
   
10. 
    Кострикин А.И. Введение в алгебру. Часть II. Линейная алгебра. 2000. – 368 с.
    
11. 
    Куликов Л.Я. Алгебра и теория чисел. Москва. 1979. –559 с.
    
12. 
    Курош А.Г. Курс высшей алгебры. 2008. – 432 c.
    
13. 
    Проскуряков И.Л. Сборник задач по линейной алгебре.
    

«Наука», 2010. – 480 с.

14. 
    Фаддеев Д.К. Лекции по алгебре. 2007. – 416 с.
    
15. 
    Фаддеев Д.К., Соминский И.С. Задачи по высшей алгебре, Санкт-Петербург, 1999. – 304 с.
    
16. 
    Хожиев Ж.Х. Файнлейб А.С. Алгебра ва сонлар назарияси курси, Тошкент, «Ўзбекистон», 2001 й.