Birinchi darajali taqqoslashlar. Taqqoslash moduli natural son. Taqqoslash moduli natural son

n da ular bir xil qoldiqlarni beradi.

Ekvivalent formulalar: a va b moduli bilan solishtirish mumkin n agar ularning farqi a - b n ga bo'linadi yoki a ni quyidagicha ifodalash mumkin bo'lsa a = b + kn , Qayerda k- ba'zi bir butun son. Masalan: 32 va −10 7-modul bilan taqqoslanadi, chunki

“a va b ni solishtirish mumkin bo'lgan modul n” bayonoti quyidagicha yoziladi:

Modulning tenglik xususiyatlari

Moduli taqqoslash munosabati o'ziga xos xususiyatlarga ega

Har qanday ikkita butun son a Va b taqqoslanadigan modul 1.

Raqamlar uchun a Va b modul bo'yicha solishtirish mumkin edi n, ularning farqi ga bo'linishi zarur va etarli n.

Agar va raqamlari modul bo'yicha juftlik bilan taqqoslansa n, keyin ularning yig'indilari va , shuningdek, ko'paytmalari va modul bo'yicha ham solishtirish mumkin n.

Agar raqamlar bo'lsa a Va b moduli bilan solishtirish mumkin n, keyin ularning darajalari a k Va b k modul bo'yicha ham solishtirish mumkin n har qanday tabiiy ostida k.

Agar raqamlar bo'lsa a Va b moduli bilan solishtirish mumkin n, Va n tomonidan bo'linadi m, Bu a Va b moduli bilan solishtirish mumkin m.

Raqamlar uchun a Va b modul bo'yicha solishtirish mumkin edi n, oddiy omillarga uning kanonik parchalanishi shaklida taqdim etilgan p i

zarur va yetarli

Taqqoslash munosabati ekvivalentlik munosabati bo'lib, oddiy tengliklarning ko'pgina xususiyatlariga ega. Masalan, ularni qo'shish va ko'paytirish mumkin: agar

Biroq, taqqoslashlarni, umuman olganda, bir-biriga yoki boshqa raqamlarga bo'linib bo'lmaydi. Misol: , lekin 2 ga kamaytirilsa, biz noto'g'ri taqqoslashni olamiz: . Taqqoslash uchun qisqartma qoidalari quyidagicha.

Agar ularning modullari mos kelmasa, taqqoslash bo'yicha operatsiyalarni ham bajara olmaysiz.

Boshqa xususiyatlar:

Tegishli ta'riflar

Deduktsiya sinflari

ga taqqoslanadigan barcha raqamlar to'plami a modul n chaqirdi chegirma klassi a modul n , va odatda [ bilan belgilanadi a] n yoki . Shunday qilib, taqqoslash qoldiq sinflarining tengligiga tengdir [a] n = [b] n .

Modullarni taqqoslashdan boshlab n- butun sonlar to'plamidagi ekvivalentlik munosabati, keyin qoldiq sinflar moduli n ekvivalentlik sinflarini ifodalaydi; ularning soni teng n. Barcha qoldiq sinflari moduli to'plami n yoki bilan belgilanadi.

Qo'shish va ko'paytirish amallari to'plamda tegishli operatsiyalarni keltirib chiqaradi:

[a] n + [b] n = [a + b] n

Ushbu amallarga nisbatan to'plam chekli halqadir va agar n oddiy - chekli maydon.

Deduksiya tizimlari

Qoldiqlar tizimi cheklangan sonlar to'plamida uning chegarasidan tashqariga chiqmasdan arifmetik amallarni bajarishga imkon beradi. Chegirmalarning to'liq tizimi modul n - tengsiz modul n bo'lgan har qanday n ta butun sonlar to'plami. Odatda, eng kichik manfiy bo'lmagan qoldiqlar modul n qoldiqlarining to'liq tizimi sifatida olinadi.

0,1,...,n − 1

yoki raqamlardan tashkil topgan mutlaq eng kichik ajratmalar

g'alati holatda n va raqamlar

teng bo'lsa n .

Taqqoslashlarni yechish

Birinchi darajali taqqoslashlar

Raqamlar nazariyasi, kriptografiya va fanning boshqa sohalarida ko'pincha shaklni birinchi darajali taqqoslash uchun echimlarni topish muammosi paydo bo'ladi:

Bunday taqqoslashni yechish gcd ni hisoblashdan boshlanadi (a, m)=d. Bunday holda, 2 ta holat mumkin:

Agar b ko'p emas d, keyin taqqoslash hech qanday yechimga ega emas.
Agar b bir nechta d, keyin taqqoslash yagona yechim moduliga ega m / d, yoki, nima bir xil, d modulli yechimlar m. Bu holda, asl taqqoslashni kamaytirish natijasida d taqqoslash:

Qayerda a 1 = a / d , b 1 = b / d Va m 1 = m / d butun sonlardir va a 1 va m 1 nisbatan asosiy hisoblanadi. Shuning uchun raqam a 1 teskari modul bo'lishi mumkin m 1, ya'ni shunday raqamni toping c, bu (boshqacha aytganda, ). Endi olingan taqqoslashni ga ko'paytirish orqali yechim topiladi c:

Qiymatni amaliy hisoblash c turli yo'llar bilan amalga oshirilishi mumkin: Eyler teoremasidan, Evklid algoritmidan, davomli kasrlar nazariyasidan (qarang. Algoritm) va boshqalar. Xususan, Eyler teoremasi qiymatni yozishga imkon beradi. c sifatida:

Misol

Taqqoslash uchun bizda bor d= 2, shuning uchun 22 moduli taqqoslash ikkita echimga ega. Keling, 26 ni 22 moduli bilan solishtirish mumkin bo'lgan 4 ga almashtiramiz va keyin barcha 3 raqamni 2 ga kamaytiramiz:

2 moduli 11 ga ko'p bo'lgani uchun chap va o'ng tomonlarini 2 ga qisqartirishimiz mumkin. Natijada bitta modul moduli 11: ga erishamiz, ikkita modul 22: moduliga ekvivalent.

Ikkinchi darajali taqqoslashlar

Ikkinchi darajali taqqoslashlarni echish, berilgan sonning kvadrat qoldiq ekanligini aniqlashga (kvadrat o'zaro qonunidan foydalanish) va keyin kvadrat ildiz modulini hisoblashga to'g'ri keladi.

Hikoya

Ko'p asrlar davomida ma'lum bo'lgan xitoycha qoldiq teoremasi (zamonaviy matematik tilda) qoldiq halqa moduli bir nechta tub sonlarning ko'paytmasi ekanligini ta'kidlaydi.

Keling, taqqoslash tizimini ko'rib chiqaylik

Bu yerda f1(x), f2(x), …. , fs(x)€Z[x].

Teorema 1. M = m1,m2,…,ms sonlarning eng kichik umumiy karrali bo‘lsin. Agar tizim (2) ni qanoatlantirsa, u holda a moduli M sinfidagi istalgan raqam ushbu tizimni qanoatlantiradi.

Isbot. b€ a sinfiga o'ting. Chunki a ≡ b(mod M), keyin a ≡b(mod m), i= 1,2,...,s (taqqoslash xossasi 16). Binobarin, b, a kabi, teoremani isbotlovchi tizimning har bir taqqoslashini qanoatlantiradi. Shuning uchun (2) sistemaning yechimini M sinf moduli deb hisoblash tabiiy.

Ta'rif. Taqqoslash tizimining yechimi(2) - tizimning har bir taqqoslashini qanoatlantiradigan M = modulli sonlar sinfi.

12. Darhol ta'kidlaymizki, toq sonlar ikkinchi taqqoslashni qoniqtirmaydi. 12-modul qoldiqlarining to'liq tizimidan juft raqamlarni olib, to'g'ridan-to'g'ri tekshirish orqali biz 2, -2, 6 raqamlari 2-qiyoslashni qondirishiga amin bo'ldik va tizim ikkita echimga ega: x ≡ 2 (mod l2), x ≡ - 2 (mod 12).

Keling, 1-darajali taqqoslash tizimini ko'rib chiqaylik (3)

Teorema 2. d=(m1,m2), M = bo‘lsin.

Agar c1 - c2 d ga bo'linmasa, (3) sistemaning yechimlari yo'q.

Agar (c1 -c2):d bo'lsa, (3) tizim bitta yechimga ega - M sinf moduli.

Isbot. 1-taqqosdan x = c1+m1t, t€Z. 2-taqqosni almashtiring: s1+ m1t ≡ c2(mod m2) yoki

m1t ≡ c2-cl (mod m2). Bu taqqoslash faqat (c2 – c1): d.

Va yechim sinf modulidir (§2 dan 4-teorema).

Yechim , ya'ni bu erda k€Z bo'lsin.

M==, ya’ni x≡c1+m1t0(mod M) yechimdir

Misollar.

1. :2, tizim bitta yechim sinfi moduliga ega 24. 1-taqqosdan x =2+6t. 2-taqqoslashda x ni almashtirsak, bizda: 2 + 6t≡ 4(tnod 8); 6t≡ 2(mod 8); -2t≡2(mod8); t≡-1 (mod 4); t=-1+4k; x=2+6(-1+4k); x=-4+24k, ya'ni x≡-4(mod 24).

2. 7-3 3 ga bo'linmaydi, sistemaning yechimlari yo'q.

Xulosa 1. Taqqoslash tizimi (4)

Yoki uning yechimlari yo'q yoki bitta yechimga ega - sinf moduli M =.

Isbot. Agar birinchi ikkita taqqoslash sistemasi yechimga ega bo'lmasa, u holda (4) ning yechimlari yo'q. Agar u x ≡ a(mod) yechimga ega bo'lsa, u holda bu taqqoslashga sistemaning uchinchi taqqoslashini qo'shish orqali biz yana (3) ko'rinishdagi sistemani olamiz, uning yechimi bitta bo'ladi yoki yechimlari yo'q. Agar uning yechimi bo'lsa, biz (4) tizimning barcha taqqoslashlarini tugatmagunimizcha shu yo'lni davom ettiramiz. Agar yechim mavjud bo'lsa, bu M sinf modulidir.

Izoh. Bu erda LCM xususiyati ishlatiladi: =.

Xulosa 2. Agar m1,m2,…,ms juft-juft boʻlsa, sistema (4) bitta yechimga ega boʻladi - modul sinfi M=m1m2…ms.

Misol:

Modullar juftlik nisbatan sodda bo'lganligi sababli, tizim bitta yechimga ega - modul sinfi 105 = 5 * 3 * 7. Birinchi taqqoslashdan boshlab

Biz ikkinchi taqqoslashni almashtiramiz: 2 +5t≡ 0(mod 3) yoki 2t≡-2(mod3), t=-1+3k, x=2+5(-1+3k), x=-3+15k . Uchinchi taqqoslashda almashtiramiz:

3+15k≡5(mod7), 15k≡8(mod 7), k=1+7l. keyin x=-3+15(1+7l); x=12+105l; x≡12 (mod 105).

Keling, tanishamiz boshqalar bu tizimni yechish usuli, (Biz tizimning bitta yechimga ega ekanligidan foydalanamiz.) Keling, ikkala qismni va birinchi taqqoslash modulini 21 ga, ikkinchisini 35 ga va uchinchisini 15 ga ko'paytiramiz: yig'indisidan birinchi va uchinchidan ikkinchisini ayiramiz:

(36 -35)x ≡ 75 + 42(modl05); x≡117(mod105); x≡12 (mod105).

Keling, umumiy shaklning birinchi darajali taqqoslash tizimini ko'rib chiqaylik

Agar ushbu tizimni ba'zi bir taqqoslashda hech qanday yechim bo'lmasa, u holda tizimning echimlari yo'q. Agar (5) sistemaning har bir taqqoslash echilishi mumkin bo'lsa, uni x uchun yechamiz va (4) ko'rinishdagi ekvivalent sistemani olamiz:

Bu erda (4-teorema, §2).

Xulosa 1, tizimda yechim yo'q yoki bitta yechim mavjud.

Misol:

Tizimning har bir taqqoslashini hal qilib, biz ekvivalent tizimni olamiz

Ushbu tizim bitta yechimga ega - sinf moduli 105. Birinchi taqqoslashni va modulni 3 ga, ikkinchisini esa 35 ga ko'paytirsak, biz olamiz

Ikkinchi taqqoslashdan 11 ga ko'paytirilgan birinchi taqqoslashni ayirib, 2x ≡-62(modl05) ni olamiz, undan x ≡ -31(modl05).

1-darajali taqqoslash tizimini ko'rib chiqishgacha bo'lgan muammolar bizning eramizning boshlarida yashagan Xitoy matematigi Sun Tszining arifmetikasida ko'rib chiqilgan. Uning savoli quyidagi shaklda qo'yilgan: berilgan sonlarga bo'linganda berilgan qoldiqlarni beradigan sonni toping. Shuningdek, u quyidagi teoremaga ekvivalent yechimni beradi.

Teorema (Xitoycha qoldiq teoremasi). m1,m2,…,ms juft tub sonlar bo‘lsin, M = mlm2...ms, b1, b2,…, b lar shunday tanlansin.

Keyin tizimning yechimi

Bu x≡x0 (mod M) kabi ko'rinadi.

Isbot. Chunki biz x0≡ olamiz

Xuddi shunday, biz x0≡c2(mod m2),…, x0≡cs(mod ms), ya’ni x0 hammasini qanoatlantirishini tekshiramiz.

tizim taqqoslashlari.

10. 1-darajali taqqoslashlar. Noaniq tenglamalar

§ 2. 1-darajali taqqoslashlar. Noaniq tenglamalar

1-darajali taqqoslashni ax≡b (mod m) ko'rinishiga keltirish mumkin.

Teorema 4. Agar (a,m) = 1 bo'lsa, taqqoslash ax ≡b(mod m) (2) yagona yechimga ega.

Isbot. 0,1,2,...,m-1 - modulli m qoldiqlarning to'liq sistemasini olaylik. Chunki (a,m) = 1, u holda 0,a,2a,...,(m-1)a ham qoldiqlarning yaxlit sistemasidir (3-teorema, §2, 2-bob). U b moduli m (b bilan bir xil sinfga tegishli) bilan taqqoslanadigan bitta va faqat bitta raqamni o'z ichiga oladi. Bu ax 0 bo'lsin, ya'ni ax 0 € sinf b yoki ax 0 ≡b (mod m). x ≡x 0 (mod m) (2) ning yagona yechimidir. Teorema isbotlangan.

Teorema 5. Agar (a, m)= 1 bo'lsa, ax≡b(mod m) taqqoslash yechimi x 0 ≡a ph (m)-1 b(mod m) sinfdir.

Isbot.(a,m) = 1 bo'lgani uchun Eyler printsipi bo'yicha a ph(m) ≡1(mod m). X 0 ≡a ph (m)-1 b (mod m) taqqoslash (2) yechimi ekanligini ko‘rish oson. Haqiqatan ham, a(a ph (m)-1 b)≡a ph (m) b≡b(mod m). 4-teoremadan kelib chiqadiki, bu yechim yagonadir.

Keling, ko'rib chiqaylik solishtirish yechim usullari ax ≡b (mod m).

1. Tanlash usuli. Modulli m qoldiqlarning to'liq tizimini olib, biz taqqoslashni qanoatlantiradigan raqamlarni tanlaymiz.

2. Eyler teoremasidan foydalanish (5-teorema).

3. Koeffitsientni aylantirish usuli. Biz koeffitsientlarni o'ng tomonni x koeffitsientiga bo'lish uchun aylantirishga harakat qilishimiz kerak. Ko'rib chiqilayotgan o'zgarishlar quyidagilardan iborat: koeffitsientlarni mutlaq eng kichik qoldiqlar bilan almashtirish, b raqamini mutlaq qiymat bilan taqqoslanadigan raqam bilan almashtirish (mutlaq qiymatga ko'paytiriladigan sonni qo'shish), ikkinchisi a ga bo'linishi, harakatlanuvchi a va b dan ular bilan taqqoslanadigan boshqa raqamlarga, umumiy bo'linuvchiga ega bo'ladi va hokazo. Bunda solishtirish xossalari va ularga asoslangan ekvivalent taqqoslashlar bo'yicha teoremalardan foydalanamiz.

1) 223x ≡ 115 (mod ll).

Birinchidan, koeffitsientlarni eng kichik mutlaq qiymat ajratmalari bilan almashtiramiz: 3x ≡ 5 (mod 11). Agar biz teoremadan foydalansak

Demak, Eyler

x≡3 ph(11)-1 *5=3 9 *5≡(3 3) 3 *5≡(27) 3 *5≡5 3 *5≡125*5≡4*5≡9(modll).

Biroq, koeffitsientlarni aylantirish osonroq. O'ng tomonga modulning karrali sonini qo'shish orqali taqqoslashni ekvivalent bilan almashtiramiz:

3x ≡ 5 + 22 (mod 11). Ikkala tomonni 3 raqamiga bo'lib, modulga ko'paytirsak, biz x ≡ 9 (mod l1) ni olamiz.

2) 111x≡ 8 (mod 34).

Biz koeffitsientga aylantirish usulidan foydalanamiz.

(111-3*34)x≡8(mod 34), 9x≡8+34≡42(mod 34), 3x≡14(mod 34), 3x≡14+34≡48(mod 34), x≡16 (mod 34).

Teorema 6. Agar (a, m) = d va b d ga bo'linmasa, (1) taqqoslashning yechimlari yo'q.

Isbot (qarama-qarshilik bilan). X 0 klassi yechim bo'lsin, ya'ni ax 0 ≡b (mod m) yoki (ax 0 -b):m, va demak, (ax 0 -b):d. Lekin a:d, keyin b:d qarama-qarshilikdir. Shuning uchun taqqoslashda hech qanday yechim yo'q.

Teorema 7. Agar (a,m)= d, d>1, b:d bo‘lsa, solishtirish(1) da d bo‘ladi

modul qoldiqlarining bir sinfini tashkil etuvchi va formulalar bo'yicha topilgan eritmalar

Qayerda Bilan yordamchi taqqoslashni qanoatlantiradi

Izoh. Teoremaga ko'ra, taqqoslash (1) quyidagicha yechiladi.

1) (a,m) = d, d> 1 va b:d ekanligiga ishonch hosil qilib, taqqoslashdagi (2) ikkala qismni d ga ajratamiz va a 1 x≡b 1 (mod m 1) yordamchi taqqoslashni olamiz, qayerda. Taqqoslash faqat bitta yechimga ega. c sinfi yechim bo'lsin.

2) Javobni yozing x 0 ≡c(mod m), x 1 ≡c+m 1 (mod m), x 2 ≡c+2m 1 (mod m), … , x d -1 ≡c+(d-1) m 1 (mod m).

Isbot. 2(3) teoremaga muvofiq yordamchi taqqoslash dastlabki taqqoslashga (2) ekvivalentdir. Chunki ( 1, Keyin yordamchi taqqoslash yagona yechimga ega - sinf moduli m 1 = . X≡c(mod m 1) yechim boʻlsin. c moduli m 1 sonlar sinfi moduli m d sinfiga boʻlinadi: .

Haqiqatan ham, x0 moduli m 1 sinfidagi har qanday raqam x 0 +m 1 t ko'rinishga ega. t ni qoldiq bilan d ga bo'ling: t = dq +r, bu erda 0≤r

Demak, taqqoslash (1) m moduli d yechimga ega: x0, x0+m1,..., x0 +(d-1)m1.(yuqorida gorizontal chiziqlar)

Misollar.

1) 20x≡ 15 (mod 108). (20,108) = 4 va 15 4 ga bo'linmaganligi sababli, echimlar yo'q.

2) 20x≡ 44 (mod 108). (20,108) = 4 va 44:4, shuning uchun taqqoslash to'rtta echimga ega. Ikkala qismni va modulni 4 ga bo'lib, biz quyidagilarni olamiz:

5x≡11 (mod 27); 5 x≡11-81 ≡ -70(mod27), x ≡ -14 ≡ 13(mod 27). Keyin x≡13 + 27r (mod 108), bu erda r = 0,1,2,3. men jj

Javob: x≡13(modl08); x ≡ 40 (modl08); x ≡ 67(modl08); x≡94 (modl08).

Taqqoslash nazariyasining noaniq tenglamalarni yechishda qo‘llanilishi

Keling, noaniq yoki boshqacha deyilganidek, ikkita noma'lum ax + by = c bo'lgan birinchi darajali diofant tenglamasini ko'rib chiqaylik, bu erda a, b, c € Z. Bu tenglamani butun sonlarda yechish kerak. Agar (a,b)=d va c d ga bo'linmasa, u holda taqqoslashning butun sonlarda yechimlari yo'qligi aniq. Agar c d ga bo'linadigan bo'lsa, tenglamaning ikkala tomonini d ga bo'ling. Shuning uchun (a, b) =1 bo'lgan holatni ko'rib chiqish kifoya.

ax c dan b ning karrali bilan farq qilganligi uchun ax ≡ c(mod b) bo'ladi (umumiylikni yo'qotmagan holda biz b > 0 deb taxmin qilishimiz mumkin). Bu taqqoslashni yechib, biz x ≡x1 (mod b) yoki x=x1+bt ni olamiz, bu erda t€Z. y ning mos qiymatlarini aniqlash uchun biz a(x1 + bt) + by = c tenglamasiga egamiz, undan

Bundan tashqari, - bu butun son, u x1 ga mos keladigan noma'lum y ning qisman qiymatidir (x1 kabi, t = 0 da chiqadi). Tenglamaning umumiy yechimi esa x=x1+bt, y=y1-at tenglamalar sistemasi ko'rinishida bo'ladi, bu erda t har qanday butun sondir.

Eslatma 1) ax + by = c tenglamasini ≡ c(mod a) dan taqqoslashdan boshlash orqali yechish mumkin edi, chunki by c dan a ning karrali bilan farq qiladi;

2) modul sifatida tanlash qulayroq eng kichik modul a va b.

Misol, 50x – 42y= 34.

Tenglamaning ikkala tomonini 2 ga bo'ling.

25x ≡ 17 (mod2l); 4x ≡ 17 (mod 21) yoki 4x ≡ 17-21 ≡ -4 (mod21).

x ≡ -1 (mod 21), ya'ni x=-1+21t, t€Z. Topilgan x ni tenglamaga almashtiramiz. 25(-1 + 21t)- 21y= 17; 21u =-42 + 25* 21t va u =-2 + 25t.

Noma'lum bir narsa bilan taqqoslash x kabi ko'rinadi

Qayerda. Agar a n ga bo'linmaydi m, bu shunday deyiladi daraja taqqoslashlar.

Qaror bilan taqqoslash har qanday butun sondir x 0 , buning uchun

Agar X 0 solishtirishni qanoatlantirsa, 9 ta taqqoslash xususiyatiga ko'ra, taqqoslanadigan barcha butun sonlar x 0 modul m. Shuning uchun, bir xil qoldiq sinf moduliga tegishli barcha taqqoslash echimlari T, biz buni bitta yechim sifatida ko'rib chiqamiz. Shunday qilib, taqqoslash, uni qanoatlantiradigan qoldiqlarning to'liq tizimining elementlari bo'lsa, shuncha ko'p echimlarga ega.

Yechimlar to‘plami mos keladigan taqqoslashlar deyiladi ekvivalent.

2.2.1 Birinchi darajali taqqoslashlar

Bir noma'lum bilan birinchi darajali taqqoslash X kabi ko'rinadi

(2.2)

2.4 teorema. Taqqoslash kamida bitta yechimga ega bo'lishi uchun bu raqam zarur va etarli b GCD ga bo'lingan ( a, m).

Isbot. Avval biz zaruratni isbotlaymiz. Mayli d = GCD( a, m) Va X 0 - taqqoslash yechimi. Keyin , ya'ni farq Oh 0 − b tomonidan bo'linadi T. Shunday qilib, bunday butun son mavjud q, Nima Oh 0 − b = qm. Bu yerdan b= ah 0 − qm. Va shundan beri d, umumiy bo'luvchi sifatida sonlarni ajratadi A Va T, keyin minuend va subtrahend ga bo'linadi d, va shuning uchun b tomonidan bo'linadi d.

Endi etarliligini isbotlaylik. Mayli d- sonlarning eng katta umumiy bo'luvchisi A Va T, Va b tomonidan bo'linadi d. Keyin, bo'linish ta'rifiga ko'ra, quyidagi butun sonlar mavjud a 1 , b 1 , T 1 , Nima .

Kengaytirilgan Evklid algoritmidan foydalanib, 1 = gcd( sonining chiziqli tasvirini topamiz. a 1 , m 1 ):

ba'zilar uchun x 0 , y 0 . Oxirgi tenglikning ikkala tomonini ga ko'paytiramiz b 1 d:

yoki bir xil narsa,

ya'ni va taqqoslashning yechimidir. □

2.10-misol. Taqqoslash 9 X= 6 (mod 12) yechimga ega, chunki gcd(9, 12) = 3 va 6 3 ga boʻlinadi. □

2.11-misol. Taqqoslash 6x= 9 (mod 12) hech qanday yechimga ega emas, chunki gcd(6, 12) = 6 va 9 6 ga boʻlinmaydi. □

2.5 teorema. Taqqoslash (2.2) yechiladigan bo'lsin va d = GCD( a, m). Keyin taqqoslash yechimlari to'plami (2.2) dan iborat d modul qoldiqlari sinflari T, ya'ni, agar X 0 - yechimlardan biri, keyin qolgan barcha yechimlar

Isbot. Mayli X 0 - taqqoslash yechimi (2.2), ya'ni Va , . Shunday qilib, bunday narsa bor q, Nima Oh 0 − b = qm. Endi o'rniga oxirgi tenglikni almashtirish X 0 shaklning ixtiyoriy yechimi, bu yerda ifodani olamiz

, ga bo'linadi m. □

2.12-misol. Taqqoslash 9 X=6 (mod 12) uchta yechimga ega, chunki gcd(9, 12)=3. Ushbu yechimlar: X 0 = 2, x 0 + 4 = 6, X 0 + 2∙4=10.□

2.13-misol. Taqqoslash 11 X=2 (mod 15) noyob yechimga ega X 0 = 7, chunki GCD(11,15)=1.□

Biz sizga birinchi darajali taqqoslashni qanday hal qilishni ko'rsatamiz. Umumiylikni yo'qotmasdan, biz GCD ( a, t) = 1. Keyin (2.2) taqqoslash yechimini, masalan, Evklid algoritmidan foydalanib izlash mumkin. Haqiqatan ham, kengaytirilgan Evklid algoritmidan foydalanib, biz 1 raqamini raqamlarning chiziqli birikmasi sifatida ifodalaymiz. a Va T:

Keling, bu tenglikning ikkala tomonini ko'paytiramiz b, olamiz: b = abq + mrb, qayerda abq - b = - mrb, ya'ni a ∙ (bq) = b(mod m) Va bq- taqqoslash yechimi (2.2).

Yana bir yechim Eyler teoremasidan foydalanishdir. Yana ishonamizki, GCD(a, T)= 1. Eyler teoremasini qo‘llaymiz: . Taqqoslashning ikkala tomonini ko'paytiring b: . Oxirgi ifodani quyidagicha qayta yozish , biz taqqoslashning yechimi ekanligini olamiz (2.2).

Keling, GCD( a, m) = d>1. Keyin a = atd, m = mtd, bu erda GCD( A 1 , m 1) = 1. Bundan tashqari, zarur b = b 1 d, solishtirish echilishi mumkin bo'lishi uchun. Agar X 0 - taqqoslash yechimi A 1 x = b 1 (mod m 1) va yagona, chunki GCD( A 1 , m 1) = 1, keyin X 0 yechim va taqqoslash bo‘ladi A 1 xd = db 1 (mod m 1), ya'ni dastlabki taqqoslash (2.2). Dam olish d- 2.5-teorema bo'yicha 1 ta yechim topilgan.

Bir noma'lum bilan birinchi darajali taqqoslash quyidagi shaklga ega:

f(x) 0 (mod m); f(X) = Oh + va n. (1)

Taqqoslashni hal qiling- x ning uni qanoatlantiradigan barcha qiymatlarini topishni bildiradi. X ning bir xil qiymatlarini qondiradigan ikkita taqqoslash deyiladi ekvivalent.

Agar taqqoslash (1) har qanday bilan qanoatlansa x = x 1, keyin (49 ga ko'ra) barcha raqamlar bilan solishtirish mumkin x 1, modul m: x x 1 (mod m). Bu butun sonlar sinfi hisoblanadi bitta yechim. Bunday kelishuv bilan quyidagi xulosaga kelish mumkin.

66.C tekislash (1) to'liq tizimning uni qanoatlantiradigan qoldiqlari soni qancha bo'lsa, shuncha yechimga ega bo'ladi.

Misol. Taqqoslash

6x– 4 0 (mod 8)

0, 1,2, 3, 4, 5, 6, 7 raqamlari orasida ikkita raqam modul 8 qoldiqlarining to'liq tizimini qondiradi: X= 2 va X= 6. Demak, bu taqqoslash ikkita yechimga ega:

x 2 (mod 8), X 6 (mod 8).

Erkin terminni (qarama-qarshi belgi bilan) o'ng tomonga siljitish orqali birinchi darajani solishtirish shaklga qisqartirilishi mumkin.

bolta b(mod m). (2)

Shartni qondiradigan taqqoslashni ko'rib chiqing ( A, m) = 1.

66 ga ko'ra, bizning taqqoslashimiz uni qondiradigan to'liq tizimning qoldiqlari qancha ko'p bo'lsa, shuncha ko'p echimlarga ega. Lekin qachon x modul qoldiqlarining to'liq tizimidan o'tadi T, Bu Oh chegirmalarning to'liq tizimidan o'tadi (60 tadan). Shuning uchun, bitta va faqat bitta qiymat uchun X, to'liq tizimdan olingan, Oh bilan solishtirish mumkin bo'ladi b. Shunday qilib,

67. Qachon (a, m) = 1 taqqoslash bolta b(mod m)bitta yechimga ega.

Keling, ( a, m) = d> 1. So'ngra, taqqoslash uchun (2) yechimlarga ega bo'lish uchun (55 tadan) kerak bo'ladi. b tomonidan bo'linadi d, aks holda (2) ni har qanday butun x uchun taqqoslash mumkin emas . Shuning uchun faraz qilish b karrali d, qo'yaylik a = a 1 d, b = b 1 d, m = m 1 d. Keyin taqqoslash (2) bunga ekvivalent bo'ladi (qisqartirilgan d): a 1 x b 1 (mod m), unda allaqachon ( A 1 , m 1) = 1, va shuning uchun u bitta yechim moduliga ega bo'ladi m 1 . Mayli X 1 - bu eritmaning eng kichik manfiy bo'lmagan qoldig'i moduli m 1 , u holda barcha raqamlar x bo'ladi , bu yechimni hosil qilish shaklida topiladi

x x 1 (mod m 1). (3)

Modulo m, raqamlar (3) bitta yechimni emas, balki 0, 1, 2 qatoridagi raqamlar (3) qancha bo'lsa, shuncha ko'p yechim hosil qiladi, ..., m - 1 ta eng kam salbiy bo'lmagan modul qoldiqlari m. Ammo bu erda quyidagi raqamlar (3) tushadi:

x 1 , x 1 + m 1 , x 1 + 2m 1 , ..., x 1 + (d – 1) m 1 ,

bular. Jami d raqamlar (3); shuning uchun (2) taqqoslash mavjud d qarorlar.

Biz teoremani olamiz:

68. (a, m) = d bo'lsin. Taqqoslash ax b ( mod m) mumkin emas, agar b d ga bo'linmasa. Agar b d ning karrali bo'lsa, taqqoslash d yechimga ega bo'ladi.

69. Davomli kasrlar nazariyasiga asoslangan birinchi darajali taqqoslashlarni yechish usuli:

Munosabatni davomli kasrga kengaytirish m:a,

va oxirgi ikkita mos keladigan kasrlarga qarab:

davom etgan kasrlarning xususiyatlariga ko'ra (bo'yicha 30 ) bizda ... bor

Shunday qilib, taqqoslashning yechimi bor

topish uchun, bu hisoblash uchun etarli Pn– 30-bandda ko‘rsatilgan usul bo‘yicha 1.

Misol. Keling, taqqoslashni hal qilaylik

111x= 75 (mod 321). (4)

Bu erda (111, 321) = 3 va 75 3 ga karrali. Shuning uchun taqqoslash uchta yechimga ega.

Taqqoslashning ikkala tomonini va modulni 3 ga bo'lib, biz taqqoslashni olamiz

37x= 25 (mod 107), (5)

birinchi navbatda hal qilishimiz kerak. Bizda ... bor

q
P 3

Shunday qilib, bu holatda n = 4, P n - 1 = 26, b= 25 va bizda (5) ko'rinishda taqqoslash uchun yechim mavjud

x–26 ∙ 25 99 (mod 107).

Shunday qilib, (4) taqqoslash uchun echimlar quyidagicha taqdim etiladi:

X 99; 99 + 107; 99 + 2 ∙ 107 (mod 321),

Xº99; 206; 313 (mod 321).

Berilgan modul bo'yicha teskari elementni hisoblash

70.Agar sonlar butun son bo'lsa a Va n ko‘paytma bo‘lsa, u holda son bo‘ladi a', taqqoslashni qondirish a ∙ a′ ≡ 1 (mod n). Raqam a' chaqirdi n modulining multiplikativ teskarisi va buning uchun ishlatiladigan belgi a- 1 (mod n).

Muayyan qiymat moduli bo'yicha o'zaro miqdorlarni hisoblash birinchi darajani noma'lum bilan taqqoslashni hal qilish orqali amalga oshirilishi mumkin, bunda x qabul qilingan raqam a'.

Taqqoslash yechimini topish uchun

a∙x≡ 1(mod m),

qayerda ( a, m)= 1,

Evklid algoritmidan (69) yoki Ferma-Eyler teoremasidan foydalanishingiz mumkin, bu esa agar ( a, m) = 1, keyin

a φ( m) ≡ 1 (mod m).

x ≡ a φ( m)–1 (mod m).

Guruhlar va ularning xususiyatlari

Guruhlar umumiy xarakterli xossalarga ega boʻlgan matematik tuzilmalarni tasniflashda qoʻllaniladigan taksonomik sinflardan biridir. Guruhlar ikkita komponentdan iborat: bir guruh (G) Va operatsiyalar() ushbu to'plamda aniqlangan.

To'plam, element va a'zolik tushunchalari zamonaviy matematikaning aniqlanmagan asosiy tushunchalaridir. Har qanday to'plam tarkibiga kiradigan elementlar bilan belgilanadi (ular, o'z navbatida, to'plamlar ham bo'lishi mumkin). Shunday qilib, biz to'plam aniqlangan yoki berilgan deb aytamiz, agar biron bir element uchun uning ushbu to'plamga tegishli yoki yo'qligini aniqlay olsak.

Ikki to'plam uchun A, B yozuvlar B A, B A, B∩ A, B A, B \ A, A × B mos ravishda shuni anglatadi B to‘plamning kichik to‘plamidir A(ya'ni har qanday element B tarkibida ham mavjud A, masalan, natural sonlar to'plami haqiqiy sonlar to'plamida joylashgan; bundan tashqari, har doim A A), B to‘plamning tegishli to‘plamidir A(bular. B A Va B ≠ A), ko'pchilikning kesishishi B Va A(ya'ni, bir vaqtning o'zida joylashgan barcha elementlar A, va ichida B, masalan, butun sonlar va musbat haqiqiy sonlarning kesishishi natural sonlar toʻplami), toʻplamlar birligi B Va A(ya'ni, ichida joylashgan elementlardan tashkil topgan to'plam A, yoki ichida B), farqni belgilang B Va A(ya'ni, unda joylashgan elementlar to'plami B, lekin yolg'on gapirmang A), to‘plamlarning dekart ko‘paytmasi A Va B(ya'ni, shaklning juftliklari to'plami ( a, b), Qayerda a A, b B). | orqali A| to'plamning kuchi doimo belgilanadi A, ya'ni. to'plamdagi elementlar soni A.