22-мавзу: биринчи даражали бир номаълумли танқосламаларнинг эчимлари сони ҳАҚидаги теорема. 1-таъриф

Эслатма.Мураккаб модули такқослама учун 1-теорема ўринли бўлмайди.
Масалан, x²–5х+ 6  0 (mod 6) таққослама х= 0, 2, 3,5 (mod 6) лардан иборат тўртта ечимга эга.
4-ТЕОРЕМА. Бош коэффициенти 1 га тенг бўлган n (n>p) даражали f(x)=0(mod р) таққослама р та ечамга эга бўлиши учун f(x) ни х^р–х га бўлишдан ҳосил бўлган r(x)қолдиқ кўпҳаднинг барча коэффициентлари р га бўлиниши зарур ва етарли.
28-МАВЗУ: СОННИНГ ТАРТИБИ. ЧЕГИРМАЛАР СИНФИНИНГ ТАРТИБИ. ХОССАЛАРИ.

Эйлер теоремасига кўра (а; m)=1 бўлганда

a^φ(m)≡ 1(mod m) (1)
таққослама ўринли. (1) таққосламанинг иккала қнсмини k- даражага кўтариб
a^kφ(m)= 1(mod m) (2)
га эга бўламиз. (1) ва (2) ни умумлаштириб қуйидаги хулосага келамиз: aгap(a;m) = l бўлса, ҳар доим шундай γ натурал сон топиладики,
a^γ ≡ l(mod m) (3)
таққослама ўринли бўлaди ((1) га асосан).
Биз ушбу қўлланманинг биринчи қисмида натурал сонлар системасини қурганда ҳар қандай натурал сонлар тўплами доимо энг кичик элемент эга эканини кўpгaн эдик. Шунга кўра (3) таққосламани қаноатлантирувчи натурал сонлар тўпламининг энг кичик элементи мавжуд. Уни δ орқали белгилайлик, яъни δ = min γ бўлсин.
1-ТАЪРИФ. Aгap (а;m) = 1 бўлганда
a^δ ≡ l (mod m) (4)
таққослама ўринли бўлса, у ҳолда δ сон а сонинанг m модулга кўра кўрсаткаш ёки m модуль бўйича а сонига тегишли, кўрсаткич дейилади.
Бу таьрифга асосан, δ ≤ φ(m) бўлади.
2-ТАЪРИФ. Агар (а; m)=1бўлиб, δ = φ(m) бўлса, у ҳолда а сон m модуль бўйича бошланғич илдаз дейилади.
m модуль бўйича бирор а сонига тегишли кўрсаткични топишни қуйидаги мисолларда кўриб ўтамиз:
1-мисол. m=7 модуль бўйича 2,3,5 сонларга тегишли бўлган кўрсаткичларни топинг.
а) а=2 бўлсин, φ(7)= 6 бўлгани учун 2¹, 2², 2³, 2⁴, 2⁵, 2⁶ даражаларни 7 модуль бўйича кўриб чиқамиз:
2≡ 2 (mod7),
2²≡4 (mod7,
2³≡l (mod7).
Демак, таърифга кўра 2 сон 7 модуль бўйича 3 кўрсаткичга тегишли.
б) a = 3 бўлсин. У ҳолда
3≡ 3(mod7),
3²≡2 (mod7),
3³≡–l(mod7),
3⁴≡ 4(mod 7),
3⁵≡ 5(mod 7),
3⁶≡ l(mod7).
Демак, 3 сонининг 7 модуль бўйича кўрсаткичи 6 га тенг экан.
в) a=5 бўлсин. У ҳолда
5 ≡ 5(mod7),
5² ≡ 4(mod 7),
5³ ≡20 (mod 7)
5⁴ ≡ 16 ≡ 2 ( mod7),
5⁵ ≡24 ≡ 3(mod 7)
5⁶ ≡ 1 (mod 7).
Бундан 5 сонининг 7 модуль бўйича кўрсаткичи ҳам 6 га тенг. б) ва в) лар да φ(7)=6 бўлгани учун 3 га 5 сонлари 7 модуль бўйича бошланғич илдизни ташкил этади. Демак, битта модулъ бўйича ҳар хил бошланғич илдизлар мавжуд экан.
1-ТЕОРЕМА. Бирор m модуль бўйича тузилган битта синфнинг чегирмалари шу модуль буйича бир хил кўрсаткичга тегишли бўлади.
ИСБОТИ. Теоремани тескаридан исбот қилайлик, а ва а₁ чегирмалар m модуль бўйича битта чегирмалар синфидан олинган бўлсин.
а≡a₁ (mod m) бўлиб, а^δ≡1(modт) ва ҳамда δ≠ δ₁ бўлсин. Аниқлик учун δ<δ₁ (ёки δ>δ₁) деб оламиз. δ<δ₁ бўлиши мумкин эмас, чунки а^δ≡1(mod m) ва а≡a₁ (mod m) лигидан охирги таққосламани δ даражага кўтариб, га эга бўламиз. У ҳолда а^δ≡1(mod m) эканидан бўлади. a₁ сон δ₁ кўрсаткичга тегишли бўлгани учун, таърифга асосан, δ≥δ₁ га эга буламиз. Бу эса δ<δ₁ шартга зид. Энди δ>δ₁ деб фараз қиламиз ва а≡a₁ (mod m) нинг иккала қисмини δ₁ даражага кўтарамиз:

a сон m модуль бўйича δ кўрсаткичга тегишли бўлгани учун
δ≤δ₁
(δ ≤ δ₁)  (δ ≥ δ₁)  δ = δ₁.
Демак, агар бирор а сон m модуль бўйича бирор δ кўрсаткичга тегишли бўлса, а билан m модуль бўйича тенг қолдиқлар синфининг барча элементлари ҳам шу кўрсаткичга тегишли бўлади, яъни берилган модуль бўйича битта кўрсаткичга тегишли бўлган сонлар синфи тўғрисида гапириш мумкин.
m модуль бўйича δ кўрсаткичга тегишли бўлган ҳар бир а сони m билан ўзаро туб бўлиши лозим, акс ҳолда, яъни (а;m)= d > 1 бўлса, a^γ≡l(modm) таққослама ўринли бўлмайди.
Агар а сони m модуль бўйича бошланғич илдиз бўлса, у ҳолда биз бошланғич илдизлар синфи ҳақида фикр юритамиз.
29-МАВЗУ: ТУБ МОДУЛ БЎЙИЧА БОШЛАНҒИЧ ИЛДИЗЛАР СОНИ


2-ТЕОРЕМА. Агар (a; m) = 1 бўлганда
а^δ≡1(modт) (5)
бўлса, у ҳолда
а⁰, а¹, ... , а^δ-1 (6)
сонлар системаси, m модуль бўйича ўзаро таққосланмайди.
ИСБОТИ. Исботни тескарисини фараз қилиш усули билан бажарамиз. Фараз қилайлик, k ва l лар ихтиёрий натурал сонлар бўлганда а^k≡a^l (mod m) таққослама рост бўлиб, бунда δ – l ≥ l>k ≥ 0 бўлсин. (а^k; m)=1 бўлгани учун юқоридаги таққосламанинг иккала қисмини a^k гa бўлиб
a^l-k≡ 1 (mod m) (0 < l – k < δ)
таққосламага эга бўламиз. Лекин бу таққосламанинг ўринли бўлиши мумкин эмас, чунки а сон m модуль бўйича δ кўрсаткичга тегишли.
1-натижа. δ = φ(m) бўлганда (3) система m модуль бўйича чегирмаларнинг келтирилган системасини ташкил қилади.
Ҳақиқатан,

1. 
   (6) системада φ(m) та элемент мавжуд;
   

2. (а; m) = 1  (а^k;m) = 1;
3. а^k элементларнинг ҳар бири 2-теоремага асосан, m модуль бўйича турли синфларга тегишли. Бу учта шарт (6) нинг келтирилган чегирмалар системасини билдиради.
2-натижа. Aгap m, модуль туб сон бўлса, яъни m=р бўлиб ва а сон р модуль бўйича бошланғич илдиз бўлса, у ҳолда (6) қатор
а⁰, а¹, ... , а^р-2 (7)
кўринишда бўлади.
2-мисол. 7 модуль бўйича 5 бошланғич илдиз учун (7) кўринишдаги системани тузинг.
1 =3⁰, 3, 3², 3³, 3⁴, 3⁵ ни тузамиз ва ҳар бир даражани 7 модуль бўйича энг кичик мусбат чегирмалар билан алмаштирамиз. Улар қуйидагилардан иборат (1-б мисол):
1, 3, 2, 6, 4, 5.
Ҳақиқатан, бу система 7 модуль бўйича чегирмаларнинг келтирилган системасидан иборатдир.
3-ТЕОРЕМА. а сон m модуль бўйича δ кўрсаткичга тегшили бўлса, у ҳолда ушбу
(8)
таққосламанинг ўринли бўлиши учун
γ= γ ₁ (mоd δ) (9)
таққосламанинг ўринли бўлиши зарур ва етарлидир.
ИСБОТИ. Зарурийлиги. а сон m модуль бўйича δ кўрсаткичга тегишли ва таққослама ўринли бўлсин. У ҳолда γ ва γ₁ ларни қуйидагича ёзиб оламиз:
γ =δq+r, γ₁=δq₁+r₁ (0≤r<δ, 0≤r₁, δ)
ва r = r₁ эканини кўрсатамиз. γ ва γ₁ ларнинг бу қийматларини (7) гa қўямиз. У ҳолда

Лекин а^δ≡1(mod m) бўлгани учун охирги таққослама кўринишни олади.
Юқорида кўриб ўтилган 2-теоремага асосан охирги таққослама фақатгина r = r₁ бўлгандағина ўринли бўлади. Демак, r = r₁ ва γ≡γ₁(modт).
Етарлилиги. а^δ ≡ 1 (mod m) ва γ≡γ₁(modт) таққосламалар ўринли бўлсин. Иккинчи таққосламани тенглик ёрдамида қуйидагича ёзиш мумкин:
γ =δq+r, γ₁=δq₁+r (0≤r<δ)
а сон m модуль бўйича δ кўрсаткичга тегишли бўлганидан

3-натижа. γ≡0 (mod δ) бўлганда ва фақат шу ҳолдагина a^γ≡1 (mod m) таққослама ўринли бўлади.
Ҳақикатан, агар γ≡γ₁(mod δ) ва γ₁=0 десак, a^γ≡a⁰≡1(modm) ҳосил бўлади. Бошқача айтганда γ/δ бажарилса. a^γ≡1 (mod m) бўлади.
4-натижа. а соннинг m модуль бўйича δ кўрсаткичи φ (m) нинг бўлувчиси бўлади. (Агар а бошланғич илдиз бўлса, δ кўрсаткич φ(р)=р-1 ни бўлади) δ кўрсаткични топиш учун а⁰, а¹, ... , a^δ-1 системадаги барча даражаларни ҳисоблаб чиқиш шарт эмас, унинг ўрнига даража кўрсаткичи φ(m) ни бўладиган даражаларни ҳисоблаймиз.
Масалан, 7 модуль бўйнча 5 сон тегишли бўлган кўрсаткични топиш учун φ (7) = 6 бўлганидан 1, 2, 3 ва 6 кўрсаткичларни текшириш кифоя.