Eyler funksiyasi. Eyler va Ferma teoremalari

Eyler funksiyasi. Eyler va Ferma teoremalari Reja: 1. Modul bo'yicha chegirmalarning tula sistemasi. 2. Modul bo'yicha chegirmalarning keltirilgan sistemasi. 3. Eyler funksiyasi ta'rifi. 4. Eyler funksiyasining xossalari. 5. Eyler funksiyasini hisoblash formulalari. 6. Eyler teoremasi. 7. Ferma teoremasi. 8. Misol. Barcha butun sonlarni ml natural songa bo'lganda 0, 1, 2, , m-1 koldiklar hosil bo'ladi. Bunday xar bir koldikka butun sonlarning biror sinfi mos keladi. ta'rif. m ga bulinganda r ga teng bir xil koldik beradigan butun sonlar to'plami m modul bo'yicha chegirmalar sinflari deyiladi va uni kabi belgilanadi. Masalan, m=3 bulsa, =, -6, -3, 0, 3, 6, , =, -5, -2, 1, 4, 7, , =, -4, -1, 2, 5, 8, chegirmalar sinflari bo'ladi. ta'rif. Chegirmalar sinfining ixtiyoriy elementi shu sinfning chegirmasi deyiladi. ta'rif. m modul bo'yicha tuzilgan xar bir chegirmalar sinfidan erkinlik bilan bittadan element olib tuzilgan to'plamga m modul bo'yicha chegirmalarning tula sistemasi deyiladi. Masalan, m=3 bo'lganda 0, 1, 2; -1, -5, 6; 0, -4,4; sistemalar 3 modul bo'yicha chegirmalarning tula sistemasi bo'ladi. Sinfning bitta chegirmasi m modul bilan o'zaro tub bulsa, u holda bu sinfning barcha elementlari xam m modul bilan o'zaro tub bo'ladi. ta'rif. m modul bilan o'zaro tub bo'lgan barcha chegirmalar sinfidan erkinlik bilan bittadan chegirma olib tuzilgan to'plam chegirmalarning m modul bo'yicha keltirilgan sistemasi deyiladi. Masalan, m=3 bulsa, u holda 1, 2; -1, 7; -5, 8, sistemalar Z modul bo'yicha chegirmalarning, keltirilgan sistemasi bo'ladi. m modul bo'yicha chegirmalarning keltirilgan sistemasidagi elementlar sonini aniqlash uchun Eyler funksiyasi deb ataluvchi (m) funksiyadan foydalanamiz. ta'rif. Agar quyidagi ikkita shart bajarilsa, u holda (m) sonli funksiya Eyler funksiyasi deyiladi: 1. (1)=1. 2. (m) funksiya m dan kichik va m bilan o'zaro tub bo'lgan natural sonlar soni. Misol. m=10 bulsa, u holda (10)=4 bo'ladi, yani 1 dan 10 gacha va 10 bilan o'zaro tub bo'lgan natural sonlar soni 4 ta bo'ladi. ta'rif. Natural sonlar to'plamida aniqlangan f funksiya uchun (m; n)=1 bo'lganda f(mn)=f(m)f(n) tenglik bajarilsa, u holda f funksiyaga multiplikativ funksiya deyiladi. Teorema. Eyler funksiyasi multiplikativ funksiya bo'ladi. Bu teoremaning isboti [1, 2] da keltirilgan. (m) Eyler funksiyasini hisoblash formulalari kuyidagilardan iborat: m=p tub son bulsa, u holda (p)=r-1 bo'ladi. m= r (r-tub son, -natural son) bulsa, u holda (p)= =p-1(p-1) bo'ladi. m= bulsa, u holda bo'ladi. Bu formulalarning hosil bo'lishi [1,2] da berilgan. Misol. (540) ni toping. Xakikatdan, (540)=(22335)=540(1-) (1-)(1--)=144, (540)=144 bo'ladi. Teorema (Eyler teoremasi). Agar (a; m)=1 bulsa, u holda a(m)1(modm) taqqoslama urinli bo'ladi. ...