Muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti farg’ona filiali

TEOREMA. Agar ⁽𝑎, 𝑚⁾ = 1 bo`lsa, u holda 𝑎𝑥 ≡ 𝑏(𝑚𝑜𝑑𝑚)
taqqoslamaning yechimi 𝑥 ≡ 𝑏𝑎<sup>𝜑(𝑚)−1</sup>(𝑚𝑜𝑑𝑚) bo`ladi.
ISBOTI. (𝑎, 𝑚) = 1 bo`lgani uchun Eyler teoremasiga ko`ra 𝑎^𝜑(𝑚) ≡ 1⁽𝑚𝑜𝑑𝑚⁾. Bundan
𝑎^𝜑(𝑚) ∙ 𝑏 = 𝑏(𝑚𝑜𝑑𝑚)
𝑎 ∙ 𝑎^{𝜑(𝑚)−1} ∙ 𝑏 = 𝑏(𝑚𝑜𝑑𝑚) (3)
Demak, (1) ∧ (3) ni solishtirsak, 𝑥 = 𝑎^{𝜑(𝑚)−1} ∙ 𝑏(𝑚𝑜𝑑𝑚)
yechimi ekani ko`rinadi.
Misol. 5𝑥 ≡ 3(𝑚𝑜𝑑6)
<sup>(</sup>5,6<sup>)</sup> = 1 bo`lgani uchun 𝑥 = 3 ∙ 5^𝜑(6)−1(𝑚𝑜𝑑𝑚⁾ ≡ 3 ∙ 5⁽𝑚𝑜𝑑𝑚⁾ ≡ 15 ≡ 3⁽𝑚𝑜𝑑𝑚⁾.
Sinash usuli. Bu usulning mohiyati shundaki (1) taqqoslamadagi 𝑥 o`rniga 𝑚 modulga ko`ra chegirmalarning to`la sistemasidagi barcha chegirmalar 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.

taqqoslama berilgan bo`lib, <sup>(</sup>𝑎, 𝑚<sup>)</sup> = 1 ∧ 𝑎 > 0 bo`lsin. ^𝑚
𝑎
kasrni uzluksiz

kasrlarga yoyib, uning munosib kasrlarini ^𝑃𝑘
𝑄_𝑘
(𝑘 = ^̅1^̅̅,^̅𝑛^̅) kabi belgilaymiz, bunda

𝑃_𝑛 = 𝑚 ∧ 𝑄_𝑛 = 𝑎 bo`ladi, u holda
𝑃_𝑛𝑄_𝑛−1 − 𝑃_𝑛−1𝑄_𝑛 = (−1)^𝑛

tenglikni

𝑚𝑄_𝑛−1 − 𝑎𝑃_𝑛−1 = ⁽−1^)𝑛

ko`rinishda yozish mumkin, yoki
𝑎𝑃<sub>𝑛−1</sub> ≡ <sup>(</sup>−1<sup>)𝑛</sup> + 𝑚𝑄<sub>𝑛−1</sub> dan
𝑎𝑃<sub>𝑛−1</sub> ≡ <sup>(</sup>−1<sup>)𝑛−1(</sup>𝑚𝑜𝑑𝑚<sup>)</sup> (2)
(2) ni (−1)<sup>𝑛−1</sup> ∙ 𝑏 ga ko`paytirib,
(−1)^𝑛−1 ∙ 𝑏 ∙ 𝑎𝑃_𝑛−1 ≡ 𝑏(𝑚𝑜𝑑𝑚) (3)

1. 
   va (3) ni solishtirib
   

𝑥 ≡ ⁽−1^)𝑛−1𝑏 ∙ 𝑃_𝑛−1(𝑚𝑜𝑑𝑚)

ni hosil qilamiz. Bu erda 𝑃_𝑛−1
son ^𝑚
𝑎
kasrning ⁽𝑛 − 1⁾ − munosib kasrning

suratidan iborat.

1. 
   taqqoslama yagona yechimga ega bo`lgani uchun (3) yechim (1) ning yagona yechimi bo`ladi.
   

MISOL. 68𝑥 ≡ 164(𝑚𝑜𝑑212)
⁽68,164⁾ = 4, 212/4
17𝑥 ≡ 41⁽𝑚𝑜𝑑53⁾, ⁽17,53⁾ = 1
𝑃_𝑘−1 = 25 𝑛 = 3, 𝑛 − 1 = 2
𝑥₀ ≡ ⁽−1⁾² ∙ 25 ∙ 41⁽𝑚𝑜𝑑53⁾ ≡ 18⁽𝑚𝑜𝑑53⁾
𝑥 ≡ 18, 71, 124, 177(𝑚𝑜𝑑212)

)

(
hollarda Lejandr simvoli deb ataluvchi va ^𝑎
𝑝
foydalaniladi.

Ta’rif. Quyidagi shatrlarniqanoatlantiruvchi deyiladi:
𝑎
kabi atluvchi simvoldan


)

(
^𝑎 simvol Lejandr simvoli
𝑝

( )
𝑝
1, 𝑎𝑔𝑎𝑟 𝑎 𝑠𝑜𝑛 𝑝 𝑡𝑜𝑞 𝑡𝑢𝑏 𝑚𝑜𝑑𝑢𝑙 𝑏𝑜^′𝑦𝑖𝑐ℎ𝑎𝑘𝑣𝑎𝑑𝑟𝑎𝑡𝑖𝑘 𝑐ℎ𝑒𝑔𝑖𝑟𝑚𝑎 𝑏𝑜^′𝑙𝑠𝑎;
^{= {}−1, 𝑎𝑔𝑎𝑟 𝑎 𝑠𝑜𝑛 𝑝 𝑡𝑜𝑞 𝑡𝑢𝑏 𝑚𝑜𝑑𝑢𝑙 𝑏𝑜^′𝑦𝑖𝑐ℎ𝑎𝑘𝑣𝑎𝑑𝑟𝑎𝑡𝑖𝑘 𝑐ℎ𝑒𝑔𝑖𝑟𝑚𝑎𝑚𝑎𝑠 𝑏𝑜^′𝑙𝑠𝑎.

)

(
^𝑎 simvol a sondan p bo’yicha tuzlgan Lejandr simvoli deb taladi, bu yerda a
𝑝
Lejandr simbolining surati, p esa Lejandr simvolining maxraji deyiladi.

Misol. (
⁷ ) = 𝟏, chunki Eyler kriteriysiga asosan, 7
19
19−1

² ≡ 1 (𝑚𝑜𝑑 19)

bo’lgani uchun 7 son 19 modul bo’yicha vadratik chegirmadir. 5 son 17 modul

bo’yicha kvadratik chegirmamas bo’lganligidan
( ⁵ )
= −1 bo’ladi.

17

Ma’lumki, 𝑎
𝑝−1
² ≡ 1 (𝑚𝑜𝑑 𝑝) , 𝑎
𝑝−1
² ≡ −1 (𝑚𝑜𝑑 𝑝) ekanligiga qarab, a

kvadratik chegirma yoki kvadratik chegirmamas bo’ladi. Demak, Ljandr simvoli va Eyler kriteriylariga asosan, quyidagini yoza olamiz:

(
^𝑎) ≡ 𝑎
𝑝
𝑝−1
² (𝑚𝑜𝑑 𝑝). (1)

Endi Lejandr simvolining quyidagi ba’zi bir xossalarini o’rib chiqamiz:

1-xossa. 𝑎 ≡ 𝑎₁
⁽𝑚𝑜𝑑 𝑝⁾ => ^𝑎

)

(
𝑝
= ^𝑎 )

1

(
𝑝
. (2)

Haqiqatan, bitta sinfning elementlari berilgan modul bo’yicha yo kvadratik chegirma, yoki kvadratik chegirmamas bo’ladi. Bunga asosan, (1) ning to’g’rilii kelib chiqadi. Bu xossadan foydalanib, har qanday 𝑘 ∈ 𝑍 uhun quyidagini yoza

(
olamiz: (^𝑎) = (^{𝑘𝑝+𝑎1}), (^{𝑘𝑝+𝑎1}) = ^𝑎
) bo’lgani uchun ^𝑎 = (^𝑎1)
bo’ladi.

1

)

(
𝑝 𝑝 𝑝 𝑝

2-xossa. (¹) = 1 .
𝑝 𝑝

𝑝

3. 
   
   (
   xossa. ⁻¹
   

𝑝
) = (−1)
𝑝−1

2 _.

(1) taqqoslamaga asosan quyidagini yoza olamiz:

₋₁ 𝑝−1

( ) = (−1)
𝑝
² (𝑚𝑜𝑑 𝑝) (3).

₋₁ 𝑝−1

Lekin (
𝑝
) va (−1)
² larning qiymati ±1 dan farqli emas. Shu bilan bir

vaqtda p toq tub son bo’lgani uchun 1 va -1 lar shu modul bo’yicha taqqoslanuvchi
₋₁ 𝑝−1

bo’la olmaydi. Demak, (
𝑝
bo’ladi.
) va (−1)
² lar bir vaqtda 1 ga yoki -1 ga teng

3. 
   xossa. (^𝑎∙𝑏) ≡
   

𝑝
𝑎 𝑏

)

∙

.
( ( )
𝑝 𝑝

Isboti. (1) taqqoslaamaga asosan quyidagini yozish mumkin: (^𝑎∙𝑏) ≡
𝑝

𝑝−1
𝑝−1
𝑝−1
𝑎 𝑏
𝑎∙𝑏 𝑎

⁽𝑎 ∙ 𝑏⁾
𝑏
² ≡ ⁽𝑎^)
2 ∙ ⁽𝑏⁾
𝑝−1
² ≡ (
𝑝
𝑝−1
) ∙ (
𝑝
𝑎
) (𝑚𝑜𝑑 𝑝) yoki (
𝑝
𝑏
) ≡ ( ) ∙
𝑝

( ) (𝑚𝑜𝑑 𝑝) . ⁽𝑎⁾
𝑝
² ∙ ⁽𝑏^)
2 ≡ (
𝑝
) ∙ (
𝑝
) ⁽𝑚𝑜𝑑 𝑝⁾ taqqoslamaning ikkala 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 yosa olamiz. Bu xossadan quyidagi natijalar kelib chiqadi:
(^𝑎)
𝑝

• 
  (^𝑏)
  

𝑝

)

.

(
1-natija. (^𝑎2) ≡ 1, (^𝑎∙𝑏2) ≡ ^𝑎
𝑝 𝑝 𝑝
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.

₂ 𝑝²−1

3. 
   xossa. (
   

𝑝
) ≡ (−1) ⁸ .

Biz bu xossani isbot qilib o’tirmasdan undan amaliy mashg’ulotlarda foydalnishning a’zi bir tomonlarin ko’rsatib o’tamiz.

1. 
   𝑝 ≡ 8𝑚 ± 1 shakldagi tub son bo’lsin. U holda
   

𝑝² − 1
=
8
(8𝑚 ± 1)² − 1


8
= 8𝑚² ± 2𝑚 ≡ 0 (𝑚𝑜𝑑 2)

Bo’lgani uchun (²) ≡ 1.
𝑝

2. 
   𝑝 ≡ 8𝑚 ± 3 shakldagi tub son bo’lsa,
   

𝑝² − 1
=
8
(8𝑚 ± 3)² − 1


8
= 8𝑚² ± 6𝑚 + 1 ≡ 1 (𝑚𝑜𝑑 2)

bo’adi. Demak, 𝑝 ≡ 8𝑚 ± 3 shakldagi tub son bo’lsa, 2 son p modul boyicha

kvadratik chegirmamas bo’lad, ya’ni (²)
≡ −1.

𝑝

3. 
   xossa. O’zarolik qonuni.
   

Agar p va q lar har xil toq tub son bo’lsa,

𝑝 𝑞
𝑝−1_∙𝚐−1

tenglik o’rinli bo’ladi.

( ) ∙ (
𝑞 𝑝
) ≡ (−1) ^{2 2} (4)

Bu xossani ham isbot qilmasan uning amaliy mashg’ulotlardaqo’llanishini

ko’rsatmiz. Buning uchun (4) ning har ikkaa qismini
(^𝑝)
𝑞
ga ko’paytiramiz:

_𝑞 𝑝−1 𝚐−1 _𝑝

bu yerda

2



^𝑝) = 1.

(
𝑞
( ) ≡ (−1) ^{2 ∙}
𝑝
² ( ), (5)
𝑞

(5) tenglikka asosan, p va q larning kamida bittasi 4m+1 shakldagi son bo’lsa,

𝑝−1 𝚐−1
𝑝 𝑞

(−1)
^{2 ∙ 2} = 1 bo’lib, (
𝑞
) = (
𝑝
) hosil boladi.

Agar p va q larning har biri 4m+3 shaklagi tub son bo’lsa,u holda (-1) ning

darajasi toq son bo’lib,
(^𝑝)
𝑞
𝑞
= − ( )
𝑝
bo’ladi.

Misol. 𝑥² ≡ 426(𝑚𝑜𝑑 491) taqqoslama yechimga egami?
Bu savolga javob berish uchun (⁴²⁶) Lejandr simvolini tuzamiz. 426 = 2 ∙
491
3 ∙ 71 shakldagi son bo’lgani uchun 4- xossaga asosan quyidagicha yozamiz:

( ) (
₍426_{) ≡} 2 _∙ 3
) ∙ ( ⁷¹ ) .

491
491
491
491

2. 
   
   (
   
   )
   ( ³ ) ≡ − (⁴⁹¹) ≡ − ²
   

≡ −⁽−1⁾ = 1, chunki 491 ≡ 3 (𝑚𝑜𝑑 4) va 3 ≡

491 3 3

)

(

)

(

)

(

)

(

)

(

)
3 (𝑚𝑜𝑑 4) hamda 3 ≡ 3 (𝑚𝑜𝑑 8).

3. 
   
   (
   
   )
   
   (
   ( ⁷¹ ) ≡ − (⁴⁹¹) ≡ − ⁶⁵ ≡ − ⁵
   

• 
  13
  

_{≡ −} 71

• 
  71
  

≡ − ¹ ∙ ⁶ ≡

491
71 71
71 71
5 13
5 13

)

(

)

(
− ( ² ) ∙ ( ³ ) ≡ −⁽−1^{) 13} ≡ 1 ∙ ¹
≡ 1, chunki 491 ≡ 3⁽𝑚𝑜𝑑 4⁾, 71 ≡

13 13 3 3
3 ⁽𝑚𝑜𝑑 4⁾, 491 ≡ 65 ⁽𝑚𝑜𝑑 71⁾, 5 ≡ 1 ⁽𝑚𝑜𝑑 4⁾, 13 ≡ 5 (𝑚𝑜𝑑 8).
Demak, (⁴²⁶) ≡ ⁽−1⁾ ∙ 1 ∙ 1 = −1, (⁴²⁶) ≡ −1 , bo’lgan uchun berilgan