Taqqoslamalar va ularning xossalari

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

_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₁, r₂ , ..., r_c
sonlari uchun
ar₁, ar₂ , ..., ar_c
sonlarni

ar₁  s₁(mod m),
ar₂
 s₂ (mod m),
ar_c
 s_c (mod m).

Bu yerda
s₁, s₂ , ..., 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

r_i = r_j . ^{Bu esa r}_k
sonlarining turli ekanligiga zid.

Shuningdek,
s₁, s₂ , ..., s_c
sonlarning barchasi m bilan o‘zaro tub

ekanligini ko‘rish qiyin emas. Bundan esa
tenglik kelib chiqadi.
r₁  r₂ ... r_c
= s₁  s₂ ... s_c

ar_i
 s_i (mod m)
taqqoslamalarni hadma-had ko‘paytirsak,

a^cr  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

deyiladi.

39 - §. Birinchi darajali taqqoslamalar.

Qoldiqlar haqidagi Xitoy teoremasi

Biz 37-mavzuda
_m = _0, 1, ..., m 1_

to‘plamni aniqlab, bu

to‘plamda qo‘shish va ko‘paytirish amallarini kiritgan edik.

Ushbu mavzuda
to‘plamda berilgan





a  x = b

bir noma’lumli birinchi darajali tenglamani yechish masalasi bilan shug‘ullanamiz.

Ma’lumki,
da keltrilgan bir noma’lumli tenglama
ax  b(mod m)

bir noma’lumli birinchi darajali taqqoslamaga teng kuchlidir, bu yerda

a,b  ^{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:

a) (a, m) = 1;
b) (a, m) = d > 0
c) (a, m) = d > 0

bo‘lib, b soni d ga bo‘linmaydi; bo‘lib, b soni d ga bo‘linadi.

39.1-tasdiq.

ax  b(mod m)
bir noma’lumli birinchi darajali

taqqoslama tenglama uchun quyidagilar o‘rinli:

a) (a, m)  1
yagonadir;
bo‘lsa, taqqoslamaning yechimi mavjud va

b) (a, m)  d > 0
emas;
c) (a, m)  d > 0
yechimga ega.
bo‘lib, b soni d ga bo‘linmasa, yechim mavjud bo‘lib, b soni d ga bo‘linsa, taqqoslama d ta

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

qiymatlarni qabul qiladi. Demak, ixtiyoriy b  uchun yagona ^x
topiladi, ya’ni taqqoslama yagona yechimga ega.

Aytaylik, (a, m)  d
bo‘lsin, ya’ni
a = a₁d,
m = m₁d . 37.10-

xossaga asosan
ax  b(mod m)
yechimga ega bo‘lishi uchun b sonining

ham d ga bo‘linishi zarur va yetarli, ya’ni
b = b₁d .

Taqqoslamaning xar bir hadi va modulini d ga bo‘lib,
a₁x  b₁ (mod m₁ )

tenglamani hosil qilamiz. yagona yechimga ega.
(a₁, m₁ )  1
bo‘lganligi uchun bu tenglama

Aytaylik,
x₁ soni tenglama yechimining eng kichik nomanfiy

elementi bo‘lsin. U holda
x = x₁  m₁,


x₁  2m₁,


x₁  (d 1)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.

to‘plam chekli bo‘lganligi uchun



a  x = b

tenglamaga dagi elementlarini birma-bir olib kelish qo‘yish
mumkin. Agar ularning birortasida tenglama ayniyatga aylansa, demak bu element tenglamaning yechimi bo‘ladi.

Masalan,



to‘plamda ^{5  x = 4}
tenglamani qaraymiz.

No‘malumning o‘rniga quyidagilarni hosil qilamiz:
ning elemetlarini olib borib qo‘ysak,

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 u,v  sonlari topilib,

bo‘ladi. Bu tenglikdan
au  mv = 1





^{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.

Misol 39.1. ^{7  x  9}
tenglamani
da yeching. Bu yerda
a  7,

b  9 va
m  10
bo‘lib, (7,10) = 1. Yevklid algoritmidan foydalanib

7  3 10  (2)  1 ekanligini hosil qilamiz, ya’ni Demak,
u  3,
v  2.

x = 3  9 = 3  9 = 27 = 7

tenglamaning yechimi bo‘ladi.

Eyler teoremasidan foydalanib yechish usuli. Ma’lumki,

(a, m)  1
bo‘lsa,
_a (m)
 1(mod m)



bo‘ladi. Endi a  x  b
tengla-

maning ikkala tomonini
_a (m)1
ga ko‘paytirsak,

_a (m)1 _{ a  x  a} (m)1 <sub> b,




a</sub> (m) _{ x  a} (m)1 _{ b,}




1 x  a^(m)1  b ,



_{x  a} (m)1 _{ b.}

hosil bo‘ladi. Topilgan ^x element tenglamaning yechimi bo‘ladi.

Misol 39.2. ^{3  x  7}
tenglamani
da yeching. Ushbu

tenglamada (3,11)  1
bo‘lganligi uchun yuqorida keltirilgan usuldan

foydalanamiz. (11)  10
ekanligi uchun

bo‘ladi.

x  3⁹  7  27³  7  5³  7  125  7  4  7  28  6

FOYDALANILGAN ADABIYOTLAR RO‘YHATI

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. 
   Kuttler K. Elementary linear algebra. 2012. – 433 p.
   
4. 
   Strang G. Introduction to Linear algebra. 2016. – 584 p.
   
5. 
   Бухштаб А.А. Теория чисел. 1966. – 386 с.
   
6. 
   Веретенников Б.М., Михалева М.М., Алгебра и теория чисел. Учебное пособие. 2014. – 52 с.
   
7. 
   Виноградов И.М. Основы теории чисел. 1948. – 178 c.
   
8. 
   Гельфанд И.М. Лекции по линейной алгебре. 1998. – 320 с.
   
9. 
   Кострикин А.И. Введение в алгебру. Часть I. Основы алгебры. 2000. – 272 с.
   
10. 
    Кострикин А.И. Введение в алгебру. Часть II. Линейная алгебра. 2000. – 368 с.
    
11. 
    Куликов Л.Я. Алгебра и теория чисел. Москва. 1979. –559 с.
    
12. 
    Курош А.Г. Курс высшей алгебры. 2008. – 432 c.
    
13. 
    Проскуряков И.Л. Сборник задач по линейной алгебре.
    

«Наука», 2010. – 480 с.

14. 
    Фаддеев Д.К. Лекции по алгебре. 2007. – 416 с.
    
15. 
    Фаддеев Д.К., Соминский И.С. Задачи по высшей алгебре, Санкт-Петербург, 1999. – 304 с.
    
16. 
    Хожиев Ж.Х. Файнлейб А.С. Алгебра ва сонлар назарияси курси, Тошкент, «Ўзбекистон», 2001 й.