Usporedbe prvoga stupnja. Usporedba po modulu prirodnog broja Definicija Usporedba po modulu prirodnog broja

Pri n daju iste ostatke.

Ekvivalentne formulacije: a i b usporedivi po modulu n ako njihova razlika a - b je djeljiv s n, ili ako se a može predstaviti kao a = b + kn , Gdje k- neki cijeli broj. Na primjer: 32 i −10 su usporedivi po modulu 7, jer

Izjava "a i b su usporedivi po modulu n" napisana je kao:

Svojstva jednakosti modula

Relacija modulo usporedbe ima svojstva

Bilo koja dva cijela broja a I b usporedivo po modulu 1.

Kako bi brojke a I b bili usporedivi po modulu n, potrebno je i dovoljno da je njihova razlika djeljiva sa n.

Ako su brojevi i u parovima usporedivi po modulu n, zatim njihovi zbrojevi i , kao i umnošci i također su usporedivi po modulu n.

Ako brojevi a I b usporedivi po modulu n, zatim njihove diplome a k I b k također su usporedivi po modulu n pod bilo kojim prirodnim k.

Ako brojevi a I b usporedivi po modulu n, I n podjeljeno sa m, To a I b usporedivi po modulu m.

Kako bi brojke a I b bili usporedivi po modulu n, prikazan u obliku svoje kanonske dekompozicije na jednostavne faktore str ja

potrebno i dovoljno da se

Odnos usporedbe je odnos ekvivalencije i ima mnoga svojstva običnih jednakosti. Na primjer, mogu se zbrajati i množiti: ako

Usporedbe se, međutim, općenito govoreći, ne mogu dijeliti jedna s drugom ili s drugim brojevima. Primjer: , ali smanjenjem za 2 dobivamo pogrešnu usporedbu: . Pravila kratica za usporedbe su sljedeća.

Također ne možete izvoditi operacije na usporedbama ako se njihovi moduli ne podudaraju.

Ostala svojstva:

Povezane definicije

Dedukcijski razredi

Skup svih brojeva usporedivih s a modulo n nazvao razred odbitka a modulo n , a obično se označava [ a] n ili . Dakle, usporedba je ekvivalentna jednakosti klasa ostataka [a] n = [b] n .

Od modulo usporedbe n je relacija ekvivalencije na skupu cijelih brojeva, tada su klase ostataka modulo n predstavljaju klase ekvivalencije; njihov broj je jednak n. Skup svih klasa ostataka po modulu n označen sa ili.

Operacije zbrajanja i množenja induciraju odgovarajuće operacije na skupu:

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

S obzirom na te operacije skup je konačan prsten, a ako n jednostavno – konačno polje.

Sustavi odbitka

Sustav ostataka omogućuje izvođenje aritmetičkih operacija na konačnom skupu brojeva bez odlaska izvan njegovih granica. Potpuni sustav odbitaka po modulu n je bilo koji skup od n cijelih brojeva koji su neusporedivi po modulu n. Obično se najmanji nenegativni ostaci uzimaju kao potpuni sustav ostataka modulo n

0,1,...,n − 1

ili apsolutno najmanji odbici koji se sastoje od brojeva

u slučaju ak n i brojevima

u slučaju čak n .

Rješavanje usporedbi

Usporedbe prvoga stupnja

U teoriji brojeva, kriptografiji i drugim područjima znanosti često se javlja problem pronalaženja rješenja za usporedbe oblika prvog stupnja:

Rješavanje takve usporedbe počinje izračunavanjem GCD-a (a, m)=d. U ovom slučaju moguća su 2 slučaja:

Ako b ne višestruka d, tada usporedba nema rješenja.
Ako b višestruki d, tada usporedba ima jedinstveno rješenje modulo m / d, ili, što je isto, d modulo rješenja m. U ovom slučaju, kao rezultat smanjenja izvorne usporedbe za d usporedba je:

Gdje a 1 = a / d , b 1 = b / d I m 1 = m / d su cijeli brojevi, i a 1 i m 1 su relativno prosti. Stoga broj a 1 se može obrnuti modulo m 1, odnosno pronađite takav broj c, to (drugim riječima, ). Sada se rješenje nalazi množenjem dobivene usporedbe s c:

Praktični izračun vrijednosti c može se implementirati na različite načine: korištenjem Eulerovog teorema, Euklidovog algoritma, teorije kontinuiranih razlomaka (vidi algoritam), itd. Konkretno, Eulerov teorem omogućuje vam da zapišete vrijednost c kao:

Primjer

Za usporedbu imamo d= 2, tako da po modulu 22 usporedba ima dva rješenja. Zamijenimo 26 s 4, usporedivo s njim po modulu 22, a zatim smanjimo sva 3 broja za 2:

Budući da je 2 jednako prost s modulom 11, možemo smanjiti lijevu i desnu stranu za 2. Kao rezultat, dobivamo jedno rješenje po modulu 11: , ekvivalentno dvama rješenjima po modulu 22: .

Usporedbe drugog stupnja

Rješavanje usporedbi drugog stupnja svodi se na pronalaženje je li dati broj kvadratni ostatak (koristeći kvadratni zakon reciprociteta) i zatim izračunavanje kvadratnog korijena po modulu.

Priča

Kineski teorem o ostatku, poznat stoljećima, tvrdi (na modernom matematičkom jeziku) da je prsten ostataka modulo umnožak nekoliko međusobno prostih brojeva

Razmotrimo sustav usporedbi

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

Teorem 1. Neka je M = najmanji zajednički višekratnik brojeva m1,m2,…,ms. Ako a zadovoljava sustav (2), tada svaki broj iz klase a po modulu M zadovoljava ovaj sustav.

Dokaz. Neka b€ pripada klasi a. Kako je a ≡ b(mod M), onda je a ≡b(mod m), i= 1,2,...,s (usporedno svojstvo 16). Prema tome, b, kao i a, zadovoljava svaku usporedbu sustava, što dokazuje teorem. Stoga je prirodno rješenje sustava (2) smatrati klasom po modulu M.

Definicija. Rješenje sustava usporedbi(2) je klasa brojeva po modulu M = koji zadovoljavaju svaku usporedbu sustava.

12. Odmah napomenimo da neparni brojevi ne zadovoljavaju drugu usporedbu. Uzimajući parne brojeve iz kompletnog sustava ostataka po modulu 12, izravnom provjerom uvjeravamo se da brojevi 2, -2, 6 zadovoljavaju 2. usporedbu, a sustav ima dva rješenja: x ≡ 2(mod l2), x ≡ - 2 (mod 12).

Razmotrimo sustav usporedbi 1. stupnja (3)

Teorem2. Neka je d=(m1,m2), M = .

Ako c1 - c2 nije djeljiv s d, tada sustav (3) nema rješenja.

Ako je (c1 -c2):d, tada sustav (3) ima jedno rješenje - klasu po modulu M.

Dokaz. Iz 1. usporedbe x = c1+m1t, t€Z. Zamjena u 2. usporedbu: s1+ m1t ≡ c2(mod m2) odn.

m1t ≡ c2-cl (mod m2). Ova usporedba ima rješenje samo ako (c2 – c1): d.

A rješenje je klasa modulo (teorem 4 iz §2).

Neka je rješenje , odnosno gdje je k€Z.

M== , odnosno x≡c1+m1t0(mod M) je rješenje

Primjeri.

1. :2, sustav ima jednu klasu rješenja modulo 24. Iz 1. usporedbe x =2+6t. Zamjenom x u 2. usporedbu, imamo: 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, to je x≡-4(mod 24).

2. 7-3 nije djeljivo s 3, sustav nema rješenja.

Korolar 1. Sustav usporedbe (4)

Ili nema rješenja, ili ima jedno rješenje - klasu po modulu M=.

Dokaz. Ako sustav prve dvije usporedbe nema rješenja, tada (4) nema rješenja. Ako ima rješenje x ≡ a(mod), onda dodavanjem treće usporedbe sustava ovoj usporedbi opet dobivamo sustav oblika (3) koji ili ima jedno rješenje ili nema rješenja. Ako ima rješenje, nastavit ćemo tako dok ne iscrpimo sve usporedbe sustava (4). Ako postoji rješenje, onda je to klasa po modulu M.

Komentar. Ovdje se koristi svojstvo LCM: =.

Korolar 2. Ako su m1,m2,…,ms upareno prosti, tada sustav (4) ima jedno rješenje - modulo klasa M=m1m2…ms.

Primjer:

Budući da su moduli u paru relativno jednostavni, sustav ima jedno rješenje - modulo klasa 105 = 5*3*7. Iz prve usporedbe

Zamjenjujemo u drugu usporedbu: 2 +5t≡ 0(mod 3) ili 2t≡-2(mod3), t=-1+3k, x=2+5(-1+3k), x=-3+15k . Zamijenimo u trećoj usporedbi:

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

Idemo se upoznati drugi metoda rješavanja ovog sustava, (Koristimo se činjenicom da sustav ima jedno rješenje.) Pomnožimo oba dijela i modul prve usporedbe s 21, druge s 35, a treće s 15: iz zbroja prvi i treći oduzimamo drugi:

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

Razmotrimo sada sustav usporedbi prvog stupnja općeg oblika

Ako neka usporedba ovog sustava nema rješenja, onda sustav nema rješenja. Ako je svaka usporedba sustava (5) rješiva, tada je rješavamo za x i dobivamo ekvivalentni sustav oblika (4):

Gdje je (teorem 4, §2).

Prema korolariji 1, sustav ili nema rješenja ili ima jedno rješenje.

Primjer:

Nakon rješavanja svake usporedbe sustava dobivamo ekvivalentni sustav

Ovaj sustav ima jedno rješenje - klasu po modulu 105. Množenjem prve usporedbe i modula s 3, a druge s 35, dobivamo

Oduzimajući prvu usporedbu pomnoženu s 11 od druge usporedbe, dobivamo 2x ≡-62(modl05), iz čega je x ≡ -31(modl05).

Problemi koji se svode na razmatranje sustava usporedbi 1. stupnja razmatrani su u aritmetici kineskog matematičara Sun Tzua, koji je živio početkom naše ere. Njegovo je pitanje bilo postavljeno u sljedećem obliku: nađite broj koji daje zadane ostatke kada se dijeli zadanim brojevima. Također daje rješenje ekvivalentno sljedećem teoremu.

Teorem (kineski teorem o ostatku). Neka su m1,m2,…,ms upareni međusobno prosti brojevi, M = mlm2...ms, β1, β2,…, βs odabrani tako da

Zatim rješenje sustava

Izgledat će kao x≡x0(mod M).

Dokaz. Pošto smo dobili x0≡

Na sličan način provjeravamo da x0≡c2(mod m2),…, x0≡cs(mod ms), odnosno x0 zadovoljava sve

usporedbe sustava.

10. Usporedbe I. stupnja. Nesigurne jednadžbe

§ 2. Usporedbe 1. stupnja. Nesigurne jednadžbe

Usporedba 1. stupnja može se svesti na oblik ax≡b(mod m).

Teorem 4. Ako je (a,m) = 1, tada usporedba ax ≡b(mod m) (2) ima jedinstveno rješenje.

Dokaz. Uzmimo 0,1,2,...,m-1 - potpuni sustav ostataka modulo m. Budući da je (a,m) = 1, tada je 0,a,2a,...,(m-1)a također potpuni sustav ostataka (Teorem 3, §2, Poglavlje 2.). Sadrži jedan i samo jedan broj usporediv s b po modulu m (koji pripada istoj klasi kao i b). Neka to bude ax 0, tj. ax 0 € klasa b ili ax 0 ≡b(mod m). x ≡x 0 (mod m) je jedino rješenje (2). Teorem je dokazan.

Teorem 5. Ako je (a, m)= 1, tada je rješenje za usporedbu ax≡b(mod m) klasa x 0 ≡a φ (m)-1 b(mod m).

Dokaz. Kako je (a,m) = 1, onda je po Eulerovom principu a φ(m) ≡1(mod m). Lako je vidjeti da je x 0 ≡a φ (m)-1 b (mod m) rješenje za usporedbu (2). Doista, a(a φ (m)-1 b)≡a φ (m) b≡b(mod m). Iz teorema 4 slijedi da je ovo rješenje jedinstveno.

Razmotrimo metode usporedbe rješenja ax ≡b(mod m).

1. Metoda odabira. Uzimajući cijeli sustav ostataka modulo m, odabiremo brojeve koji zadovoljavaju usporedbu.

2. Korištenje Eulerovog teorema (teorem 5).

3. Metoda pretvorbe koeficijenata. Moramo pokušati transformirati koeficijente tako da se desna strana može podijeliti s koeficijentom od x. Transformacije o kojima je riječ su sljedeće: zamjena koeficijenata s apsolutno najmanjim ostacima, zamjena broja b s brojem usporedivim po apsolutnoj vrijednosti (dodavanje broja koji je višekratnik apsolutne vrijednosti) tako da je potonji djeljiv s a, pomicanje od a i b do drugih njima usporedivih brojeva, koji bi imali zajednički djelitelj, itd. U ovom slučaju koristimo svojstva usporedbi i na njima temeljene teoreme o ekvivalentnim usporedbama.

1) 223x ≡ 115(mod ll).

Prvo zamjenjujemo koeficijente s najmanjim odbicima apsolutne vrijednosti: 3h ≡ 5(mod 11). Ako se poslužimo teoremom

Euler, dakle

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

Međutim, lakše je pretvoriti koeficijente. Zamijenimo usporedbu ekvivalentnom tako da na desnu stranu dodamo broj koji je višekratnik modula:

3x ≡ 5 + 22 (mod 11). Podijelimo li obje strane s brojem 3, istoprostim s modulom, dobivamo x ≡ 9(mod l1).

2) 111x≡ 8(mod 34).

Koristimo metodu pretvorbe koeficijenata.

(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 (izmjena 34).

Teorem 6. Ako je (a, m) = d i b nije djeljiv s d, tada usporedba (1) nema rješenja.

Dokaz (kontradikcijom). Neka je klasa x 0 rješenje, to jest, ax 0 ≡b (mod m) ili (ax 0 -b):m, i, prema tome, (ax 0 -b):d. Ali a:d, onda je b:d kontradikcija. Stoga usporedba nema rješenja.

Teorem 7. Ako je (a,m)= d, d>1, b:d, tada usporedba(1) ima d

rješenja koja čine jednu klasu modulo ostataka i nalaze se pomoću formula

Gdje S zadovoljava pomoćnu usporedbu

Komentar. Prema teoremu, usporedba (1) se rješava na sljedeći način.

1) Uvjerivši se da je (a,m) = d, d> 1 i b:d, oba dijela u usporedbama (2) podijelimo s d i dobijemo pomoćnu usporedbu a 1 x≡b 1 (mod m 1) , gdje . Usporedba ima samo jedno rješenje. Neka je klasa c rješenje.

2) Napišite odgovor 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).

Dokaz. Pomoćna usporedba prema teoremu 2(3) ekvivalentna je izvornoj usporedbi (2). Budući da je ( 1, tada pomoćna usporedba ima jedinstveno rješenje - klasu po modulu m 1 = . Neka je x≡c(mod m 1) rješenje. Klasa brojeva c po modulu m 1 dijeli se na d klasa po modulu m: .

Doista, bilo koji broj iz klase x0 modulo m 1 ima oblik x 0 +m 1 t. Podijelite t s ostatkom s d: t = dq +r, gdje je 0≤r

Dakle, usporedba (1) ima d rješenja po modulu m: x0, x0+m1,..., x0 +(d-1)m1. (horizontalne crte na vrhu)

Primjeri.

1) 20x≡ 15(mod 108). Kako (20,108) = 4 i 15 nije djeljivo s 4, nema rješenja.

2) 20x≡ 44 (mod 108). (20,108) = 4 i 44:4, stoga usporedba ima četiri rješenja. Podijelimo oba dijela i modul sa 4, dobivamo:

5h≡11(mod 27); 5 x≡11-81 ≡ -70(mod27), x ≡ -14 ≡ 13(mod 27). Tada je x≡13 + 27r(mod 108), gdje je r = 0,1,2,3. ja jj

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

Primjena teorije usporedbi na rješavanje nesigurnih jednadžbi

Promotrimo neodređenu ili, kako se inače zove, Diofantovu jednadžbu prvog stupnja s dvije nepoznanice ax + by = c, gdje su a, b, c € Z. Ovu jednadžbu morate riješiti u cijelim brojevima. Ako (a,b)=d i c nije djeljiv s d, onda je očito da usporedba nema rješenja u cijelim brojevima. Ako je c djeljiv s d, tada obje strane jednadžbe podijelite s d. Stoga je dovoljno razmotriti slučaj kada je (a, b) =1.

Budući da se ax razlikuje od c višekratnikom b, tada je ax ≡ c(mod b) (bez gubitka općenitosti možemo pretpostaviti da je b > 0). Rješavanjem ove usporedbe dobivamo x ≡x1 (mod b) ili x=x1+bt, gdje je t€Z. Za određivanje odgovarajućih vrijednosti y imamo jednadžbu a(x1 + bt) + by = c, iz koje

Štoviše, - je cijeli broj, to je djelomična vrijednost nepoznate y, koja odgovara x1 (ispada, kao i x1, pri t = 0). A opće rješenje jednadžbe će imati oblik sustava jednadžbi x=x1+bt, y=y1-at, gdje je t bilo koji cijeli broj.

Bilješka da se 1) jednadžba ax + by = c može riješiti počevši s usporedbom by ≡ c(mod a), budući da se by razlikuje od c višekratnikom a;

2) prikladnije je odabrati kao modul najmanji modul a i b.

Primjer, 50x – 42y= 34.

Podijelite obje strane jednadžbe s 2.

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

x ≡ -1 (mod 21), odnosno x=-1+21t, t€Z. Zamijenimo pronađeni x u jednadžbu. 25(-1 + 21t)- 21y= 17; 21u =-42 + 25* 21t i u =-2 + 25t.

Usporedba s jednom nepoznatom x izgleda kao

Gdje . Ako a n nije djeljiv sa m, tako se zove stupanj usporedbe.

Odlukom usporedba je bilo koji cijeli broj x 0 , za koji

Ako x 0 zadovoljava usporedbu, tada, prema svojstvu 9 usporedbi, svi cijeli brojevi usporedivi s x 0 modulo m. Stoga sve usporedne otopine koje pripadaju istoj klasi ostataka modulo T, smatrat ćemo ga jednim rješenjem. Dakle, usporedba ima onoliko rješenja koliko ima elemenata cjelovitog sustava ostataka koji je zadovoljavaju.

Usporedbe čiji se skupovi rješenja podudaraju nazivaju se ekvivalent.

2.2.1 Usporedbe prvog stupnja

Usporedba prvog stupnja s jednom nepoznatom x izgleda kao

(2.2)

Teorem 2.4. Da bi usporedba imala barem jedno rješenje, potrebno je i dovoljno da broj b podijeljeno s GCD( a, m).

Dokaz. Prvo dokazujemo nužnost. Neka d = GCD( a, m) I x 0 - rješenje usporedbe. Zatim , odnosno razlika Oh 0 − b podjeljeno sa T. Dakle, postoji takav cijeli broj q, Što Oh 0 − b = qm. Odavde b= ah 0 − qm. I od d, kao zajednički djelitelj, dijeli brojeve A I T, tada se minuend i subtrahend dijele sa d, i stoga b podjeljeno sa d.

Sada dokažimo dostatnost. Neka d- najveći zajednički djelitelj brojeva A I T, I b podjeljeno sa d. Tada, prema definiciji djeljivosti, postoje sljedeći cijeli brojevi a 1 , b 1 ,T 1 , Što .

Koristeći prošireni euklidski algoritam, nalazimo linearni prikaz broja 1 = gcd( a 1 , m 1 ):

za neke x 0 , g 0 . Pomnožimo obje strane posljednje jednakosti s b 1 d:

ili, što je isto,

odnosno i rješenje je usporedbe. □

Primjer 2.10. Usporedba 9 x= 6 (mod 12) ima rješenje budući da je gcd(9, 12) = 3 i 6 djeljivo s 3. □

Primjer 2.11. Usporedba 6x= 9 (mod 12) nema rješenja, budući da je gcd(6, 12) = 6, a 9 nije djeljivo sa 6. □

Teorem 2.5. Neka je usporedba (2.2) rješiva i d = GCD( a, m). Tada se skup usporednih rješenja (2.2) sastoji od d modulo rezidualne klase T, naime ako x 0 - jedno od rješenja, onda su sva ostala rješenja

Dokaz. Neka x 0 - rješenje usporedbe (2.2), tj I , . Dakle, postoji takva stvar q, Što Oh 0 − b = qm. Sada zamjenjujemo u posljednju jednakost umjesto x 0 proizvoljno rješenje oblika, gdje, dobivamo izraz

, djeljiv sa m. □

Primjer 2.12. Usporedba 9 x=6 (mod 12) ima točno tri rješenja, jer gcd(9, 12)=3. Ova rješenja: x 0 = 2, x 0 + 4 = 6, x 0 + 2∙4=10.□

Primjer 2.13. Usporedba 11 x=2 (mod 15) ima jedinstveno rješenje x 0 = 7, jer GCD(11,15)=1.□

Pokazat ćemo vam kako riješiti usporedbe prvog stupnja. Bez gubitka općenitosti, pretpostavit ćemo da je GCD( a, t) = 1. Tada se rješenje usporedbe (2.2) može tražiti, na primjer, pomoću Euklidovog algoritma. Doista, koristeći prošireni Euklidski algoritam, predstavljamo broj 1 kao linearnu kombinaciju brojeva a I T:

Pomnožimo obje strane ove jednakosti s b, dobivamo: b = abq + mrb, gdje abq - b = - mrb, to je a ∙ (bq) = b(mod m) I bq- rješenje usporedbe (2.2).

Drugo rješenje je korištenje Eulerovog teorema. Opet vjerujemo da GCD(a, T)= 1. Primjenjujemo Eulerov teorem: . Pomnožite obje strane usporedbe s b: . Prepisivanje posljednjeg izraza kao , dobivamo da je to rješenje usporedbe (2.2).

Neka sada GCD( a, m) = d>1. Zatim a = atd, m = mtd, gdje je GCD( A 1 , m 1) = 1. Osim toga potrebno je b = b 1 d, kako bi usporedba bila razrješiva. Ako x 0 - rješenje usporedbe A 1 x = b 1 (mod m 1), i jedini, od GCD( A 1 , m 1) = 1, tada x 0 bit će rješenje i usporedba A 1 xd = db 1 (mod m 1), odnosno izvorna usporedba (2.2). Odmor d- 1 rješenja se nalaze prema teoremu 2.5.

Usporedba prvog stupnja s jednom nepoznatom ima oblik:

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

Riješite usporedbu- znači pronaći sve vrijednosti x koje ga zadovoljavaju. Pozivaju se dvije usporedbe koje zadovoljavaju iste vrijednosti x ekvivalent.

Ako je usporedba (1) zadovoljena bilo kojom x = x 1, zatim (prema 49) svi brojevi usporedivi s x 1, modulo m: x x 1 (mod m). Cijela ova klasa brojeva smatra se jedno rješenje. S takvim sporazumom može se izvesti sljedeći zaključak.

66.C poravnanje (1) imat će onoliko rješenja koliki je broj ostataka kompletnog sustava koji ga zadovoljavaju.

Primjer. Usporedba

6x– 4 0 (mod 8)

Među brojevima 0, 1, 2, 3, 4, 5, 6, 7 dva broja zadovoljavaju potpuni sustav ostataka po modulu 8: x= 2 i x= 6. Stoga ova usporedba ima dva rješenja:

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

Usporedba prvog stupnja pomicanjem slobodnog člana (sa suprotnim predznakom) na desnu stranu može se svesti na oblik

sjekira b(mod m). (2)

Razmotrimo usporedbu koja zadovoljava uvjet ( A, m) = 1.

Prema 66, naša usporedba ima onoliko rješenja koliko ima ostataka kompletnog sustava koji je zadovoljavaju. Ali kada x prolazi kroz cijeli sustav modulo ostataka T, Da Oh prolazi kroz cijeli sustav odbitaka (od 60). Dakle, za jednu i samo jednu vrijednost X, preuzeto iz kompletnog sustava, Oh bit će usporedivo s b. Tako,

67. Kada je (a, m) = 1 usporedna sjekira b(mod m)ima jedno rješenje.

Neka sada ( a, m) = d> 1. Zatim, za usporedbu (2) da bi postojala rješenja potrebno je (od 55) da b podjeljeno sa d, inače je usporedba (2) nemoguća za bilo koji cijeli broj x . Pretpostavljajući dakle b višestruki d, stavimo a = a 1 d, b = b 1 d, m = m 1 d. Tada će usporedba (2) biti ekvivalentna ovoj (skraćeno od d): a 1 x b 1 (mod m), u kojem već ( A 1 , m 1) = 1, i stoga će imati jedno rješenje modulo m 1 . Neka x 1 – najmanji nenegativni ostatak ove otopine po modulu m 1 , tada su svi brojevi x , tvoreći ovu otopinu nalaze se u obliku

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

Modulo m, brojevi (3) ne čine jedno rješenje, već više, točno onoliko rješenja koliko ima brojeva (3) u nizu 0, 1, 2, ..., m – 1 najmanji nenegativni modulo ostataka m. Ali ovdje će pasti sljedeći brojevi (3):

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

oni. Ukupno d brojevi (3); stoga usporedba (2) ima d odluke.

Dobivamo teorem:

68. Neka je (a, m) = d. Usporedba ax b ( mod m) nije moguće ako b nije djeljivo s d. Kada je b višekratnik d, usporedba ima d rješenja.

69. Metoda rješavanja usporedbi prvog stupnja, temeljena na teoriji ukočenih razlomaka:

Proširivanje relacije u nastavljeni razlomak m:a,

i gledajući zadnja dva podudarna razlomka:

prema svojstvima nastavljenih razlomaka (prema 30 ) imamo

Dakle, usporedba ima rješenje

pronaći, što je dovoljno za izračunavanje Pn– 1 prema metodi navedenoj u 30.

Primjer. Riješimo usporedbu

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

Ovdje (111, 321) = 3, a 75 je višekratnik broja 3. Stoga usporedba ima tri rješenja.

Podijelimo obje strane usporedbe i modul s 3, dobivamo usporedbu

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

koje prvo moramo riješiti. Imamo

q
P 3

Dakle, u ovom slučaju n = 4, P n – 1 = 26, b= 25, a imamo rješenje usporedbe (5) u obliku

x–26 ∙ 25 99 (mod 107).

Stoga su rješenja za usporedbu (4) prikazana na sljedeći način:

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

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

Izračunavanje inverznog elementa po zadanom modulu

70.Ako su brojevi cijeli brojevi a I n su prosti, tada postoji broj a′, zadovoljavajući usporedbu a ∙ a′ ≡ 1 (mod n). Broj a′ nazvao multiplikativni inverz modula n a oznaka koja se za to koristi je a- 1 (mod n).

Izračun recipročnih veličina modulo određene vrijednosti može se izvesti rješavanjem usporedbe prvog stupnja s jednom nepoznanicom, u kojoj x broj prihvaćen a′.

Kako bi se pronašlo rješenje za usporedbu

a∙x≡ 1(mod m),

Gdje ( a,m)= 1,

možete koristiti Euklidov algoritam (69) ili Fermat-Eulerov teorem, koji kaže da ako ( a,m) = 1, dakle

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

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

Grupe i njihova svojstva

Grupe su jedna od taksonomskih klasa koja se koristi u klasifikaciji matematičkih struktura sa zajedničkim karakterističnim svojstvima. Grupe imaju dvije komponente: gomila (G) I operacije() definiran na ovom skupu.

Pojmovi skupa, elementa i pripadnosti osnovni su nedefinirani pojmovi moderne matematike. Bilo koji skup definiran je elementima koji su u njega uključeni (koji pak također mogu biti skupovi). Dakle, kažemo da je skup definiran ili zadan ako za bilo koji element možemo reći pripada li tom skupu ili ne.

Za dva kompleta A, B zapisa B A, B A, B∩ A, B A, B \ A, A × B odnosno znače da B je podskup skupa A(tj. bilo koji element iz B također je sadržano u A, na primjer, skup prirodnih brojeva sadržan je u skupu realnih brojeva; osim toga, uvijek A A), B je pravi podskup skupa A(oni. B A I B ≠ A), sjecište mnogih B I A(tj. svi takvi elementi koji leže istovremeno u A, i u B, na primjer, presjek cijelih i pozitivnih realnih brojeva je skup prirodnih brojeva), unija skupova B I A(tj. skup koji se sastoji od elemenata koji leže ili u A, bilo u B), postavite razliku B I A(tj. skup elemenata koji leže u B, ali nemojte ležati A), Kartezijev produkt skupova A I B(tj. skup parova oblika ( a, b), Gdje a A, b B). Preko | A| uvijek se označava snaga skupa A, tj. broj elemenata u skupu A.