Termiz davlat pedagogika instituti matematika va informatika fakulteti

TERMIZ DAVLAT PEDAGOGIKA INSTITUTI
MATEMATIKA VA INFORMATIKA FAKULTETI
MATEMATIKA VA INFORMATIKA YO’NALISHI
2-BOSQICH SIRTQI 21-01-GURUH TALABASI
ZIYOQULOV SARVARNING
ALGEBRA VA SONLAR NAZARIYASI FANIDAN TAYYORLAGAN
MUSTAQIL ISHI

EYLER FUNKSIYASI. EYLER FUNKSIYASINING MULTIPLIKATIVLIGI. EYLER TEOREMASINI HISOBLASH FORMULASI. EYLER TEOREMASI. FERMA TEOREMASI

Eyler teoremasi. va shartlarda

taqqoslama bajariladi.
Isboti.Agar son keltirilgan sistemani tashkil etuvchi manfiy bo’lmagan eng kichik chegirmalarga teng qiymatlarni qabul qilsa , ya’ni
,
bo’lsa , u holda sonlarning dan iborat manfiy bo’lmagan eng kichik chegirmalari ham shu sistemani (lekin , umuman aytganda , boshqa tartibda) tashkil etadi.
Ushbu
, , ….,
taqqoslamalarni hadlab ko’paytirsak ,
hosil bo’ladi, ikkala tomonni ko’paytmaga qisqartirib

taqqoslamani hosil qilamiz .
Ferma teoremasi. - tub son bo’lib , son songa bo’linmasa
(1)
taqqoslama bajariladi.
Isboti. Bu teorema Eyler teoremasining tub qiymatiga mos keluvchi xususiy holidir.(1) tenglikni ikkala tomonini ga ko’paytirib

taqqoslamani hosil qilamiz .
Bu taqqoslama istalgan butun sonlar uchun to’g’ridir , chunki u ga bo’linuvchi lar uchun ham o’rinlidir. .
Bir noma’lumli taqqoslamalar.
Ushbu mavzuda asosiy maqsadimiz
, (1) taqqoslamalarni o’rganishdan iborat.
Agar son ga bo’linmasa , taqqoslamaning darajasi deyiladi.
Taqqoslamani yechish , bu ning uni (taqqoslamani) qanoatlantiruvchi topish demakdir. ning bir xil qiymatlari bilan qanoatlantiriluvchi ikki taqqoslamaga teng kuchli taqqoslamalar deyiladi. Agar (1) taqqoslamani son qanoatlantirsa , u vaqtda ushbu taqqoslamani bilan modul bo’yicha taqqoslanuvchi , ya’ni shartga bo’ysunuvchi har qanday son ham qanoatlantiradi. Shunday sonlarning barchasidan tuzilgan sinf bitta yechim hisoblanadi. Bu holda , (1) taqqoslamani modul bo’yicha to’la sistemasining nechta chegirmasi qanoatlantirsa , (1) taqqoslama shuncha yechimga ega bo’ladi.
Misol.

Taqqoslamani modul bo’yicha chegirmalarning to’la sistemasidan va sonlar qanoatlantiradi. Shu sababli berilgan taqqoslama ikkita va yechimga ega.
Birinchi darajali taqqoslamalar
Umumiy ko’rinishda berilgan birinchi darajali taqqoslamani ozod hadini o’ng tomonga o’tkazib , ko’rinishga keltirish mumkin. Quyida biz bo’lsin deb olamiz. taqqoslama yechimlarining soni to’la sistemadagi uni qatnashtiruvchi chegirmalarning soniga teng . Lekin , son modul bo’yicha to’la sistemaning chegirmalariga teng qiymatlarni qabul qilganda , ham shu modul bo’yicha chegirmalarga teng qiymatlarni qabul qiladi. Demak , ning to’la sistemasidan olingan faqat bitta qiymatida son son bilan taqqoslanadi. Shunday qilib , bo’lganda (1) taqqoslama bitta yechimga ega.
Endi bo’lsin. Bu holda (1) taqqoslama yechimga ega bo’lishi uchun , sonning ga bo’linishi shart, aks holda (1) taqqoslama ning hech qanday qiymatida (albatta butun qiymat tushuniladi ) bajarilmaydi. Shuning uchun son ga bo’linadi deb faraz qilib , , , tengliklarni yozamiz. Bu holda (1) taqqoslamani ga qisqartirib, taqqoslamani hosil qilamiz. Bu yerda bo’lib , hosil bo’lgan so’ngi taqqoslama modul bo’yicha bitta yechimga ega bo’ladi. Bu yechimning modul bo’yicha manfiy bo’lmagan eng kichik chegirmasi bo’lsin , u holda shu yechimni tashkil etuvchi barcha sonlar
(2) ko’rinishda ifodalanadi. Lekin (2) sonlar modul bo’yicha bittagina emas , balki ko’proq yechimlarni tashkil etadi , ya’ni modul bo’yicha dan iborat manfiy bo’lmagan eng kichik chegirmalar qatorida (2) sonlardan nechta topilsa shuncha yechim bo’ladi , ularning soni esa (2) sonlardan ko’rinishdagi ta sonlardan iborat bo’ladi , demak , (1) taqqoslama ta yechimga ega .
Ushbu ko’rilgan bu ikki holni yakunlab quyidagi teoremaga kelamiz.
Teorema . bo’lsin . Agar son ga bo’linmasa , u holda taqqoslama bajarilmaydi, ya’ni bu holda taqqoslamayechimga ega emas , son ga bo’linadigan bo’lsa , u holda taqqoslama ta yechimga ega bo’ladi.
Endi (1) taqqoslamani yechish usulini ko’raylik. Uzluksiz kasrlar nazariyasiga asoslangan usulni qaraymiz.
Bunda bo’lgan holni qaraymiz. Ikkinchi hol ham shunga keladi.
nisbatni uzluksiz kasrga yoyaylik.

Bundan oxirgi ikki
,
munosib kasrni ko’zdan kechirsak , uzluksiz kasrning xossalariga asosan, quyidagilarga ega bo’lamiz:
,
,
.
Shunday qilib.

taqqoslamaning yechimi

bo`ladi.Bunda ni topish kifoya.
Misol. taqqoslamani yeching.
Bunda ,Shu sababli taqqoslama bitta yechimga ega.

	0	1	2	3	4	5
		1	3	6	4	3
	1	1	4	25	104	337

Demak,bu holda ,u holda berilgan taqqoslamaning yechimi

ko’rinishda bo’ladi.
Shunday qilib,javob
Chegirmalarning keltirilgan sistemasidagi elementlar sonini aniqlash uchun Eyler funksiyasi deb ataluvchi funksiyadan foydalaniladi.
m- ixtiyoriy musbat son bo‘lsin, m dan katta bo‘lmagan va m bilan o‘zaro tub bo‘lgan musbat sonlar sonini bilan belgilanadi.
TA‘RIF. Agar quyidagi ikkita shart bajarilsa, sonlifunksiya Eyler funksiyasi deyiladi:
1.
2. funksiya m dan kichik va m bilan o‘zaro tub bo‘lganmusbat sonlar soni.
1-TEOREMA. 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 - m modul’ bo‘yicha chegirmalarning keltirilgan sistemasi bo‘lsin, u holda
ham m modul bo‘yicha chegirmalarning keltirilgan sistemasi bo‘ladi.
Isboti. 1-teoremaga ko‘ra,
sonlar to‘plamidagi ixtiyoriy ikkitasi m modul’ bo‘yicha taqqoslanmasligini ko‘rsatish kifoya. Haqiqatan, agar
bo‘lsa, (a,m)=1 bo‘lgani uchun
bo‘ladi. Bunday bo‘lishi mumkin emas, chunki lar m modul’ bo‘yicha chegirmalarning turli sinflariga tegishli.
Ta‘rif. Natural sonlar to‘plamida aniqlangan f funksiya uchun (m,n)=1 bo‘lganda
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. dan kichik bo‘lgan barcha manfiymas sonlar to‘plami M ni qaraylik. M dagi har bir sonni, qoldiqli bo‘lish teoremasiga asosan, yagona tarzda
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 ta bo‘ladi. - shunday sonlarning biri bo‘lsin. U holda
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 ta bo‘ladi. Shunday qilib, har bir songa (b bilan o‘zaro tub bo‘lgan) bq+ ko‘rinishdagi a bilan o‘zaro tub sonlar va demak, ab bilan ham o‘zaro tub bo‘lgan ta son mos keladi. Shuning uchun, ab bilan o‘zaro tub bo‘lgan sonlar soni , ya‘ni bo‘ladi.
Teorema. Agar bo‘lsa, u holda
bo‘ladi.
Isboti. funksiya multiplikativ bo‘lgani uchun, bu funksiyani uchun hisoblashni bilish kifoya.
dan kichik manfiy bo‘lmagan va bilan o‘zaro tub bo‘lmagan sonlar soni ga teng, chunki faqat kp, sonlargina bilan o‘zaro tub bo‘lmaydi. Shuning uchun dan kichik va bilan o‘zaro tub sonlar soni
ta bo‘ladi.
va multiplikativ bo‘lgani uchun
Eyler teoremasi. Agar a butun son m bilan o‘zaro tub bo‘lsa, u holda
(1)
bo‘ladi.
Isboti. (2) – m modul bo‘yicha chegirmalarning keltirilgan sistemasi bo‘lsin, u holda 2-teoremaga ko‘ra,
(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
ko‘paytma m bilan o‘zaro tub, shuning uchun taqqoslamaning xossasiga ko‘ra, ga bo‘linishi mumkin, demak,
bo‘ladi.
Ferma teoremasi. Agar a son p tub songa bo‘linmasa, u holda
taqqoslama o‘rinli bo‘ladi.
Isboti. A son p tub songa bo‘linmasa, u holda (a,p)=1 bo‘ladi. Bundan, Eyler teormasiga ko‘ra, m=p va ekanligidan
bo‘ladi, yoki (a,p)=1 bo‘lgani uchun
Misol 1. Eyler funksiyasini hisoblang:
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, ga asosan ya‘ni =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 formula yordamida topiladi. Haqiqatan ham Eyler teoremasiga ko‘ra Bundan va larni hosil qilsak, x kelib chiqadi. 7x 10(mod 4) dan a=7, b=10, m=4 yechim ni topish uchun ni aniqlaymiz. ekanligidan kelib chiqadi. Demak, Agar 10 2(mod4), 7 3(mod4), 6 2(mod4) taqqoslamalardan foydalansak x 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 bo‘lganda taqqoslama to‘g‘ri bo‘lsa, u holda 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.
Agar a son (1) taqqoslamani qanoatlantirsa u holda m modul bo‘yicha a bilan taqqoslanuvchi 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) =3+6t, =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
bo‘lsin, u holda (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 son uchun sonning b songa tegishli bo‘lgan chegirma sinfiga tegishli bo‘lishini bildiradi, bunda
bo‘ladi. Demak, agar (a,m)=1 bo‘lsa, (1) taqqoslama yagona bo‘lgan x= (mod m) yoki x= +mt, t 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 sinf yechim bo‘lsin va bo‘lsin, u holda yoki
bo‘ladi. dan 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 taqqoslama d ta turli yechimlarga ega bo‘ladi. Bu yechim modul bo‘yicha bitta sinfni tashkil qiladi.
Isboti. Shartga ko‘ra a,b va m sonlar d ga bo‘linadi. (1) ni d ga bo‘lib, unga teng kuchli bo‘lgan
(4)
taqqoslamaga ega bo‘lamiz. Haqiqatan x=a son (4) ni qanoatlantirsa, u holda taqqoslamaga ega bo‘lamiz, uning ikkala qismini va modulni d ga bo‘lib, hosil bo‘ladi. Demak, a (4) ni qanoatlantiradi.
Aksincha, butun son taqqoslamani qanoatlantirsin. Bu taqqoslamaning ikkala qismini va modulni d ga ko‘paytirib, taqqoslamani hosil qilamiz. Demak, ni qanoatlantiradi.
Shunday qilib (1) va (4) teng kuchli ekan. (4) dagi (a, )=1, shuning uchun bu taqqoslama V
yagona yechimga ega, bu yerda m modul bo‘yicha manfiymas eng kichik chegirma bo‘lsin yoki
(5)
(5) dagi har bir chegirma (4) ni qanoatlantiradi va demak, (1) ni ham qanoatlantiradi. modul bo‘yicha (5) dagi hamma sonlar bitta sinfga tegishli, lekin modul bo‘yicha ular turli sinflarga tegishli bo‘ladi, bu sinflarning chegirmalari esa
(6)
Demak, (1) m modul bo‘yicha d ta turli yechimga ega bo‘ladi:
bu yerda - (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 bo‘ladi.
Teorema. Agar (a,m)=1 bo‘lsa, u holda taqqoslamaning yechimi bo’ladi.
Isboti. (a,m)=1 bo‘lgani uchun Eyler teoremasiga ko‘ra Bundan
(3)
Demak, (1) (3) ni solishtirsak, yechimi ekani ko‘rinadi.
Misol. 5x (mod 6)
(5,6)=1 bo‘lgani uchun
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)
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 taqqoslama o‘rinli edi. Shunga ko‘ra, bo‘ladi.

Misol.
Taqqoslamaning moduli yetarlicha katta bo‘lsa, quyidagi usul ancha qulaydir.
Uzluksiz kasrlardan foydalanish usuli.
taqqoslama berilgan bo‘lib, (a,m)=1 a>0 bo‘lsin. kasrni uzluksiz kasrlarga yoyib, uning munosib kasrlarini (k=1,n) kabi belgilaymiz, bunda bo‘ladi, u holda
tenglikni
ko‘rinishda yozish mumkin, yoki dan (2) ni ga ko‘paytirib, (3). (1) va (3) ni solishtirib
ni hosil qilamiz. Bu yerda son 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
17x 41(mod 53), (17,53)=1
Lejandr simvoli va uning xossalari.
Ushbu , (a;p)=-1 taqqoslamaning moduli yetarlicha katta bo‘lganda Eyler kriteriysidan foydalanish unchalik qulay emas. Bunday hollarda Lejandr simvoli deb ataluvchi va kabi ataluvchi simvoldan foydalaniladi.
Ta‘rif. Quyidagi shartlarni qanoatlantiruvchi simvol Lejandr simvoli deyiladi:
simvol a sondan p bo‘yicha tuzilgan Lejandr simvoli deb ataladi, bu yerda a Lejandr simvolining surati, p esa Lejandr simvolining maxraji deyiladi.
Misol. chunki Eyler krityerasiga asosan, bo‘lgani uchun 7 son 19 modul bo‘yicha kvadratik chegirmadir. 5 son 17 modul bo‘yicha kvadratik chegirmamas bo‘lganligidan bo‘ladi.
Ma‘lumki, ekanligiga qarab, a kvadratik chegirma yoki kvadratik chegirmamas bo‘ladi. Demak, Lejandr simvoli va Eyler kriteriylarga asosan, quyidagini yoza olamiz:
. (1)
Endi Lejandr simvolining quyidagi ba‘zi bir xossalarini ko‘rib chiqamiz:
1-xossa. (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 uchun quyidagini yoza olamiz: bo‘lgani uchun bo‘ladi.
2-xossa. .
Haqiqatan, taqqoslama doimo yechimga ega bo‘lib, uning yechimidir.
3-xossa. (1) taqqoslamaga asosan quyidagini yoza olamiz:
(3). Lekin larning qiymati 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, lar bir vatda 1 ga yoki -1 ga teng bo‘ladi.
4-xossa.
Isboti. (1) taqqoslamaga asosan quyidagini yozish mumkin: yoki 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 tenglikni yoza olamiz. Bu xossadan quyidagi natijalar kelib chiqadi:
1-natija.
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.
Biz bu xossani isbot qilib o‘tirmasdan undan amaliy mashg‘ulotlarda foydalanishning ba‘zi bir tomonlarini ko‘rsatib o‘tamiz.
a) shakldagi tub son bo‘lsin. U holda
Bo‘lgani uchun
b) shakldagi tub son bo‘lsa,
bo‘ladi. Demak, shakldagi tub son bo‘lsa, 2 son p modul bo‘yicha kvadratik chegirmamas bo‘ladi, ya‘ni
6-xossa. O‘zarolik qonuni. Agar p va q lar har xil toq tub son bo‘lsa,
(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 ga ko‘paytiamiz:
(5)
bu yerda (5) tenglikka asosan, p va q larning kamida bittasi 4m+1 shakldagi son bo‘lsa, bo‘lib, 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, bo‘ladi.
Misol. taqqoslama yechimga egami?
Bu savolga javob berish uchun Lejandr simvolini tuzamiz. shakldagi son bo‘lgani uchun 4-xossaga asosan quyidagicha yozamiz:
1. chunki 491 3(mod8).
2. - chunki 491 3(mod4) va 3 3(mod4) hamda 3 3(mod8).
3.
Demak, bo‘lgani uchun berilgan taqqoslama yechimga ega emas.
Adabiyotlar:


1..Ильин В.А.,Позняк Э.Г. Аналитическая геометрия .М. Наука .1983 г
2.Курош Ф.Г. Олий алгебра курси. Т.Укитувчи . 1976 й..
3.Ильин В.А.,Позняк Э.Г. Линейная алгебра .М. Наука .1974 г.
4.Ҳожиев Ж., Файнлейб.Ф.С. Алгебра ва сонлар назарияси курси. Т. 2001 й.
5.Фадеев Д.К.,Соминский И.С.Сборник задач по высшей алгебре. М.Наука .1976 г.
6. Проскуряков М.Б. Сборник задач по линейной алгебре М.1976 г.