Документ

Всего документов: 5844
Число пользователей: 15251

Информация о документе

Цена	40000UZS
Размер	342.1KB
Покупки	2
Дата загрузки	02 Февраль 2024
Расширение	docx
Категория	Информатика и ИТ

Multiplikativ funksiyalar.

ax 1≡b1(mod m1) (4)
taqqoslamaga ega bo‘lamiz. Haqiqatan x=a son (4) ni qanoatlantirsa, u holda
αα ≡b(mod m)
taqqoslamaga ega bo‘lamiz, uning ikkala qismini va modulni d ga
bo‘lib,
α1α=b1(mod m1) hosil bo‘ladi. Demak, a (4) ni qanoatlantiradi.
Aksincha,
x= β butun son a1β=b1(mod m1) taqqoslamani qanoatlantirsin. Bu
taqqoslamaning ikkala qismini va modulni d ga ko‘paytirib,
aβ ≡b(mod m)
taqqoslamani hosil qilamiz. Demak,
β(1) ni qanoatlantiradi.
Shunday qilib (1) va (4) teng kuchli ekan. (4) dagi (a,
m1 )=1, shuning uchun
bu taqqoslama
x= x0(mod m) V x= x0+mt ,(t∈t)
yagona yechimga ega, bu yerda
x0 m modul bo‘yicha manfiymas eng kichik
chegirma bo‘lsin yoki
... x0−2m1,x0−m1,x0,x0+m,x0+2m1,....,x0+(d−1)m1,x0+dm1,x0+(d+1)m1,....
(5)
(5) dagi har bir chegirma (4) ni qanoatlantiradi va demak, (1) ni ham
qanoatlantiradi.
m1= m
d modul bo‘yicha (5) dagi hamma sonlar bitta sinfga tegishli,
lekin
m=m1d modul bo‘yicha ular turli sinflarga tegishli bo‘ladi, bu sinflarning
chegirmalari esa
(6)
x0,x0+m1,x0+2m1,....,x0+(d−2)m1,x0+(d−1)m1
Demak, (1) m modul bo‘yicha d ta turli yechimga ega bo‘ladi:
x≡ x0(mod m),x≡x0+m1(mod m)
x≡ x0+2m1(mod m),.....,x≡x0+(d−1)m1(mod m)
bu yerda
x0 - (3) taqqoslamaning yechimi bo‘lgan sinfning eng kichik manfiymas
chegirmasi.
Misol. 3x
¿ 6(mod 9)
(3,6)=3
Λ 6 ⋮ 3=2 3 ta yechimga ega.
x=2(mod 3)
Demak, berilgan taqqoslamaning barcha yechimlari
15

pa dan kichik manfiy bo‘lmagan va pa bilan o‘zaro tub bo‘lmagan sonlar
soni
pa−1 ga teng, chunki faqat kp, 0≤k<pa−1 sonlargina pa bilan o‘zaro tub
bo‘lmaydi. Shuning uchun
pa dan kichik va pa bilan o‘zaro tub sonlar soni
pa− pa−1
ta bo‘ladi.
ϕ(pa)= pa(1− 1
p)
m= p1
a1⋅p2
a2¿....⋅pn
an
va ϕ multiplikativ bo‘lgani uchun
ϕ(m )=ϕ(p1
a1)⋅ϕ(p2
a2)⋅....⋅ϕ(pn
an)= p1
a1(1−1
p1
)⋅p2
a2(1−1
p2
).....pn
an(1−1
pn
)= p1
a1¿p2
a2¿....⋅pn
an¿
⋅(1−1
p1
)(1−1
p2
)⋅.....⋅(1−1
pn
)=m(1−1
p1
)(1−1
p2
)⋅.....⋅(1−1
pn
)
Eyler teoremasi. Agar a butun son m bilan o‘zaro tub bo‘lsa, u holda
aϕ(m)=1(mod m)
(1)
bo‘ladi.
Isboti.
a1,a2,......,aϕ(m) (2) – m modul bo‘yicha chegirmalarning keltirilgan
sistemasi bo‘lsin, u holda 2-teoremaga ko‘ra,
aa1,aa 2,......,aa ϕ(m)
(3)
ham m modul bo‘yicha chegirmalarning keltirilgan sistemasi bo‘ladi. Shuning
uchun (3) sonlar ko‘paytmasi (2) sonlar ko‘paytmasi bilan m modul bo‘yicha
taqqoslanadi, ya‘ni
aϕ(m)a1⋅a2⋅......⋅aϕ(m)≡a1⋅a2⋅......⋅aϕ(m)(mod m)
a1⋅a2⋅......⋅aϕ(m)
ko‘paytma m bilan o‘zaro tub, shuning uchun taqqoslamaning
xossasiga ko‘ra,
a1a2......aϕ(m) ga bo‘linishi mumkin, demak,
aϕ(m)≡1(mod m)
bo‘ladi.
Ferma teoremasi. Agar a son p tub songa bo‘linmasa, u holda
ap−1≡1(mod p)
taqqoslama o‘rinli bo‘ladi.
12

$ 1   1   1  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 1  p 2 ko‘rinishda bo‘lsin, bu yerda p 1 , p 2 tub sonlar. Umumiylikka ziyon yetkazmagan holda p 1 < p 2 deb olib, {1, 2,..., p 1 p 2  1}\{ p 1 , 2 p 1 ,3 p 1 ,...,( p 2  1) p 1 , p 2 , 2 p 2 ,3 p 2 ,...,( p 1  1) p 2 } sonlarni qaraymiz. Bu sonlarning barchasi bo‘ladi, ya’ni 28$

Misol. ;  p n
bo’lganda bo’ladi va bo’lib, bu esa
Eyler funksiyasi umumlashtirilgan Eyler funksiyasining xususiy holi
ekanligini ko’rsatadi.
1 – masala. dan kichik va bilan o’zaro tub bo’lgan barcha natural sonlar
yig’indisi tengligini ko’rsating.
Yechilishi. bo’lsin. uchun holda bo’ladi (buni isbotlang).
lar dan kichik va bilan o’zaro tub sonlar bo’sin. Bu ketma – ketlikda
ta element bo’lib, bo’lganda, bo’lib bo’ladi,
bunday juftliklar soni da va bo’ladi. Demak, dagi barcha sonlar
yig’indisi bo’ladi.
Misol. . 18 dan kichik va 18 bilan o’zaro tub
bo’lgan 1, 5, 7, 11, 13, 17 sonlarining yig’indisi .
Izoh. tub son bo’lganda bo’ladi.
2-masala. orqali dan kichik va bilan eng katta umumiy bo’luvchisi
ga teng bo’lgan sonlar soni belgilanadi. ekanligini isbotlang.
Yechilishi. bo’lib bo’lsin.
Demak, har qanday son uchun
9
               
   727236 2418129854321
72
 

d d
           
82,8133,1223248 1334
 
LL
             
.364,18,2155,133,122532540 2222
 LL
   1
1  p p p P     
 ppP  n 
 n L
m m
 m m T   2
1
  1 ,  m a   1 ,  a m a
) ( 1 , , , ...., , ,1 1 2 2 1 A m a m a m a a   
m m  m 
A ak
Aam
k    m a m a
kk   
A  m 2
1
) (A
 m m  2
1
     6 6 1 9 2 18 ; 18        m
  54 18 18 2
1     T
p m     
2
1
2
1     p p p p T
 nd n n
d
 





d n
n
d
n m    d n m  ,
  1 1 1 1 1 1 ;1 , ; , n m n m n d n m d m       n m  1 1 n m 

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 2
p 3

     
     
Isbot. Ravshanki, n ! ko‘paytmaning ko‘paytuvchilari orasida
 n

tasi p ga,  n

tasi p 2
ga va hakazo  n

tasi
22

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
1 , r
2 , ..., r
c
sonlari uchun
ar
1 , ar
2 , ..., ar
c
sonlarni
ar
1  s
1 (mod m ),
ar
2
 s
2 (mod m ),
ar
c
 s
c (mod m ).
Bu yerda
s
1 , s
2 , ..., 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
30

bu yerda (p
q)2=1. (5) tenglikka asosan, p va q larning kamida bittasi 4m+1
shakldagi son bo‘lsa,
(−1)
p−1
2⋅q−1
2=1 bo‘lib, (p
q)=(q
p) hosil bo‘ladi.
Agar p va q larning har biri 4m+3 shakldagi tub son bo‘lsa, u holda (-1) ning
darajasi toq son bo‘lib,
(p
q)=−(q
p) bo‘ladi.
Misol.
x2≡426 (mod 491 ) taqqoslama yechimga egami?
Bu savolga javob berish uchun
(426
491 ) Lejandr simvolini tuzamiz.
426 =2⋅3⋅71
shakldagi son bo‘lgani uchun 4-xossaga asosan quyidagicha yozamiz:
(426
491 )≡( 2
491 )⋅( 3
491 )⋅(71
491 ).
1.
( 2
491 )≡−1, chunki 491
¿ 3(mod8).
2.
( 3
491 )
¿ -
(491
3 )≡−(2
3)≡−(−1)=1, chunki 491
¿ 3(mod4) va 3 ¿ 3(mod4)
hamda 3
¿ 3(mod8).
3.
(
71
491
)≡−(
491
71
)≡−(
65
71
)≡−(
5
71
)⋅(
13
71
)≡−(
71
5
)⋅(
71
13
)≡−(
1
5
)⋅(
6
13
)≡−(
2
13
)⋅(
3
13
)≡¿¿¿−(−1)(
13
3
)≡1⋅(
1
3
)≡1, chunki 491 ≡3(mod4 ), 71≡3(mod4 ), 491 ≡65(mod71 ), 5≡1(mod4 ),
13≡5(mod8 ).
Demak,
(426
491 )=(−1)⋅1⋅1=−1, (426
491 )≡−1, bo‘lgani uchun berilgan taqqoslama
yechimga ega emas.
[ 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
21

Kurs ishining maqsadi: Algebra va sonlar nazariyasi fani davomida Butun
sonlarda bolinish nazaryasi . Sonlarning umumiy bo‘luvchisi va karralisi
tog’risida olgan bilim va ko’nikmalarni mustahkamlash. Butun sonlarni bo‘linish
belgilari nazariyasini chuqurroq o’rganish.
Kurs ishining ob’ekti: Oliy va o’rta ta’lim muassalarida chiziqli algebra fanini
o’qitish jarayoni.
Kurs ishining predmeti: Algebra va sonlar nazariyasi o’qitish metodlari va
vositalari.
Kurs ishining vazifalari:
1. Butun sonlarning umumiy bo‘luvchisi va karralisi
shakllantirish;
2. Tub sonlar. Arifmetikaning asosiy qonuni
3. Bo‘linish belgilari
6

9x¿ 5(mod 28)
9x
¿ 5-140(mod 28)
9x
¿ -135(mod 28)
x
¿ -15(mod 28)
x
¿ 13(mod 28)
Eyler teoremasidan foydalanish usuli. Ma‘lumki, (a,m)=1 bo‘lsa, u holda
aϕ(m)≡1(mod m)
taqqoslama o‘rinli edi. Shunga ko‘ra, x=aϕ(m)−1⋅b(mod m) bo‘ladi.
Misol.
3x≡7(mod 11 )
x≡3ϕ(11)−1⋅7(mod 11 ) ϕ(11 )= 10
x≡39⋅7(mod 11 )≡(33)3⋅7≡ 53⋅7≡ 4⋅7≡ 28 ≡ 6(mod 11 )
Taqqoslamaning moduli yetarlicha katta bo‘lsa, quyidagi usul ancha qulaydir.
Uzluksiz kasrlardan foydalanish usuli.
ax ≡b(mod m)
taqqoslama berilgan bo‘lib, (a,m)=1
Λ a>0 bo‘lsin.
m
a kasrni uzluksiz kasrlarga
yoyib, uning munosib kasrlarini
Pk
Qk (k=1,n) kabi belgilaymiz, bunda
Pn=m Λ Q n=a
bo‘ladi, u holda
PnQn−1−Pn−1Qn=(−1)n
tenglikni mQ n−1−aP n−1=(−1)n
ko‘rinishda yozish mumkin, yoki
aP n−1≡(−1)n+mQ n−1 dan aP n−1≡(−1)n−1(mod m) (2)
ni
(−1)n−1⋅b ga ko‘paytirib, (−1)n−1⋅b⋅aP n−1≡b(mod m) (3). (1) va (3) ni solishtirib
x≡(−1)n−1b⋅Pn−1(mod m)
ni hosil qilamiz. Bu yerda
Pn−1 son
m
a kasrning (n-1) – munosib kasrning suratidan
iborat.
(1) taqqoslama yagona yechimga ega bo‘lgani uchun (3) yechim (1) ning yagona
yechimi bo‘ladi.
Misol. 68x
¿ 164(mod 212)
(68,164)=4, 212/4
17

XULOSA
Kurs ishi oliy ta’lim tizimining barcha bosqichlarida chiziqli algebra fanini
o‘qitishda muhim aham i yatga ega bo‘lgan tekislikdagi to‘g‘ri chiziq tenglamalarini
o‘rganish , o‘rgatish masalasiga bag‘ishlangan.
Kurs ishi kirish, asosiy qism, xulosa va foydalanilgan adabiyotlar iborat.
Kirish qismida yurtimizda ta’lim sohasida olib borilayotgan islohotlar, ularning
samarali natijasi va mavzu bo‘yicha boshlang‘ich ma’lumotlar berildi.
Xulosa qilib aytganda men bu kurs ishini yozganimdan asosiy maqsad butun
sonlar bo'linish nazariyasi mavzusidan men a, b butun sonlarning har birini
boladigan songa shu sonlarning umumiy boluvchisi deyilishini, EKUB asli
nimaligini, uni belgilanishini, tub sonlarni, a, b butun sonlarning EKUBi
algoritimidagi oxirgi r
B qoldiqqa tengligi bildim, isbotini korib o'rgandim. Tub
sonlarni teoremalarini, isbotlarini o'rgandim va yana butun sonlar bolinish
nazaryasiga oid tariflarni ko'rib chiqdim.
32

Multiplikativ funksiyalar.
Reja:
Kirish
Asosiy qism
1.1. Multiplikativ funksiyalar.
1.2. Eyler funktsiyasi.
1.3. Eyler funktsiyasining multiplikativligi.
1.4. Lejandr simvoli va uning xossalari.
Xulosa
Adabiyotlar
4

F.I.O Baho Imzo
Rasmiylashtirish
Himoya
Savollar:
O’rtacha baho
3

“ Sayyoramizning ertangi kuni, farovonligi farzandlarimiz
qanday inson bo‘lib kamolga yetishi bilan bog‘liq. Bizning
asosiy vazifamiz – yoshlarning o‘z salohiyatini namoyon
qilishi uchun zarur sharoitlar yaratishdan iborat.”.
SH.M.Mirziyoyev
KIRISH
Mamlakatimizda qabul qilingan Kadrlar tayyorlash milliy dasturiningo’ziga
xos jihati shundan iboratki, u yaxlit samarali tizimga asos bo’lib, shaxs, davlatva
jamiyat manfaatlariga xizmat qiladi. Uzluksiz ta’lim, ilm- fan va ishlab chiqarishbu
yaxlit jarayonning uzviy tarkibiy qismlaridir. Mazkur dastur
mamlakatimiziqtisodiyoti va hayotining barcha jabhalari uchun yuqori malakali,
raqobatdoshkadrlar tayyorlash, ta’lim, ilm-fan va ishlab chiqarishning
samaraliintegratsiyalashuvini ta’minlash, yoshlarni milliy va umuminsoniy
qadriyatlar asosidama’naviy-axloqiy tarbiyalash, shuningdek, kadrlar tayyorlash
borasida o’zaromanfaatli xalqaro hamkorlikni rivojlantirishga qaratilgan yaxlit
o’quv-ilmiy ishlabchiqarish kompleksi sifatida ta’lim tizimini bosqichma- bosqich
takomillashtirishvazifasini muvaffaqiyatli hal etishga xizmat qilmoqda. Yetuk va
barkamol avlodnitarbiyalashda oilaning o’rnini kuchaytirish, oila institutining
ta’lim va tarbiyamuassasalari bilan amaliy hamkorligini mustahkamlash bo’yicha
ham salmoqli ishlarbajarildi. Bu haqda gapirganda, oila, mahalla va ta’lim
muassasasi o’rtasidagihamkorlikni, uning samarasini kuchaytirish bo’yicha
kompleks chora-tadbirlar ishlabchiqilib, amalga oshirilayotganini qayd etish
o’rinlidir.
Mamlakatimizning istiqlol yo’lidagi birinchi qadamlaridan, buyuk
ma’naviyatimizni tiklash va yanada yuksaltirish, milliy ta’lim-tarbiya
tiziminitakomillashtirish, uning milliy zaminini mustahkamlash, zamon talablari
bilanuyg’unlashtirish asosida jahon andozalari va ko’nikmalari darajasiga
chiqarishmaqsadiga katta ahamiyat berib kelinmoqda. Bu jarayonda oxirgi yillarda
qilinganishlar haqida qisqacha to’xtalib o’tamiz.
5

Misol. .
So’ngra

chunki songa ga bo’ladigan va tengsizlikni qanoatlantiradigan
barcha butun sonlar soniga teng.
Misol. m=20; (4,5)=1.
(0,4,8,12,16 sonlari soni.)
Misol. ;
Haqiqatdan ham, (4, 8, 16, 28, 32, 44, 52, 56 sonlari soni);
(4, 8, 12, 16, 24, 28, 32, 36, 44, 48, 52, 156 sonlari soni);
(12, 24, 36, 48 sonlari soni);
8 =12 – 4 (*) tenglikdan foydalanib quyidagi teoremani isbotlaymiz.
Misol.
Misol.
Misol.
Misol. Hech qanday natural uchun qiymati 14, 26, 34, 38, 50, 62, 68,
74, 86, 90, 94, 98 ga teng bo’la olmasligi isbotlangan.
2) bo’lganda bo’ladi.
Misol. , , , .
Misol. uchun Gauss ayniyatini tekshiring, ;
;
8)4( ) ( ) 1( m m  
4 ) 12( ) 121(   
)5( , )1 (
1 1 m
m m  
1m
m
1m m k 0
k
  .5 4
20 1/4   
.5 ,4        2 1 m m 3, p 5; 4 3 60 m
.1 )5,4( ,5/3 4/3  
).5/4 3( )5/4( )5 3/4(     
8 )5 3/4(   
12 )5/4(  
4 )5/4 3(   
    . 16 3
1 1 2
1 1 3 2 3 2 4844 
 
  
 
      
      16 4 2 2 5 4 3 60        
       
525,45,20525 22

n  n 
  1 ,2  n        n n n     2 2
  2 6 3       4 10 5        6 14 7       6 18 9   
72n 2 3 3 2 72   n
     12 1 2 1 3 72     

bo‘lsa, (a,m)=1 bo‘lgani uchun bi= bk(mod m)
bo‘ladi. Bunday bo‘lishi mumkin emas, chunki
bi,bk lar m modul’ bo‘yicha
chegirmalarning turli sinflariga tegishli.
Ta‘rif. Natural sonlar to‘plamida aniqlangan f funksiya uchun (m,n)=1
bo‘lganda
f(m⋅n)= f(m )⋅f(n)
tenglik bajarilsa, u holda f funksiya multiplikativ funksiya deyiladi.
Teorema. Eyler funksiyasi multiplikativ funksiyadir.
Isboti. a va b o‘zaro tub bo‘lgan musbat butun sonlar bo‘lsin.
a⋅b dan kichik
bo‘lgan barcha manfiymas sonlar to‘plami M ni qaraylik. M dagi har bir sonni,
qoldiqli bo‘lish teoremasiga asosan, yagona tarzda
b⋅q+r (r∈{0,1, .....,b-1 }, q ∈{0 ,1,2, ....,a-1 })
ko‘rinishda ifodalash mumkin.
bq+r son a bilan o‘zaro tub bo‘lishi uchun (b,r)=1 bo‘lishi zarur va yetarli. Bunday
r sonlar soni
ϕ(b) ta bo‘ladi. r1 - shunday sonlarning biri bo‘lsin. U holda
r1, b+r1, 2b +r1,....., b (a-1 )+r1
sonlar ketma-ketligi a modul bo‘yicha chegirmalarning to‘la sistemasini tashkil
etadi. Shuning uchun, bu sonlar orasida a bilan o‘zaro tub bo‘lgan sonlar
ϕ(a) ta
bo‘ladi. Shunday qilib, har bir
r1 songa (b bilan o‘zaro tub bo‘lgan) bq+ r1
ko‘rinishdagi a bilan o‘zaro tub sonlar va demak, ab bilan ham o‘zaro tub bo‘lgan
ϕ(a)
ta son mos keladi. Shuning uchun, ab bilan o‘zaro tub bo‘lgan sonlar soni
ϕ(a)⋅ϕ(b)
, ya‘ni ϕ(ab )= ϕ(a)⋅ϕ(b) bo‘ladi.
Teorema. Agar
m= p1
a1⋅p2
a2¿....⋅pn
an bo‘lsa, u holda
ϕ(m)=m(1− 1
p1
)(1− 1
p2
)⋅....⋅(1− 1
pn
)
bo‘ladi.
Isboti.
ϕ(m) funksiya multiplikativ bo‘lgani uchun, bu funksiyani ϕ(pk
ak)
uchun hisoblashni bilish kifoya.
11

1-xossa. a≡a1(mod p)=> (a
p)=(
a1
p). (2)
Haqiqatan, bitta sinfning elementlari berilgan modul bo‘yicha yo kvadratik
chegirma, yoki kvadratik chegirmamas bo‘ladi. Bunga asosan, (1) ning to‘g‘riligi
kelib chiqadi. Bu xossadan foydalanib, har qanday
k∈Z uchun quyidagini yoza
olamiz:
(a
p)=(
kp +a1
p ), (
kp +a1
p )=(
a1
p) bo‘lgani uchun (a
p)=(
a1
p) bo‘ladi.
2-xossa.
(1
p)=1 .
Haqiqatan,
x2≡1(mod p) taqqoslama doimo yechimga ega bo‘lib, x≡±1(mod p)
uning yechimidir.
3-xossa.
(−1
p)=(−1)
p−1
2. (1) taqqoslamaga asosan quyidagini yoza olamiz:
(−1
p )=(−1)
p−1
2 (mod p)
(3). Lekin (-1
p) va (−1)
p−1
2 larning qiymati
±1 dan farqli
emas. Shu bilan bir vaqtda p tub son bo‘lgani uchun 1 va -1 lar shu modul bo‘yicha
taqqoslanuvchi bo‘la olmaydi. Demak,
(-1
p) va (−1)
p−1
2 lar bir vatda 1 ga yoki -1 ga
teng bo‘ladi.
4-xossa.
(a⋅b
p )=(a
p)⋅(b
p).
Isboti. (1) taqqoslamaga asosan quyidagini yozish mumkin:
(a⋅b
p )≡(a⋅b)
p−1
2 ≡(a)
p−1
2⋅(b)
p−1
2 ≡(a
p)⋅(b
p)(mod p)
yoki (a⋅b
p )≡(a
p)⋅(b
p)(mod p).
(a)
p−1
2⋅(b)
p−1
2 ≡(a
p)⋅(b
p)(mod p)
taqqoslamaning ikki qismi a va b lar p modul
bo‘yicha kvadratik chegirma yoki kvadratik chegirmamas bo‘lsa, 1 ga, a va b
larning biri p modul bo‘yicha kvadratik chegirma, ikkinchisi esa kvadratik
chegirmamas bo‘lsa, -1 ga teng. Shuning uchun
(a⋅b
p )≡(a
p)⋅(b
p) tenglikni yoza
olamiz. Bu xossadan quyidagi natijalar kelib chiqadi:
19

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 4
 3 2
 5)  (4  1)  (2  1)  (1  1) = 30;
4 2
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.

27

Agar a son (1) taqqoslamani qanoatlantirsa u holda m modul bo‘yicha a
bilan taqqoslanuvchi ∀b son ham bu taqqoslamani qanoatlantiradi, bunday 2 ta
yechim bitta deb qaraladi.
Misol. 5x
¿ 3(mod 6), 0,1,2,3,4,5 x ¿ 3(mod 6) x0 =3+6t, ∀ t∈Z x0 =9,15,…
sonlar ham bu taqqoslamani qanoatlantiradi.
Teorema. Agar (a,m)=1 bo‘lsa, u holda ax
¿ b(mod m) (1) taqqoslama
yagona yechimga ega bo‘ladi.
Isboti. m modul bo‘yicha chegirmalarning to‘la sistemasi
x1,x2,...,xm
bo‘lsin, u holda ax1,ax2,...,ax m (2)
ham chegirmalarning to‘la sistemasi bo‘lishi ma‘lum. Agar (1) da x o‘rniga ketma
ket (2) dagi chegirmalarni qo‘yib ko‘rsak, u holda bu taqqoslamaning chap qismi
chegirmalarning to‘la sistemasidagi barcha qiymatlardan o‘tadi. Bu esa bitta va
faqat bitta
xi son uchun axi sonning b songa tegishli bo‘lgan chegirma sinfiga
tegishli bo‘lishini bildiradi, bunda
ax i≡b(mod m)
bo‘ladi. Demak, agar (a,m)=1 bo‘lsa, (1) taqqoslama yagona bo‘lgan x=
xi (mod m)
yoki x=
xi +mt, t ∈Z yechimga ega bo‘ladi.
Teorema. Agar (a,m)=d>1 va b son d ga bo‘linmasa, u holda ax
¿ b(mod m)
taqqoslama yechimga ega bo‘lmaydi.
Isboti. Faraz qilaylik, ax
¿ b(mod m) taqqoslama uchun m modul bo‘yicha x1
sinf yechim bo‘lsin va
x1∈¯x1 bo‘lsin, u holda ax 1≡b(mod m) yoki ax 1−b=mt , t ∈Z
bo‘ladi.
a⋮dΛm⋮d dan b⋮d kelib chiqadi. Bunday bo‘lishi mumkin emas, shartga
ko‘ra b son d ga bo‘linmaydi. Demak, teorema isbotlandi.
Teorema. Agar (a,m)=d>1 va b son d ga bo‘linsa, u holda
ax ≡b(mod m)
taqqoslama d ta turli yechimlarga ega bo‘ladi. Bu yechim
m
d modul bo‘yicha bitta
sinfni tashkil qiladi.
Isboti. Shartga ko‘ra a,b va m sonlar d ga bo‘linadi.
a=a1d, b =b1d Λ m =m1d
(1) ni d ga bo‘lib, unga teng kuchli bo‘lgan
14

 ( a
1 a
2 ) =  ( a
1 )  ( a
2 ).
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:
a.
ixtiyoriy multiplikativ funksiya uchun  (1) = 1;
b) 
1 ( a )
va 
2 ( a )
mutiplikativ funksiyalar bo‘lsin, u holda

0 ( a ) = 
1 ( a ) 
2 ( a )
ham multiplikativ funksiya bo‘ladi.
Isbot. a) aytaylik,
 ( a
0 )  0
bo‘lsin, u holda mutiplikativ
funksiyaning ikkinchi shartiga asosan
 ( a
0 ) =  (1  a
0 ) =  (1)  ( a
0 ),
ya’ni,  (1) = 1.
b) ravshanki, 
0 (1) = 
1 (1) 
2 (1) = 1.
sonlar uchun:
Bundan tashqari,
( a
1 , a
2 ) = 1

0 ( a
1 a
2 ) = 
1 ( a
1 a
2 ) 
2 ( a
1 a
2 ) = 
1 ( a
1 ) 
1 ( a
2 ) 
2 ( a
1 ) 
2 ( a
2 ) 
= 
1 ( a
1 ) 
2 ( a
1 ) 
1 ( a
2 ) 
2 ( a
2 ) = 
0 ( a
1 ) 
0 ( a
2 ).

Bizga
 ( a )
multiplikativ funksiya va a sonining kanonik
24

FOYDALANILGAN ADABIYOTLAR RO‘YXATI
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.James J.T. Elementry number thory in nine chapters. 1999. – 417 p.
4. Kuttler K. Elementary linear algebra. 2012. – 433 p.
5. Strang G. Introduction to Linear algebra. 2016. – 584 p.
6. Бухштаб А.А. Теория чисел. 1966. – 386 с.
7.Веретенников Б.М., Михалева М.М., Алгебра и теория чисел. Учебное
пособие. 2014. – 52 с.
8.Виноградов И.М. Основы теории чисел. 1948. – 178 c.
9. Гельфанд И.М. Лекции по линейной алгебре. 1998. – 320 с. 10. Кострикин
А.И. Введение в алгебру. Часть I. Основы алгебры. 2000. – 272 с.
11. Кострикин А.И. Введение в алгебру. Часть II. Линейная алгебра. 2000. –
368 с.
12. Куликов Л.Я. Алгебра и теория чисел. Москва. 1979. –559 с. 13. Курош
А.Г. Курс высшей алгебры. 2008. – 432 c.
14. Проскуряков И.Л. Сборник задач по линейной алгебре. «Наука», 2010. –
480 с.
15. Фаддеев Д.К. Лекции по алгебре. 2007. – 416 с.
16. Фаддеев Д.К., Соминский И.С. Задачи по высшей алгебре, Санкт-
Петербург, 1999. – 304 с.
17. Хожиев Ж.Х. Файнлейб А.С. Алгебра ва сонлар назарияси курси,
Тошкент, «Ўзбекистон», 2001 й.
33

17x¿ 41(mod 53), (17,53)=1
P k−1= 25 n = 3, n-1 = 2
x0≡ (− 1)2⋅25 ⋅41 (mod 53 )≡ 18 (mod 53 )
x≡ 18 ,71 ,124 ,177 (mod 212 )
Lejandr simvoli va uning xossalari.
Ushbu
x2≡ a(mod p) , (a;p)=-1 taqqoslamaning moduli yetarlicha katta
bo‘lganda Eyler kriteriysidan foydalanish unchalik qulay emas. Bunday hollarda
Lejandr simvoli deb ataluvchi va
(a
p) kabi ataluvchi simvoldan foydalaniladi.
Ta‘rif. Quyidagi shartlarni qanoatlantiruvchi
(a
p) simvol Lejandr simvoli
deyiladi:
(
a
p
)= ¿{1, agar a son p toq tub modul bo'yicha kvadratik chegirma bo' ¿¿¿¿
(a
p)
simvol a sondan p bo‘yicha tuzilgan Lejandr simvoli deb ataladi, bu yerda a
Lejandr simvolining surati, p esa Lejandr simvolining maxraji deyiladi.
Misol.
(1
p)= 1 chunki Eyler krityerasiga asosan, 7
19−1
2 ≡1(mod 19 ) bo‘lgani
uchun 7 son 19 modul bo‘yicha kvadratik chegirmadir. 5 son 17 modul bo‘yicha
kvadratik chegirmamas bo‘lganligidan
(5
17 )=−1 bo‘ladi.
Ma‘lumki,
a
p−1
2≡1(mod p), a
p−1
2≡−1(mod p) ekanligiga qarab, a kvadratik
chegirma yoki kvadratik chegirmamas bo‘ladi. Demak, Lejandr simvoli va Eyler
kriteriylarga asosan, quyidagini yoza olamiz:
(a
p)≡a
p−1
2 (mod p)
. (1)
Endi Lejandr simvolining quyidagi ba‘zi bir xossalarini ko‘rib chiqamiz:
18

1-natija. (a2
p)≡1, (a⋅b2
p )≡(a
p).
2-natija. Juft sondagi kvadratik chegirmalar yoki kvadratik chegirmamaslar
ko‘paytmasi doimo kvadratik chegirma bo‘ladi. Toq sondagi kvadratik
chegirmamaslar ko‘paytmasi yana kvadratik chegirmamas bo‘ladi.
5-xossa.
(2
p)≡(−1)
p2−1
8 .
Biz bu xossani isbot qilib o‘tirmasdan undan amaliy mashg‘ulotlarda
foydalanishning ba‘zi bir tomonlarini ko‘rsatib o‘tamiz.
a)
p≡8m±1 shakldagi tub son bo‘lsin. U holda
p2−1
8 = (8m±1)2−1
8 =8m2±2m≡ 0(mod 2)
Bo‘lgani uchun
(2
p)≡1.
b)
p≡8m±3 shakldagi tub son bo‘lsa,
p2−1
8 = (8m± 3)2−1
8 =8m2±6m+1≡1(mod 2)
bo‘ladi. Demak,
p≡8m±3 shakldagi tub son bo‘lsa, 2 son p modul bo‘yicha
kvadratik chegirmamas bo‘ladi, ya‘ni
(2
p)≡−1.
6-xossa. O‘zarolik qonuni. Agar p va q lar har xil toq tub son bo‘lsa,
(p
q)⋅(q
p)≡(−1)
p−1
2⋅q−1
2
(4)
tenglik o‘rinli bo‘ladi.
Bu xossani ham isbot qilmasdan uning amaliy mashg‘ulotlarda qo‘llanishini
ko‘rsatamiz. Buning uchun (4) ning har ikkala qismini
(p
q) ga ko‘paytiamiz:
(q
p)≡(−1)
p−1
2⋅q−1
2(p
q),
(5)
20

Isboti. A son p tub songa bo‘linmasa, u holda (a,p)=1 bo‘ladi. Bundan, Eyler
teormasiga ko‘ra, m=p va ϕ(p)= p−1 ekanligidan
aϕ(p)≡1(mod p)
ap−1≡1(mod p)
bo‘ladi, yoki (a,p)=1 bo‘lgani uchun
ap≡ a(mod p)
Misol 1. Eyler funksiyasini hisoblang:
ϕ(18⋅42 )
Yechish: 18 bilan o‘zaro tub bo‘lgan musbat sonlar: 1,5,7,11,13,17. Demak, 18
sonlar:1,5,11,13,17,19,23,25,29,31,37,41. Demak, 42 bilan o‘zaro tub bo‘lgan
musbat sonlar soni 12 ta,
ϕ(a⋅b)= ϕ(a)⋅ϕ(b) ga asosan
ϕ(18 ⋅42 )= ϕ(18 )⋅ϕ(42 )=6⋅12 =72 ,
ya‘ni ϕ(18⋅42 ) =72 yechim hosil bo‘ladi.
Misol 2. 7x
¿ 10(mod 4) taqqoslamani Eyler teoremasi yordamida yeching.
Yechish: ax
¿ b(mod m) taqqoslama (a,m)=1 bo‘lsa, u holda uning yechimi x ¿
b⋅aϕ(m)−1(mod m)
formula yordamida topiladi. Haqiqatan ham Eyler teoremasiga
ko‘ra
aϕ(m)−1≡1(mod m). Bundan aϕ(m)b≡b(mod m) va a⋅aϕ(m)−1b≡b(mod m) larni hosil
qilsak, x
¿ba ϕ(m)−1(mod m) kelib chiqadi. 7x ¿ 10(mod 4) dan a=7, b=10, m=4 yechim
x≡10 ⋅7ϕ(4)−1(mod 4)
ni topish uchun ϕ(4) ni aniqlaymiz. 4=22 ekanligidan
ϕ(4)= 4⋅(1− 1
2)=2
kelib chiqadi. Demak, x≡10 ⋅72−1(mod 4). Agar 10 ¿ 2(mod4), 7 ¿
3(mod4), 6
¿ 2(mod4) taqqoslamalardan foydalansak x ¿
10 ⋅72−1(mod 4)= 2⋅3=6≡ 2(mod 4)
ya‘ni x ¿ 2(mod4) yechimni hosil qilamiz.
Birinchi darajali taqqoslamalar va ularni yechish usullari.
1-Ta‘rif. Ushbu ax
¿ b(mod m) (1) ko‘rinishdagi taqqoslama bir noma‘lumli
birinchi darajali taqqoslama deyiladi. (bu yerda a va b – butun sonlar, m – natural
son)
2-Ta‘rif. Agar (1) taqqoslamada
x= x0 bo‘lganda ax 0≡b(mod m) taqqoslama
to‘g‘ri bo‘lsa, u holda
x0 son taqqoslamani qanoatlantiradi deyiladi.
3-Ta‘rif. m modul bo‘yicha taqqoslamaning yechimlar soni deb, bu
taqqoslamaning m modul bo‘yicha chegirmalarning to‘liq sistemadagi yechimlar
soniga aytiladi.
13

O‘ZBEKISTON RESPUBLIKASI OLIY TA’LIM, FAN VA
INNOVATSIYALAR VAZIRLIGI
TOSHKENT AMALIY FANLAR UNIVERSITETI
“MATEMATIKA VA KOMPUTER INJINIRING”
KAFEDRASI
“ DASTURLASH ” fanidan
Mavzu:
______________________________________________________________
______________________________________________________________
______________________________________________________________
Bajardi: ___________________ guruhi talabasi
___________ __________________________
Q abul q ildi: ___________ __________________________
Toshkent – 20__ y.KURS ISHI

p
1 p
2
bilan o‘zaro tub
 ( p
1 p
2 ) = p
1 p
2  p
1  p
2  1 = ( p
1  1)( p
2  1) =  ( p
1 )  ( p
2 ) .
Demak, o‘zaro tub bo‘lgan ikkita natural son uchun
 ( p
1 p
2 ) =  ( p
1 )  ( p
2 )
ekanligi kelib chiqdi.
Induksiyadan foydalangan holda juft-jufti bilan o‘zaro tub bo‘lgan k ta natural son
uchun
 ( p
1  p
2  ...  p
k )   ( p
1 )  ( p
2 )  ...  ( 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
 
1  
1  
1 
( 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:
29

TOSHKENT AMALIY FANLAR UNIVERSITETI
“MATEMATIKA VA KOMPUTER INJINIRING”
Kafedrasi
“ DASTURLASH ” fanidan
kurs ishi bo`yicha berilgan
texnik topshiriq
Variant ___
Mavzu : _____________________________________________________
_____________________________________________________________
_____________________________________________________________
1. Kurs ishini topshirish muddati: _______________________________
2. Kurs ishini bajarish uchun boshlang’ich ma’lumotlar: Adabiyotlar,
nazariy ma’lumotlar, grafik muharrirlar. _______________________________
3. Tushuntiruv yozuvi tarkibi: Kirish, mavzu bo’yicha nazariy ma’lumotlar,
amaliy qismda berilgan topshiriq varianti bo`yicha grafik ishlanmalar, xulosa,
foydalanilgan adabiyotlar ro’yxati, ilova. _______________________________
4. Grafik materiallar: tasvir, chizma va boshqalar.
5. Topshiriq berilgan sana: _____________________________________
6. Bajarish uchun qabul qilib oldi: _____________________________
________________ fakulteti, ________________________ guruh talabasi
7. Rahbar: __________________________________________________
Ekspert guruhi baholari
2 «Tasdi q layman»
“ Matematika va komputer injiniring ”
kafedrasi mudiri __________ dots .
_____________ ___ _______ 20 ___ y.

son mos keladi. Bunday sonlar miqdori ga teng.
Jumladan, bo’ladi.
Misol. ni toping.
Haqiqatdan ham, 24 dan kichik va 24 bilan eng katta umumiy bo’luvchisi 3 ga
teng bo’lgan sonlar 3, 9, 15, 21 bo’lib, ular 4 ta.
Eyler funksiyasi. Eyler va Ferma teoremalari.
Chegirmalarning keltirilgan sistemasidagi elementlar sonini aniqlash uchun
Eyler funksiyasi deb ataluvchi ϕ(m) funksiyadan foydalaniladi.
m- ixtiyoriy musbat son bo‘lsin, m dan katta bo‘lmagan va m bilan o‘zaro
tub bo‘lgan musbat sonlar sonini
ϕ(m) bilan belgilanadi.
TA‘RIF. Agar quyidagi ikkita shart bajarilsa,
ϕ(m) sonlifunksiya Eyler
funksiyasi deyiladi:
1.
ϕ(1)=1
2.
ϕ(m) funksiya m dan kichik va m bilan o‘zaro tub bo‘lganmusbat sonlar
soni.
1-TEOREMA.
ϕ(m) ta (m>1) sonlarning ixtiyoriy to‘plami, ya‘ni m bilan
o‘zaro tub va m modul’ bo‘yicha chegirmalarning keltirilgan sistemasi bo‘ladi.
2-TEOREMA. a butun son m bilan o‘zaro tub va
b1,b2,.....,bϕ(m) - m modul’
bo‘yicha chegirmalarning keltirilgan sistemasi bo‘lsin, u holda
ab 1,ab 2,...,ab ϕ(m)
ham m modul bo‘yicha chegirmalarning keltirilgan sistemasi bo‘ladi.
Isboti. 1-teoremaga ko‘ra,
ab 1,ab 2,...,ab ϕ(m)
sonlar to‘plamidagi ixtiyoriy ikkitasi m modul’ bo‘yicha taqqoslanmasligini
ko‘rsatish kifoya. Haqiqatan, agar
ab i= ab k(mod m) i≠ k
10
  1 ,1 1  n m    n d
n n dd 
 
  1
   n n n
d 1 1 
 
 
  243    4 8 3
24 24
3  
 
 

(1  
1 )  (1  
2 )  ...  (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  
2 )  ...  (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
 1 p 
2  1
 1 p 
k  1
 1
1
 2
 ... 
k
.
p
1  1
p
2  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
 1 p 
2  1
 1 p 
k  1
 1
yig‘indisini, o‘ng tomoni esa
1
 2
 ...  k
ifodani
p
1  1
p
2  1
p
k  1
beradi. 
26

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  
1  
1 , 0  
2  
2 , ..., 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
25

r
i = r
j . Bu esa r
k
sonlarining turli ekanligiga zid.
Shuningdek,
s
1 , s
2 , ..., s
c
sonlarning barchasi m bilan o‘zaro tub
ekanligini ko‘rish qiyin emas. Bundan esa
tenglik kelib chiqadi.
r
1  r
2  ...  r
c
= s
1  s
2  ...  s
c
ar
i
 s
i (mod m )
taqqoslamalarni hadma-had ko‘paytirsak,
a c
r  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
31

p k
ga bo‘linadi.
p
p 2
p k
     
     
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.
 
3 

 
9 
 
 27 

Demak, 40! soni
3 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
1 va a
2
musbat butun sonlar uchun
23

x=2(mod 9), x=2+3(mod 9 )≡ 5(mod 9 )
x≡2+3⋅2(mod m )≡ 8(mod 9 )bo‘ladi.
Teorema. Agar (a,m)=1 bo‘lsa, u holda
ax ≡b(mod m) taqqoslamaning
yechimi
x≡ ba ϕ(m)−1(mod m) bo’ladi.
Isboti. (a,m)=1 bo‘lgani uchun Eyler teoremasiga ko‘ra
aϕ(m)≡1(mod m).
Bundan
aϕ(m)⋅b= b(mod m)
a⋅aϕ(m)−1⋅b=b(mod m)
(3)
Demak, (1)
Λ (3) ni solishtirsak, x=aϕ(m)−1⋅b(mod m) yechimi ekani ko‘rinadi.
Misol. 5x
¿3 (mod 6)
(5,6)=1 bo‘lgani uchun
x=3⋅5ϕ(6)−1(mod m)≡ 3⋅5(mod m)≡15 ≡ 3(mod m ).
Sinash usuli. Bu usulning mohiyati shundaki (1) taqqoslamadagi x o‘rniga m
modulga ko‘ra chegirmalarning to‘la sistemasidagi barcha chegimalar ketma-ket
qo‘yib chiqiladi. Ulardan qaysi biri (1) ni to‘g‘ri taqqoslamaga aylantirsa, o‘cha
chegirma qatnashgan sinf yechim hisoblanadi. Lekin koeffitsient yetarlicha katta
bo‘lganda bu usul qulay emas.
Koeffitsientlarni o‘zgartirish usuli. Taqqoslamalarning xossalaridan
foydalanib, (1) da noma‘lum oldidagi koeffitsientni a va b ni shunday o‘zgartirish
kerakki, natijada taqqoslamaning o‘ng tomonida hosil bo‘lgan son ax hadning
koeffitsientiga bo‘linsin.
Misol.1. 7x
¿ 5(mod 9)
7x
¿ 5+9(mod 9)
7x
¿ 14(mod 9)
x
¿ 2(mod 9)
2. 17x
¿ 25(mod 28)
17x+28x
¿ 25(mod 28)
45x
¿ 25(mod 28)
16

Multiplikativ funksiyalar.

Купить

Информация о документе

Продавец

Multiplikativ funksiyalar.