Az első fok összehasonlítása. Összehasonlítás modulo természetes szám Definíció összehasonlítás modulo természetes szám

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 , Ahol 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összehasonlítható 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öbbszörös 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 mint:

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 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 adódik, 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 ki kell számítani a modulo négyzetgyökét.

Sztori

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

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ítsd be a 2. összehasonlításba: c1+ m1t ≡ c2(mod m2) vagy

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 osztály modulo M=.

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, amíg a (4) rendszer összes összehasonlítását ki nem használjuk. 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).

Ismerkedjünk meg 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 kezdete körül é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ási módszer. 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 fel az ezek alapján végzett 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 le 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ásnak d van

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

Ahol Val 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 - a 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. Oszd el t-t maradékkal 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 az 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.

Összehasonlítás egy ismeretlennel xúgy néz ki, mint a

Ahol . Ha a n nem osztható vele m, így hívják fokozatösszehasonlítások.

Döntés alapján az összehasonlítás bármely egész szám x 0 , amelyekre

Ha x 0 kielégíti az összehasonlítást, akkor 9 összehasonlítás tulajdonsága szerint minden olyan egész szám, amely összehasonlítható x 0 modulo m. Ezért minden összehasonlító megoldás, amely ugyanahhoz a maradékosztályhoz tartozik modulo T, egy megoldásnak fogjuk tekinteni. Így az összehasonlításnak annyi megoldása van, ahány eleme kielégíti a maradékanyagok teljes rendszerének.

Azokat az összehasonlításokat, amelyek megoldáshalmazai egybeesnek, ún egyenértékű.

2.2.1 Az első fokozat összehasonlítása

Elsőfokú összehasonlítás egy ismeretlennel xúgy néz ki, mint a

(2.2)

Tétel 2.4. Ahhoz, hogy az összehasonlításnak legalább egy megoldása legyen, szükséges és elegendő, hogy a szám b osztva GCD( a, m).

Bizonyíték. Először bebizonyítjuk a szükségességet. Hadd d = GCD( a, m) És x 0 - összehasonlító megoldás. Akkor , vagyis a különbség Ó 0 − b osztva T. Tehát van egy ilyen egész szám q, Mit Ó 0 − b = qm. Innen b= ah 0 − qm. És azóta d, közös osztóként osztja a számokat AÉs T, akkor a minuend és a részfej osztva d, és ezért b osztva d.

Most bizonyítsuk be az elégségességet. Hadd d- a számok legnagyobb közös osztója AÉs T,És b osztva d. Ekkor az oszthatóság definíciója szerint a következő egész számok léteznek a 1 , b 1 ,T 1 , Mit .

A kiterjesztett euklideszi algoritmus segítségével megtaláljuk az 1 = gcd() szám lineáris reprezentációját a 1 , m 1 ):

néhány x 0 , y 0 . Szorozzuk meg az utolsó egyenlőség mindkét oldalát ezzel b 1 d:

vagy mi ugyanaz,

vagyis és az összehasonlítás megoldása. □

2.10. példa. 9. összehasonlítás x= 6 (mod 12) van megoldása, mivel gcd(9, 12) = 3 és 6 osztható 3-mal. □

Példa 2.11. Összehasonlítás 6x= 9 (mod 12) nem rendelkezik megoldásokkal, mivel a gcd(6, 12) = 6, és a 9 nem osztható 6-tal. □

Tétel 2.5. Legyen a (2.2) összehasonlítás megoldható és d = GCD( a, m). Ekkor az összehasonlító megoldások halmaza (2.2) abból áll d modulo maradék osztályok T, mégpedig ha x 0 - az egyik megoldás, akkor az összes többi megoldás az

Bizonyíték. Hadd x 0 - összehasonlító megoldás (2.2), azaz És , . Szóval van ilyen q, Mit Ó 0 − b = qm. Most helyette az utolsó egyenlőségbe cserélve x 0 alak tetszőleges megoldása, ahol, megkapjuk a kifejezést

, osztható vele m. □

Példa 2.12. 9. összehasonlítás x=6 (mod 12) pontosan három megoldást tartalmaz, mivel gcd(9, 12)=3. Ezek a megoldások: x 0 = 2, x 0 + 4 = 6, x 0 + 2∙4=10.□

2.13. példa. Összehasonlítás 11 x=2 (mod 15) egyedi megoldással rendelkezik x 0 = 7, mivel GCD(11,15)=1.□

Megmutatjuk, hogyan oldja meg az elsőfokú összehasonlítást. Az általánosság elvesztése nélkül feltételezzük, hogy a GCD( a, t) = 1. Ezután a (2.2) összehasonlítás megoldása kereshető például az euklideszi algoritmus segítségével. Valójában a kiterjesztett euklideszi algoritmus használatával az 1-et a számok lineáris kombinációjaként ábrázoljuk. aÉs T:

Szorozzuk meg ennek az egyenlőségnek mindkét oldalát b, kapunk: b = abq + mrb, ahol abq - b = - mrb, vagyis a ∙ (bq) = b(mod m) És bq- összehasonlító megoldás (2.2).

Egy másik megoldás az Euler-tétel használata. Ismét úgy gondoljuk, hogy a GCD(a, T)= 1. Alkalmazzuk az Euler-tételt: . Szorozzuk meg az összehasonlítás mindkét oldalát ezzel b: . Az utolsó kifejezés átírása így , azt kapjuk, hogy a (2.2) összehasonlítás megoldása.

Legyen most GCD( a, m) = d>1. Akkor a = atd, m = mtd, ahol GCD( A 1 , m 1) = 1. Ezenkívül szükséges b = b 1 d, hogy az összehasonlítás megoldható legyen. Ha x 0 - összehasonlító megoldás A 1 x = b 1 (mod m 1), és az egyetlen, mivel a GCD( A 1 , m 1) = 1, akkor x 0 lesz a megoldás és az összehasonlítás A 1 xd = db 1 (mod m 1), vagyis az eredeti összehasonlítás (2.2). Pihenés d- 1 megoldást talál a 2.5. Tétel.

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 meg, 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 amikor 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öredékévé bővítése m:a,

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

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

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

megtalálni, ami elég a kiszámításhoz P n– 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. Nekünk van

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),

Ahol ( 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 (mod 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ában használt taxonómiai osztályok egyike. A csoportok két összetevőből állnak: Egy csomó (G) És tevékenységek() 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), sokak 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, akár be 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), Ahol a A, b B). Via | A| a halmaz hatványát mindig jelöljük A, azaz a készlet elemeinek száma A.