Számok összehasonlítása modulo

Felkészítő: Irina Zutikova

MAOU "Líceum No. 6"

osztály: 10 "a"

Tudományos témavezető: Zheltova Olga Nikolaevna

Tambov

2016

• Probléma
• Projekt célja
• Hipotézis
• A projekt céljai és megvalósítási terve
• Összehasonlítások és tulajdonságaik
• Példák problémákra és megoldásaikra
• Használt oldalak és irodalom

Probléma:

A legtöbb diák ritkán alkalmaz modulo szám-összehasonlítást nem szabványos és olimpiai feladatok megoldására.

Projekt célja:

Mutasd meg, hogyan oldhatsz meg nem szabványos és olimpiai feladatokat a számok összehasonlításával modulo.

Hipotézis:

A „Számok összehasonlítása modulo” témakör mélyebb tanulmányozása segít a tanulóknak néhány nem szabványos és olimpiai feladat megoldásában.

A projekt céljai és megvalósítási terve:

1. Tanulmányozza részletesen a „Számok összehasonlítása modulo” témát.

2. Oldjon meg több nem szabványos és olimpiai feladatot a számok modulo összehasonlításával!

3. Készítsen feljegyzést a tanulók számára a „Számok összehasonlítása modulo” témában.

4. Tartson leckét „Számok összehasonlítása modulo” témában a 10. „a” osztályban.

5. Adjon házi feladatot az osztálynak a „Modulonkénti összehasonlítás” témában.

6. Hasonlítsa össze a feladat elvégzéséhez szükséges időt a „Modulonkénti összehasonlítás” témakör tanulmányozása előtt és után.

7. Következtetések levonása.

Mielőtt elkezdtem volna részletesen tanulmányozni a „Számok összehasonlítása modulo” témát, úgy döntöttem, hogy összehasonlítom, hogyan jelenik meg a különböző tankönyvekben.

• Az algebra és a matematikai elemzés kezdetei. Haladó szint. 10. osztály (Yu.M. Kolyagin és mások)
• Matematika: algebra, függvények, adatelemzés. 7. osztály (L.G. Peterson és mások)
• Az algebra és a matematikai elemzés kezdetei. Profil szint. 10. osztály (E.P. Nelin és mások)
• Az algebra és a matematikai elemzés kezdetei. Profil szint. 10. osztály (G.K. Muravin és mások)

Mint megtudtam, egyes tankönyvek az emelt szint ellenére sem érintik ezt a témát. A témát pedig L. G. Peterson tankönyve mutatja be a legvilágosabban és legközönségesebben (Fejezet: Bevezetés az oszthatóság elméletébe), ezért próbáljuk meg megérteni a „Számok összehasonlítása modulo”-t, a tankönyv elméletére támaszkodva.

Összehasonlítások és tulajdonságaik.

Meghatározás: Ha két a és b egész számnak ugyanaz a maradéka, ha elosztjuk valamilyen m egész számmal (m>0), akkor azt mondják, hogya és b összehasonlítható modulo més írja be:

Tétel: akkor és csak akkor, ha a és b különbsége osztható m-rel.

Tulajdonságok:

1. Az összehasonlítások reflexivitása.Bármely a szám összehasonlítható önmagával modulo m (m>0; a,m egész számok).
2. Szimmetrikus összehasonlítások.Ha az a szám összehasonlítható a b modulo m számmal, akkor a b szám összehasonlítható a modulo m számmal (m>0; a,b,m egész szám).
3. Az összehasonlítások tranzitivitása.Ha az a szám összehasonlítható a b modulo m számmal, és a b szám összehasonlítható a c számmal modulo ugyanaz a modulo, akkor az a szám összehasonlítható a c modulo m számmal (m>0; a,b,c ,m egész számok).
4. Ha az a szám összehasonlítható a b modulo m számmal, akkor az a szám n számmal összehasonlítható b n modulo m(m>0; a,b,m-egészek; n-természetes szám).

Példák problémákra és megoldásaikra.

1. Keresse meg a 3-as szám utolsó számjegyét 999 .

Megoldás:

Mert A szám utolsó számjegye a maradék, ha elosztjuk 10-zel, akkor

3 999 = 3 3 * 3 996 = 3 3 * (3 4 ) 249 = 7 * 81 249 7 (10. mód)

(Mert 34=81 1(mod 10);81 n 1 (mod10) (tulajdon szerint))

Válasz: 7.

2.Bizonyítsa be, hogy 2 4n -1 maradék nélkül osztható 15-tel. (Phystech2012)

Megoldás:

Mert 16 1 (mod 15), akkor

16n-1 0(mod 15) (tulajdon szerint); 16n= (2 4) n

2 4n -1 0 (mod 15)

3. Bizonyítsa be, hogy 12 2n+1 +11 n+2 Osztható 133-mal maradék nélkül.

Megoldás:

12 2n+1 =12*144 n 12*11 n (133. mód) (tulajdon szerint)

12 2n+1 +11 n+2 =12*11 n +11 n *121=11 n *(12+121) =11 n *133

Szám (11n *133) osztja 133-mal maradék nélkül, ezért (12 2n+1 +11 n+2 ) maradék nélkül osztható 133-mal.

4. Határozzuk meg a 2-es szám maradékát osztva 15-tel! 2015 .

Megoldás:

16 1 óta (mod 15), majd

2, 2015 8 (15. mód)

Válasz: 8.

5. Keresse meg az osztás maradékát a 17-es 2-es számmal 2015. (Phystech2015)

Megoldás:

2 2015 =2 3 *2 2012 =8*16 503

Mivel 16 -1 (mod 17), akkor

2 2015 -8 (15. mód)

8 9 (17. mód)

Válasz: 9.

6. Bizonyítsuk be, hogy a szám 11 100 -1 osztható 100-zal maradék nélkül. (Phystech2015)

Megoldás:

11 100 =121 50

121 50 21 50 (100-as mód) (tulajdon szerint)

21 50 =441 25

441 25 41 25 (100-as mód) (tulajdon szerint)

41 25 =41*1681 12

1681 12 (-19) 12 (100-as mód) (tulajdon szerint)

41*(-19) 12 =41*361 6

361 6 (-39) 6 (100. mód) (tulajdon szerint)

41*(-39) 6 =41*1521 3

1521 3 21 3 (mod100) (tulajdon szerint)

41*21 3 =41*21*441

441 41 (mod 100) (tulajdon szerint)

21*41 2 =21*1681

1681 -19 (mod 100) (tulajdon szerint)

21*(-19)=-399

399 1 (mod 100) (tulajdon szerint)

Tehát 11 100 1 (mod 100)

11 100 -1 0 (mod 100) (tulajdon szerint)

7. Három szám van megadva: 1771,1935,2222. Keress egy olyan számot, amelyet elosztva a három megadott szám maradékai egyenlőek lesznek. (HSE2016)

Megoldás:

Legyen az ismeretlen szám egyenlő a-val

2222 1935 (a mód); 1935 1771 (mod a); 2222 1771 (a mód)

2222-1935 0(moda) (tulajdon szerint); 1935-17710(moda) (tulajdon szerint); 2222-17710 (moda) (tulajdon szerint)

287 0 (a mód); 164 0 (a mód); 451 0 (a mód)

287-164 0(moda) (tulajdon szerint); 451-2870(moda)(tulajdonság szerint)

123 0 (a mód); 164 0 (a mód)

164-123 0(mod a) (tulajdon szerint)

41

EBK Olimpia 2016

n-nél ugyanazt a maradékot adják.

Egyenértékű megfogalmazások: a és b modulusban összehasonlítható n ha különbségük a - b osztható n-nel, vagy ha a ábrázolható mint a = b + kn , Hol k- néhány egész szám. Például: 32 és -10 összehasonlítható modulo 7, mivel

Az „a és b összehasonlítható modulo n” állítás a következőképpen írható:

Modulo egyenlőség tulajdonságai

A modulo összehasonlító relációnak vannak tulajdonságai

Bármely két egész szám aÉs b hasonló modulo 1.

A számok érdekében aÉs b modulusban összehasonlíthatóak voltak n, szükséges és elégséges, hogy különbségük osztható legyen n.

Ha a és számok páronként modulusban összehasonlíthatók n, akkor azok összegei és , valamint a termékek és modulusban is összehasonlíthatóak n.

Ha a számok aÉs b modulusban összehasonlítható n, majd a diplomáikat a kÉs b k modulusban is összehasonlíthatóak n alatt bármilyen természetes k.

Ha a számok aÉs b modulusban összehasonlítható n, És n osztva m, Azt aÉs b modulusban összehasonlítható m.

A számok érdekében aÉs b modulusban összehasonlíthatóak voltak n, amelyet az egyszerű tényezőkre történő kanonikus bontás formájában mutatunk be p én

szükséges és elegendő ahhoz

Az összehasonlító reláció egy ekvivalencia reláció, és a közönséges egyenlőségek számos tulajdonságával rendelkezik. Például összeadhatók és szorozhatók: ha

Az összehasonlítások azonban általában véve nem oszthatók sem egymással, sem más számokkal. Példa: azonban 2-vel csökkentve hibás összehasonlítást kapunk: . Az összehasonlítások rövidítési szabályai a következők.

Nem végezhet műveleteket az összehasonlításokon sem, ha azok moduljai nem egyeznek.

Egyéb tulajdonságok:

Kapcsolódó definíciók

Levonási osztályok

Az összes szám halmaza összehasonlítható a modulo n hívott levonási osztály a modulo n , és általában a [ a] n vagy . Így az összehasonlítás egyenértékű a maradékosztályok egyenlőségével [a] n = [b] n .

A modulo összehasonlítás óta n egy ekvivalencia reláció az egész számok halmazán, akkor a maradék osztályok modulo n ekvivalencia osztályokat képviselnek; számuk egyenlő n. Az összes maradék osztály halmaza modulo n vagy jelöli.

Az indukálással történő összeadás és szorzás műveletei megfelelő műveleteket adnak a halmazon:

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

Ezekre a műveletekre nézve a halmaz véges gyűrű, és ha n egyszerű - véges mező.

Levonási rendszerek

A maradékrendszer lehetővé teszi számtani műveletek végrehajtását egy véges számhalmazon anélkül, hogy túllépné annak határait. Teljes levonási rendszer A modulo n bármely n egész számból álló halmaz, amely összehasonlíthatatlan modulo n. Általában a legkisebb, nem negatív maradékokat a maradékok teljes rendszerének tekintik modulo n

0,1,...,n − 1

vagy a számokból álló abszolút legkisebb levonások

,

páratlan esetén nés számok

páros esetén n .

Összehasonlítások megoldása

Az első fok összehasonlítása

A számelméletben, a kriptográfiában és más tudományterületeken gyakran felmerül a forma első fokú összehasonlításának megoldásának problémája:

Egy ilyen összehasonlítás megoldása a gcd kiszámításával kezdődik (a, m)=d. Ebben az esetben 2 eset lehetséges:

• Ha b nem többszörös d, akkor az összehasonlításnak nincs megoldása.
• Ha b több- d, akkor az összehasonlításnak egyedi megoldási modulja van m / d, vagy mi ugyanaz, d modulo megoldások m. Ebben az esetben az eredeti összehasonlítás csökkentésének eredményeként d az összehasonlítás a következő:

Ahol a 1 = a / d , b 1 = b / d És m 1 = m / d egész számok, és a 1 és m 1 viszonylag első számú. Ezért a szám a 1 modulo megfordítható m 1, azaz keressen egy ilyen számot c, hogy (más szóval ). Most úgy találjuk meg a megoldást, hogy az eredményül kapott összehasonlítást megszorozzuk c:

Gyakorlati értékszámítás c többféleképpen is megvalósítható: Euler-tétel, Euklidész algoritmus, a folytonos törtek elmélete (lásd algoritmus) stb. segítségével. Az Euler-tétel lehetővé teszi az érték feljegyzését. c formában:

Példa

Összehasonlításképpen megvan d= 2, tehát modulo 22 az összehasonlításnak két megoldása van. Cseréljük le a 26-ot 4-gyel, ami hasonló a modulo 22-höz, majd csökkentsük mind a 3 számot 2-vel:

Mivel a 2 a 11. modul másodpímje, a bal és a jobb oldalt csökkenthetjük 2-vel. Ennek eredményeként egy modulo 11: megoldást kapunk, amely két modulo 22: megoldásnak felel meg.

A másodfokú összehasonlítások

A másodfokú összehasonlítások megoldása abból áll, hogy kiderítjük, hogy egy adott szám másodfokú maradék-e (a másodfokú reciprocitás törvénye alapján), majd kiszámítjuk a modulo négyzetgyökét.

Történet

A sok évszázada ismert kínai maradéktétel kimondja (a modern matematikai nyelven), hogy a maradékgyűrű modulo több másodpímszám szorzata

Az elsőfokú összehasonlítás egy ismeretlennel a következő formában történik:

f(x) 0 (mód m); f(X) = Ó + és n. (1)

Összehasonlítás megoldása- azt jelenti, hogy meg kell találni x minden olyan értékét, amely kielégíti azt. Két olyan összehasonlítást hívunk, amelyek megfelelnek az x azonos értékeinek egyenértékű.

Ha az (1) összehasonlítást bármely x = x 1, akkor (a 49 szerint) minden szám összehasonlítható x 1, modulo m: x x 1 (mod m). Ezt az egész számosztályt annak tekintjük egy megoldás. Egy ilyen megállapodás alapján a következő következtetés vonható le.

66.C igazítás (1) annyi megoldása lesz, ahány maradék a teljes rendszerben kielégíti.

Példa. Összehasonlítás

6x– 4 0 (8. mód)

A 0, 1,2, 3, 4, 5, 6, 7 számok közül két szám felel meg a 8. modulo maradékanyag-rendszerének: X= 2 és X= 6. Ezért ennek az összehasonlításnak két megoldása van:

x 2 (8. mód), X 6 (8. mód).

Az első fokozat összehasonlítása a szabad tag (ellentétes előjelű) jobb oldalra mozgatásával redukálható a formára

fejsze b(mod m). (2)

Vegyünk egy összehasonlítást, amely kielégíti a feltételt ( A, m) = 1.

A 66 szerint összehasonlításunkban annyi megoldás van, ahány maradéka a teljes rendszernek kielégíti. De mikor x végigfut a modulo maradékok teljes rendszerén T, Hogy Ó végigfut a teljes levonási rendszeren (60-ból). Ezért egy és csak egy értékre X, a teljes rendszerből átvéve, Óösszehasonlítható lesz b.Így,

67. Amikor (a, m) = 1 összehasonlító ax b(mod m)egy megoldása van.

Hagyd most ( a, m) = d> 1. Ezután a (2) összehasonlításhoz, hogy megoldásai legyenek, szükséges (55-ből), hogy b osztva d, különben a (2) összehasonlítás nem lehetséges bármely x egész számra . Feltéve tehát b többszörösei d, tegyük fel a = a 1 d, b = b 1 d, m = m 1 d. Ekkor a (2) összehasonlítás ezzel lesz ekvivalens (rövidítve d): a 1 x b 1 (mod m), amelyben már ( A 1 , m 1) = 1, és ezért egy modulo megoldása lesz m 1. Hadd X 1 – ennek az oldatnak a legkisebb nemnegatív maradéka modulo m 1 , akkor minden szám x , formában találjuk meg ezt a megoldást

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

Modulo m, a (3) számok nem egy megoldást alkotnak, hanem többet, pontosan annyi megoldást, ahány (3) szám van a 0, 1, 2 sorozatban, ..., m – 1 legkevesebb nem negatív modulo maradék m. De a következő számok (3) esnek ide:

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

azok. teljes d számok (3); ezért a (2) összehasonlításban szerepel d döntéseket.

Megkapjuk a tételt:

68. Legyen (a, m) = d. Összehasonlító ax b ( mod m) lehetetlen, ha b nem osztható d-vel. Ha b d többszöröse, az összehasonlításnak d megoldása van.

69. A folytonos törtek elméletén alapuló elsőfokú összehasonlítások megoldására szolgáló módszer:

A reláció folyamatos törtjére bővítve m:a,

és megnézzük az utolsó két egyező törtet:

a folytonos frakciók tulajdonságai szerint (szerint 30 ) van

Tehát az összehasonlításnak van megoldása

megtalálni, ami elég a kiszámításhoz Pn– 1 a 30. pontban meghatározott módszer szerint.

Példa. Oldjuk meg az összehasonlítást

111x= 75 (321. mód). (4)

Itt (111, 321) = 3, és 75 a 3 többszöröse. Ezért az összehasonlításnak három megoldása van.

Az összehasonlítás és a modulus mindkét oldalát elosztva 3-mal, megkapjuk az összehasonlítást

37x= 25 (107. mód), (5)

amelyet először meg kell oldanunk. megvan

q
P 3

Tehát ebben az esetben n = 4, P n – 1 = 26, b= 25, és van megoldásunk az (5) összehasonlításra a formában

x–26 ∙ 25 99 (107-es mód).

Ezért a (4) összehasonlítás megoldásai a következők:

X 99; 99 + 107; 99 + 2∙ 107 (321-es mód),

Xº99; 206; 313 (321. mód).

Az inverz elem számítása adott modulóval

70.Ha a számok egész számok aÉs n másodprím, akkor van egy szám a', kielégítve az összehasonlítást a ∙ a′ ≡ 1 (mod n). Szám a' hívott egy modulo n multiplikatív inverzeés az ehhez használt jelölés az a- 1 (mod n).

A reciprok mennyiségek számítása modulo egy bizonyos értékhez úgy végezhető el, hogy megoldjuk az elsőfokú ismeretlennel való összehasonlítását, amelyben x szám elfogadva a'.

Összehasonlító megoldást találni

a∙x≡ 1 (mod m),

hol ( a,m)= 1,

használhatja az Euclid algoritmust (69) vagy a Fermat-Euler tételt, amely kimondja, hogy ha ( a,m) = 1, akkor

a φ( m) ≡ 1 (mód m).

x ≡ a φ( m)–1 (mód m).

Csoportok és tulajdonságaik

A csoportok a közös jellemző tulajdonságokkal rendelkező matematikai szerkezetek osztályozására használt taxonómiai osztályok egyike. A csoportok két összetevőből állnak: sok (G) És műveleteket() meghatározva ezen a halmazon.

A halmaz, elem és tagság fogalma a modern matematika meghatározatlan alapfogalma. Bármely halmazt a benne lévő elemek határozzák meg (amelyek viszont halmazok is lehetnek). Így azt mondjuk, hogy egy halmaz definiált vagy adott, ha bármely elemről meg tudjuk mondani, hogy ebbe a halmazba tartozik-e vagy sem.

Két szetthez A, B rekordokat B A, B A, B∩ A, B A, B \ A, A × B illetve azt jelenti B a halmaz egy részhalmaza A(azaz bármely elem a B is benne van A, például a természetes számok halmazát a valós számok halmaza tartalmazza; ráadásul mindig A A), B a halmaz megfelelő részhalmaza A(azok. B AÉs B ≠ A), halmazok metszéspontja BÉs A(azaz minden olyan elem, amely egyszerre van benne A, és be B például az egész számok és a pozitív valós számok metszéspontja a természetes számok halmaza), a halmazok uniója BÉs A(vagyis olyan elemekből álló halmaz, amelyekben vagy A, vagy benne B), állítsa be a különbséget BÉs A(azaz a benne rejlő elemek halmaza B, de ne feküdj be A), halmazok derékszögű szorzata AÉs B(azaz a(z) alak párjainak halmaza a, b), Hol a A, b B). Via | A| mindig a halmaz számosságát jelöli A, azaz a készlet elemeinek száma A.

A művelet egy szabály, amely szerint egy halmaz bármely két eleme G(aÉs b) illeszkedik a G harmadik eleméhez: a b.

Sok elem G művelettel ún csoport, ha a következő feltételek teljesülnek.

Tekintsük az összehasonlítás rendszerét

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

1. tétel. Legyen M = az m1,m2,…,ms számok legkisebb közös többszöröse. Ha egy kielégíti a (2) rendszert, akkor az a modulo M osztály bármely száma kielégíti ezt a rendszert.

Bizonyíték. Legyen b€ az a osztályba. Mivel a ≡ b(mod M), akkor a ≡b(mod m), i= 1,2,...,s (16. összehasonlítási tulajdonság). Következésképpen b, mint a, kielégíti a rendszer minden összehasonlítását, ami bizonyítja a tételt. Ezért természetes, hogy a (2) rendszer megoldását modulo M osztálynak tekintjük.

Meghatározás. Az összehasonlítások rendszerének megoldása(2) a modulo M = számok osztálya, amelyek kielégítik a rendszer minden összehasonlítását.

12. Azonnal jegyezzük meg, hogy a páratlan számok nem elégítik ki a második összehasonlítást. A modulo 12 maradékok teljes rendszeréből páros számokat véve, közvetlen ellenőrzéssel meggyőződhetünk arról, hogy a 2, -2, 6 számok kielégítik a 2. összehasonlítást, és a rendszernek két megoldása van: x ≡ 2(mod l2), x ≡ - 2 (12. mód).

Tekintsük az I. fokú összehasonlítási rendszert (3)

2. tétel. Legyen d=(m1,m2), M = .

Ha c1 - c2 nem osztható d-vel, akkor a (3) rendszernek nincs megoldása.

Ha (c1 -c2):d, akkor a (3) rendszernek van egy megoldása - egy modulo M osztály.

Bizonyíték. Az 1. összehasonlításból x = c1+m1t, t€Z. Helyettesítse a 2. összehasonlítást: с1+ m1t ≡ c2(mod m2) ill.

m1t ≡ c2-cl (mod m2). Ennek az összehasonlításnak csak akkor van megoldása, ha (c2 – c1): d.

A megoldás pedig egy modulo osztály (4. tétel a 2. §-ból).

Legyen a megoldás , azaz ahol k€Z.

M== , azaz x≡c1+m1t0(mod M) a megoldás

Példák.

1. :2, a rendszernek egy modulo 24 megoldási osztálya van. Az 1. összehasonlításból x =2+6t. Ha x-et behelyettesítünk a 2. összehasonlításba, a következőt kapjuk: 2 + 6t≡ 4(tnod 8); 6t≡ 2 (8. mód); -2t≡2(mod8); t≡-1 (mod 4); t=-1+4k; x=2+6(-1+4k); x=-4+24k, azaz x≡-4 (mod 24).

2. A 7-3 nem osztható 3-mal, a rendszernek nincs megoldása.

Következmény 1.Összehasonlító rendszer (4)

Vagy nincs megoldása, vagy van egy megoldása – egy modulo M= osztály.

Bizonyíték. Ha az első két összehasonlítás rendszerének nincsenek megoldásai, akkor a (4)-nek nincsenek megoldásai. Ha van megoldása x ≡ a(mod), akkor ehhez az összehasonlításhoz hozzáadva a rendszer harmadik összehasonlítását, ismét egy (3) alakú rendszert kapunk, amelynek vagy egy megoldása van, vagy nincs megoldása. Ha van megoldása, akkor így folytatjuk mindaddig, amíg ki nem használjuk a (4) rendszer összes összehasonlítását. Ha van megoldás, akkor ez egy modulo M osztály.

Megjegyzés. Az LCM tulajdonság itt használatos: =.

Következmény 2. Ha m1,m2,…,ms páronként koprím, akkor a (4) rendszernek egy megoldása van - M=m1m2…ms modulo osztály.

Példa:

Mivel a modulok páronként viszonylag egyszerűek, a rendszernek egyetlen megoldása van - modulo class 105 = 5*3*7. Az első összehasonlításból

Behelyettesítjük a második összehasonlításba: 2 +5t≡ 0(mod 3) vagy 2t≡-2(mod3), t=-1+3k, x=2+5(-1+3k), x=-3+15k . Helyettesítsük be a harmadik összehasonlítást:

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

Találkozzunk mások ennek a rendszernek a megoldási módja, (Azt használjuk, hogy a rendszernek egy megoldása van.) Az első összehasonlítás mindkét részét és modulját szorozzuk 21-gyel, a másodikat 35-tel, a harmadikat pedig 15-tel: a első és harmadik kivonjuk a másodikat:

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

Tekintsük most az általános forma első fokának összehasonlító rendszerét

Ha ennek a rendszernek néhány összehasonlítása nem rendelkezik megoldással, akkor a rendszernek nincsenek megoldásai. Ha az (5) rendszer minden összehasonlítása megoldható, akkor megoldjuk x-re, és egy (4) alakú ekvivalens rendszert kapunk:

Hol (4. tétel, 2. §).

Az 1. következmény szerint a rendszernek vagy nincs megoldása, vagy csak egy megoldása van.

Példa:

A rendszer minden összehasonlítását megoldva egy ekvivalens rendszert kapunk

Ennek a rendszernek egy megoldása van - osztály modulo 105. Az első összehasonlítást és a modulust 3-mal, a másodikat 35-tel megszorozva kapjuk

Az első összehasonlítást 11-gyel szorozva kivonva a második összehasonlításból 2x ≡-62(modl05), ebből x ≡ -31(modl05).

Az I. fokú összehasonlítási rendszer megfontolásából fakadó problémákat Sun Tzu kínai matematikus, aki korszakunk elején élt, számtanilag vizsgálta. Kérdése a következő formában hangzott el: keress egy számot, amely adott maradékokat ad adott számokkal osztva. A következő tételnek megfelelő megoldást is ad.

Tétel (kínai maradéktétel). Legyenek m1,m2,…,ms páronkénti koprímszámok, M = mlm2...ms, β1, β2,…, βs úgy választjuk meg, hogy

Aztán a rendszer megoldása

Úgy fog kinézni, hogy x≡x0(mod M).

Bizonyíték. Mivel x0≡-t kapunk

Hasonló módon ellenőrizzük, hogy x0≡c2(mod m2),…, x0≡cs(mod ms), azaz x0 mindennek megfelel-e

rendszer összehasonlítások.

10. Az I. fokozat összehasonlításai. Bizonytalan egyenletek

2. § Az I. fokozat összehasonlításai. Bizonytalan egyenletek

Az 1. fokú összehasonlítás az ax≡b(mod m) alakra redukálható.

4. tétel. Ha (a,m) = 1, akkor az ax ≡b(mod m) (2) összehasonlításnak egyedi megoldása van.

Bizonyíték. Vegyünk 0,1,2,...,m-1 - egy teljes maradékrendszert modulo m. Mivel (a,m) = 1, akkor 0,a,2a,...,(m-1)a is egy teljes maradékrendszer (3. Tétel, 2. §, 2. fejezet). Egy és csak egy b modulo m-hez hasonlítható számot tartalmaz (a b-vel azonos osztályba tartozik). Legyen ez ax 0, azaz ax 0 € b osztály vagy ax 0 ≡b(mod m). x ≡x 0 (mod m) a (2) egyetlen megoldása. A tétel bizonyítást nyert.

5. tétel. Ha (a, m)= 1, akkor az ax≡b(mod m) összehasonlítás megoldása az x 0 ≡a φ (m)-1 b(mod m) osztály.

Bizonyíték. Mivel (a,m) = 1, akkor az Euler-elv szerint a φ(m) ≡1(mod m). Könnyen belátható, hogy x 0 ≡a φ (m)-1 b (mod m) a (2) összehasonlítás megoldása. Valóban, a(a φ (m)-1 b)≡a φ (m) b≡b(mod m). A 4. Tételből következik, hogy ez a megoldás egyedi.

Mérlegeljük összehasonlító megoldási módszerek ax ≡b(mod m).

1. Kiválasztás módja. A maradék modulo m teljes rendszerét figyelembe véve olyan számokat választunk ki, amelyek kielégítik az összehasonlítást.

2. Az Euler-tétel segítségével (5. tétel).

3. Együttható-konverziós módszer. Meg kell próbálnunk az együtthatókat úgy transzformálni, hogy a jobb oldalt el lehessen osztani x együtthatójával. A szóban forgó transzformációk a következők: együtthatók helyettesítése az abszolút legkisebb maradékokkal, a b szám helyettesítése abszolút értékben összehasonlítható számmal (egy olyan szám hozzáadása, amely az abszolút érték többszöröse) úgy, hogy az utóbbi osztható legyen a-val, mozgatva a-ból és b-ből más, hozzájuk hasonló számokra, amelyeknek közös osztójuk lenne stb. Ebben az esetben az összehasonlítások és a tételek tulajdonságait használjuk az ezeken alapuló ekvivalens összehasonlításokon.

1) 223x ≡ 115 (1. mód).

Először is helyettesítjük az együtthatókat a legkisebb abszolútérték-levonásokkal: 3х ≡ 5 (mod 11). Ha a tételt használjuk

Akkor Euler

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

Az együtthatók átszámítása azonban egyszerűbb. Cseréljük ki az összehasonlítást egy ekvivalensre úgy, hogy a jobb oldalhoz adjunk egy számot, amely a modulus többszöröse:

3x ≡ 5 + 22 (11. mód). Mindkét oldalt elosztva a 3-mal, a modulusra koprimálva x ≡ 9(mod l1) kapjuk.

2) 111x≡ 8 (34-es mód).

Az együttható konverziós módszert alkalmazzuk.

(111-3*34)x≡8 (34. mód), 9x≡8+34≡42 (34. mód), 3x≡14 (34. mód), 3x≡14+34≡48 (34. mód), x≡16 (34-es mód).

6. tétel. Ha (a, m) = d és b nem osztható d-vel, akkor az (1) összehasonlításnak nincs megoldása.

Bizonyítás (ellentmondás által). Legyen az x 0 osztály megoldás, azaz ax 0 ≡b (mod m) vagy (ax 0 -b):m, és ezért (ax 0 -b):d. De a:d, majd b:d ellentmondás. Ezért az összehasonlításnak nincs megoldása.

7. tétel. Ha (a,m)= d, d>1, b:d, akkor az (1) összehasonlítás d

olyan megoldások, amelyek a modulo-maradékok egy osztályát alkotják, és a képletekkel megtalálhatók

Ahol Vel kielégíti a kiegészítő összehasonlítást

Megjegyzés. A tétel szerint az (1) összehasonlítást a következőképpen oldjuk meg.

1) Miután meggyőződtünk arról, hogy (a,m) = d, d> 1 és b:d, a ​​(2) összehasonlításban mindkét részt elosztjuk d-vel, és egy segédösszehasonlítást kapunk a 1 x≡b 1 (mod m 1) , ahol . Az összehasonlításnak csak egy megoldása van. Legyen a c osztály a megoldás.

2) Írja be a választ 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).

Bizonyíték. A 2(3) Tétel szerinti segédösszehasonlítás ekvivalens az eredeti összehasonlítással (2). Mivel ( 1, Ekkor a segédösszehasonlításnak van egy egyedi megoldása - egy osztály modulo m 1 = . Legyen x≡c(mod m 1) a megoldás. A c modulo m 1 számok osztálya d modulo m osztályra bomlik: .

Valójában az x0 modulo m 1 osztály bármely számának alakja x 0 +m 1 t. t maradékkal osztjuk d-vel: t = dq +r, ahol 0≤r

Tehát az (1) összehasonlításnak d modulo m megoldása van: x0, x0+m1,..., x0 +(d-1)m1 (vízszintes vonalak felül)

Példák.

1) 20x≡ 15 (108-as mód). Mivel (20,108) = 4 és 15 nem osztható 4-gyel, nincs megoldás.

2) 20x≡ 44 (108-as mód). (20,108) = 4 és 44:4, ezért az összehasonlításnak négy megoldása van. Mindkét részt és a modult 4-gyel elosztva kapjuk:

5х≡11 (mod 27); 5 x≡11-81 ≡ -70 (mod27), x ≡ -14 ≡ 13 (mod 27). Ekkor x≡13 + 27r(mod 108), ahol r = 0,1,2,3. én jj

Válasz: x≡13(modl08); x ≡ 40 (modl08); x ≡ 67 (modl08); x≡94(modl08).

Az összehasonlítás elméletének alkalmazása bizonytalan egyenletek megoldására

Tekintsünk egy határozatlan vagy más néven egy elsőfokú diofantin egyenletet két ismeretlennel ax + by = c, ahol a, b, c € Z. Ezt az egyenletet egész számokban kell megoldani. Ha (a,b)=d és c nem osztható d-vel, akkor nyilvánvaló, hogy az összehasonlításnak nincs egész számban kifejezett megoldása. Ha c osztható d-vel, akkor az egyenlet mindkét oldalát ossza el d-vel. Ezért elég figyelembe venni azt az esetet, amikor (a, b) =1.

Mivel ax b többszörösével különbözik c-től, akkor ax ≡ c(mod b) (az általánosság elvesztése nélkül feltételezhetjük, hogy b > 0). Ezt az összehasonlítást megoldva x ≡x1 (mod b) vagy x=x1+bt kapjuk, ahol t€Z. Az y megfelelő értékeinek meghatározásához az a(x1 + bt) + by = c egyenlet áll rendelkezésünkre, amelyből

Ráadásul a - egy egész szám, az ismeretlen y részértéke, amely x1-nek felel meg (kiderül, mint x1, t = 0-nál). Az egyenlet általános megoldása pedig egy x=x1+bt, y=y1-at egyenletrendszer formájában lesz, ahol t tetszőleges egész szám.

Jegyzet hogy 1) az ax + by = c egyenlet megoldható úgy, hogy az összehasonlítást ≡ c(mod a)-val kezdjük, mivel by különbözik c-től a többszörösével;

2) kényelmesebb modulként választani legkisebb modul a és b.

Példa, 50x – 42 év = 34.

Oszd el az egyenlet mindkét oldalát 2-vel.

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

x ≡ -1 (mod 21), azaz x=-1+21t, t€Z. Helyettesítsük be a talált x-et az egyenletbe. 25(-1 + 21t)- 21y= 17; 21у =-42 + 25* 21t és у =-2 + 25t.