Oʻzbekiston respublikasi oliy ta’lim, fan va innovatsiyalar vazirligi

OʻZBEKISTON RESPUBLIKASI OLIY TA’LIM, FAN VA INNOVATSIYALAR VAZIRLIGI
MIRZO ULUGʻBEK NOMIDAGI OʻZBEKISTON MILLIY UNIVERSITETINING JIZZAX FILIALI
Amaliy matematika fakulteti
Kompyuter ilmlari va dasturlashtirish kafedrasi
Axborot tizimlari va texnologiyalari yo’nalishi
21-21-guruh talabasi Bo’riboyev Diyorning
“Algoritmlar va berilganlar strukturasi” fanidan yozgan

MUSTAQIL ISHI

Mavzu: Eyler funksiyasi va uni hisoblash algoritmi
Tekshirdi: Tojiyev Ma’ruf
Jizzax 2023

Variant	Mustaqil ish 1	Mustaqil ish 2	Mustaqil ish 3	Mustaqil ish 4
2	2	8	4	27

2-variant. 1-Mustaqil ish
Mavzu: Eyler funksiyasi va uni hisoblash algoritmi
Reja:

1. 
   Eyler funksiyasi haqida batafsil ma’lumot
   
2. 
   Eyler funksiyasining algoritmi
   
3. 
   Eyler funksiyasining dasturiy ta’minoti
   

Eyler funksiyasi. Eyler teoremasi.
Eyler funksiyasi 𝜙(𝑛) (ba’zida 𝜑(𝑛) yoki 𝑝ℎ𝑖(𝑛) orqali ifodalanadi) – bu 1 dan n gacha bo’lgan sonlar oralig’ida n bilan o’zaro tub sonlar sonidir. Boshqacha qilib aytadigan bo’lsak, bu [1;n] oralig’idagi n bilan EKUBi birga teng bo’ladigan sonlar sonidir.
Chegirmalarning keltirilgan sistemasidagi elementlar sonini aniqlash uchun Eyler funksiyasi deb ataluvchi 𝜑(𝑚) funksiyadan foydalaniladi.
𝑚 − ixtiyoriy musbat son bo`lsin, 𝑚 dan katta bo`lmagan va 𝑚 bilan o`zaro tub bo`lgan bo`lgan musbat sonlar sonini 𝜑(𝑚) bilan belgilanadi.
TA`RIF. Agar quyidagi ikkita shart bajarilsa, 𝜑(𝑚) sonli funksiya Eyler funksiyasi deyiladi: 1. 𝜑(1) = 1
2. 𝜑(𝑚) funksiya 𝑚 dan kichik va 𝑚 bilan o`zaro tub bolgan musbat sonlar soni.
1-TEOREMA. 𝜑(𝑚) ta (𝑚 > 1) sonlarning ixtiyoriy to`plami, ya`ni 𝑚 bilan o`zaro tub va 𝑚 modul` bo`yicha ixtiyoriy ikkitasi taqqoslanmaydigan sonlar to`plami 𝑚 modul` bo`yicha chegirmalarning keltirilgan sistemasi bo`ladi.
2-TEOREMA. a butun son 𝑚 bilan o`zaro tub va 𝑏<sub>1</sub>, 𝑏<sub>2</sub>, … , 𝑏<sub>𝜑(𝑚)</sub> − 𝑚 modul` bo`yicha chegirmalarning keltirilgan sistemasi bo`lsin, u holda
𝑎𝑏1, 𝑎𝑏2, … , 𝑎𝑏𝜑(𝑚)
ham 𝑚 modul bo`yicha chegirmalarning keltirilgan sistemasi bo`ladi.
ISBOTI. 1-teoremaga ko`ra,
𝑎𝑏1, 𝑎𝑏2, … , 𝑎𝑏𝜑(𝑚)
sonlar to`plamidagi ixtiyoriy ikkitasi 𝑚 modul` bo`yicha taqqoslanmasligini ko`rsatish kifoya. Haqiqatan, agar
𝑎𝑏<sub>𝑖</sub> = 𝑎𝑏<sub>𝑘</sub>(𝑚𝑜𝑑𝑚) 𝑖 ≠ 𝑘
bo`lsa, (𝑎, 𝑚) = 1 bo`lgani uchun
𝑏<sub>𝑖</sub> = 𝑏<sub>𝑘</sub>(𝑚𝑜𝑑𝑚)
bo`ladi. Bunday bo`lishi mumkin emas, chunki 𝑏<sub>𝑖</sub>, 𝑏<sub>𝑘</sub> lar 𝑚 modul` bo`yicha chegirmalarning turli sinflariga tegishli.
TA`RIF. Natural sonlar to`plamida aniqlangan 𝑓 funksiya uchun (𝑚, 𝑛) =
1 bo`lganda
𝑓(𝑚 ∙ 𝑛) = 𝑓(𝑚) ∙ 𝑓(𝑛)
tenglik bajarilsa, u holda 𝑓 funksiya multiplikativ funksiya deyiladi.