Algebra va sonlar nazariyasi

^ri - -1^Л
. P2


'i -±^л
. Pk


formulaga ega bo‘lamiz.

20. 
    teorema (Eyler teoremasi). O‘zaro tub bo‘lgan a va m(m > 1) sonlari uchun quyidagi munosabat o‘rinli:
    

a ^p(m) = * (_mod m). (38.2)
Isbot. Aytaylik, p(m) = c bo‘lsin. m dan kichik va m bilan o‘zaro tub bo‘lgan turli r, Г, . ., Г sonlari uchun ar_x, ar₂,..., ar_c sonlarni qaraymiz. U holda
ar = Sj (mod m), ar₂ = s₂ (mod m), ..., ar_c = s_c (mod m).
Bu yerda Sj, s₂,..., s_c lar o‘zaro teng bo‘lmagan sonlar. Haqiqatan, s_f = s. bo‘lsa, u holda


265

ar = s (mod m), ar . = s. (mod m)

ekanligidan
ar - ar = (s - s ■ )(mod m) = 0(mod m) kelib chiqadi. (a,m) = 1 bo‘lganligi uchun r - r = 0(modm), ya’ni r = r. Bu esa r sonlarining turli ekanligiga zid.
Shuningdek, s, s₂,..., s sonlarning barchasi m bilan o‘zaro tub ekanligini ko‘rish qiyin emas. Bundan esa r • r₂ •... • r = s_x • s₂ • ...• s_c tenglik kelib chiqadi.
ar = s (mod m) taqqoslamalarni hadma-had ko‘paytirsak,
a°r • r • .. • r = S • s₂ • . • s_c (mod m) munosabatga ega bo‘lamiz. Demak, a° = 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-i ^ 1(mod p).
Ushbu tegnlikning ikkala tomonini a ga ko‘paytirsak, a^p = a(mod p)
tenglikka ega bo‘lamiz. Bu tenglik Fermaning kichik teoremasi deyiladi.

37. 
    - §. Birinchi darajali taqqoslamalar.
    

Qoldiqlar haqidagi Xitoy teoremasi
Biz 37-mavzuda 7L_m = |(). 1..... m - l| to‘plamni aniqlab, bu
to‘plamda qo‘shish va ko‘paytirish amallarini kiritgan edik.
Ushbu mavzuda 7L_m to‘plamda berilgan
a • x = b
bir noma’lumli birinchi darajali tenglamani yechish masalasi bilan shug‘ullanamiz.
Ma’lumki, Z_m da keltirilgan bir noma’lumli tenglama ax = b(mod m)
bir noma’lumli birinchi darajali taqqoslamaga teng kuchlidir, bu yerda flieZ, 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:

1. 
   (a, m) = 1;
   
2. 
   (a,m) = d >0 bo‘lib, b soni d ga bo‘linmaydi;
   
3. 
   (a,m) = d >0 bo‘lib, b soni d ga bo‘linadi.
   

1. 
   tasdiq. ax = b(modm) bir noma’lumli birinchi darajali taqqoslama tenglama uchun quyidagilar o‘rinli:
   

1. 
   (a,m) = 1 bo‘lsa, taqqoslamaning yechimi mavjud va yagonadir;
   
2. 
   (a,m) = d >0 bo‘lib, b soni d ga bo‘linmasa, yechim mavjud emas;
   
3. 
   (a,m) = d >0 bo‘lib, b soni d ga bo‘linsa, taqqoslama d ta yechimga ega.
   

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 qiymatlami qabul qiladi. Demak, ixtiyoriy uchun yagona x
topiladi, ya’ni taqqoslama yagona yechimga ega.
Aytaylik, (a,m) = d bo‘lsin, ya’ni a = a_xd, m = md. 37.10- xossaga asosan ax = b(modm) yechimga ega bo‘lishi uchun b sonining ham d ga bo‘linishi zarur va yetarli, ya’ni b = b_xd.
Taqqoslamaning xar bir hadi va modulini d ga bo‘lib, ax = b (mod щ )
tenglamani hosil qilamiz. (a, щ) = 1 bo‘lganligi uchun bu tenglama yagona yechimga ega.
Aytaylik, x soni tenglama yechimining eng kichik nomanfiy elementi bo‘lsin. U holda


267

x = x + m 5 x + 2 m, ..., x + (d - i)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. Z_ra to‘plam chekli bo‘lganligi uchun a-x = b tenglamaga Z_ra dagi elementlarini birma-bir olib kelish qo‘yish mumkin. Agar ularning birortasida tenglama ayniyatga aylansa, demak bu element tenglamaning yechimi bo‘ladi.
Masalan, Z₆ to‘plamda 5-x = 4 tenglamani qaraymiz. Noma’lumning o‘miga Z₆ ning elementlarini olib borib qo‘ysak, quyidagilarni hosil qilamiz:
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 3w, v e Z sonlari topilib,
au + mv = 1
bo‘ladi. Bu tenglikdan 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.