Brojevi usporedivi po modulu 7. Usporedba po modulu prirodnog broja

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.

Projekt iz matematike na temu

"Usporedbe po modulu"

Zaripova Aisylu

Sovjetski okrug Kazana

MBOU "Srednja škola br. 166", 7a razred

Znanstveni voditelj: Antonova N.A.

Sadržaj

Uvod________________________________________________________________3

Što su usporedbe_________________________________________________4

Primjena usporedbi u rješavanju problema_________________________________6

Najjednostavnija uporaba modulo usporedbi je određivanje djeljivosti brojeva___________________________6
Jedan zadatak za usporedbu_______________________________8
Korištenje modulo usporedbi u profesionalnim aktivnostima________________________________________________9

Zaključak_________________________________________________10

Popis korištene literature_______________________________________11

Uvod.

Tema: Modulo usporedbe.

Problem: Mnogi se učenici prilikom priprema za olimpijade susreću s problemima čije se rješavanje temelji na poznavanju ostataka dijeljenja cijelih brojeva prirodnim brojem. Zanimali su nas ovakvi problemi i mogući načini njihovog rješavanja. Ispostavilo se da se oni mogu riješiti korištenjem modulo usporedbi.

Cilj: Saznati bit modulo usporedbi, glavne metode rada s modulo usporedbama.

Ciljevi: pronaći teoretski materijal o ovoj temi, razmotriti probleme koji se rješavaju pomoću modulo usporedbi, pokazati najčešće metode za rješavanje takvih problema, izvući zaključke.

Predmet proučavanja: teorija brojeva.

Predmet istraživanja: teorija modulo usporedbi.

Rad se odnosi na teorijska istraživanja i može se koristiti u pripremama za matematičke olimpijade. Njegov sadržaj otkriva osnovne pojmove modulo usporedbi i njihova glavna svojstva te daje primjere rješavanja zadataka na ovu temu.

ja . Što su usporedbe?

Kaže se da su brojevi i usporedivi po modulu ako su djeljivi s, drugim riječima, a i b imaju iste ostatke kada se dijele s.

Oznaka

Primjeri:

12 i 32 su usporedivi po modulu 5, budući da 12 kada se podijeli s 5 ima ostatak 2, a 32 kada se podijeli s 2 ima ostatak 2. Zapisano je12 ;

101 i 17 su usporedivi po modulu 21;

Teoriju djeljivosti većim je dijelom stvorio Euler. Definicija usporedbe formulirana je u knjizi K. F. Gaussa “Aritmetičke studije”. Ovo djelo, napisano na latinskom jeziku, počelo se tiskati 1797. godine, ali je knjiga objavljena tek 1801. godine zbog činjenice da je tiskarski proces u to vrijeme bio izuzetno naporan i dugotrajan. Prvi dio Gaussove knjige zove se: “O usporedbi brojeva”. Gauss je bio taj koji je predložio simboliku modulo usporedbi koja se ustalila u matematici.

Ako

Dokaz:

Ako prvoj jednakosti dodamo drugu, dobivamo

je zbroj dva cijela broja, stoga je cijeli broj, dakle.

Ako od prve jednakosti oduzmemo drugu, dobivamo

ovo je razlika dva cijela broja, što znači da je cijeli broj, dakle.

Razmotrite izraz:

Ovo je razlika umnožaka cijelih brojeva, što znači da je, dakle, cijeli broj.

To je posljedica trećeg svojstva usporedbi.

Q.E.D.

5) Ako.

Dokaz: Nađimo zbroj ova dva izraza:

je zbroj dva cijela broja, stoga je cijeli broj, dakle .

Q.E.D.

6) Ako je cijeli broj, onda

Dokaz: , gdjestr– cijeli broj, pomnožimo ovu jednakost s, dobivamo: . Budući da je umnožak cijelih brojeva, to je trebalo dokazati.

7) Ako

Dokaz: obrazloženje je slično dokazu svojstva 6.

8) Ako - međusobno prosti brojevi, dakle

Dokaz: , podijelimo ovaj izraz s, dobivamo: - međusobno prosti brojevi, što znači da su djeljivi cijelim brojem, tj. =. A to znači da je ono što je trebalo dokazati.

II . Primjena usporedbi u rješavanju problema.

2.1. Najjednostavnija uporaba modulo usporedbi je određivanje djeljivosti brojeva.

Primjer. Pronađite ostatak od 2 2009 u 7.

Rješenje: Razmotrimo potencije broja 2:

dizanjem usporedbe na potenciju 668 i množenjem s dobivamo: .

Odgovor: 4.

Primjer. Dokažite da je 7+7 2 +7 3 +…+7 4 n je djeljiv sa 100 za bilo kojiniz skupa cijelih brojeva.

Rješenje: Razmotrite usporedbe

itd. Cikličnost ostataka objašnjava se pravilima množenja brojeva u stupcu. Zbrajanjem prve četiri usporedbe dobivamo:

To znači da se taj iznos dijeli sa 100 bez ostatka. Slično, zbrajanjem sljedećih usporedbi oko četiri, dobivamo da je svaki takav zbroj djeljiv sa 100 bez ostatka. To znači da cijeli zbroj koji se sastoji od 4npojmova je djeljiv sa 100 bez ostatka. Q.E.D.

Primjer. Odredite po kojoj vrijednostinizraz je djeljiv s 19 bez ostatka.

Riješenje: .

Pomnožimo ovu usporedbu s 20. Dobivamo.

Zbrojimo onda usporedbe. . Dakle, desna strana usporedbe uvijek je djeljiva s 19 za bilo koji prirodni brojn, što znači da je izvorni izraz djeljiv s 19 s prirodnimn.

Odgovor n – bilo koji prirodni broj.

Primjer. Kojom znamenkom završava broj?

Riješenje. Kako bismo riješili ovaj problem, pratit ćemo samo posljednju znamenku. Razmotrite moći broja 14:

Možete primijetiti da ako je eksponent neparan, vrijednost stupnja završava na 4, a ako je eksponent paran, završava na 6. Tada završava na 6, tj. je paran broj. Dakle, završit će za 6.

Odgovor 6.

2.2. Jedan zadatak za usporedbu.

Članak N. Vilenkina “Usporedbe i klase ostataka” predstavlja problem koji je tijekom studentskih godina riješio slavni engleski fizičar Dirac.

Postoji i kratko rješenje ovog problema koristeći modulo usporedbe. Ali susreli smo se s nizom sličnih problema. Na primjer.

Jedan je prolaznik kraj stabla pronašao hrpu jabuka na kojoj je sjedio majmun. Nakon što ih je prebrojao, shvatio je da ako se 1 jabuka da majmunu, tada će se broj preostalih jabuka podijeliti na n bez traga. Davši dodatnu jabuku majmunu, uzeo je 1/ n preostale jabuke i lijevo. Kasnije je hrpi prišao sljedeći prolaznik, zatim sljedeći itd. Svaki sljedeći prolaznik, nakon što je prebrojao jabuke, primijetio je da je njihov broj podijeljen sa n daje ostatak 1 i, nakon što je dao višak jabuke majmunu, uzeo je 1 za sebe n preostale jabuke i krenuli dalje. Nakon što je posljednji otišao, n prolaznika, broj jabuka preostalih na hrpi podijeljen je s n bez traga. Koliko je jabuka bilo prvo na hrpi?

Provodeći isto razmišljanje kao Dirac, dobili smo opću formulu za rješavanje klase sličnih problema: , gdjen- prirodni broj.

2.3. Primjena usporedbi modula u profesionalnim aktivnostima.

Teorija usporedbe primjenjuje se na teoriju kodiranja, tako da će svi ljudi koji izaberu profesiju vezanu uz računala učiti, a možda i primijeniti usporedbe u svojim profesionalnim aktivnostima. Na primjer, brojni koncepti teorije brojeva, uključujući modulo usporedbe, koriste se za razvoj algoritama šifriranja s javnim ključem.

Zaključak.

U radu se iznose osnovni pojmovi i svojstva modulo usporedbi te se na primjerima ilustrira uporaba modulo usporedbi. Materijal se može koristiti u pripremi za olimpijade iz matematike i Jedinstveni državni ispit.

Navedeni popis literature omogućuje, ako je potrebno, razmatranje nekih složenijih aspekata teorije modulo usporedbi i njezinih primjena.

Popis korištene literature.

Alfutova N.B. Algebra i teorija brojeva./N.B.Alfutova, A.V.Ustinov. M.:MCNMO, 2002, 466 str.

Bukhshtab A.A. Teorija brojeva. /A.A.Bukhshtab. M.: Obrazovanje, 1960.

Vilenkin N. Usporedbe i klase ostataka./N. Vilenkin.//Quantum. – 1978.- 10.

Fedorova N.E. Studij algebre i matematičke analize. 10. razred.http:// www. prosv. ru/ e-knjige/ Fedorova_ Algebra_10 kl/1/ xht

ru. wikipedija. org/ wiki/Modul_usporedbe.

Definicija 1. Ako su dva broja 1) a I b kada se podijeli sa str dati isti ostatak r, tada se takvi brojevi nazivaju ekviremainder ili usporedivi po modulu str.

Izjava 1. Neka str neki pozitivan broj. Zatim svaki broj a uvijek i, štoviše, na jedini način koji se može prikazati u obliku

Ali ti se brojevi mogu dobiti postavljanjem r jednako 0, 1, 2,..., str−1. Stoga sp+r=a dobit će sve moguće cjelobrojne vrijednosti.

Pokažimo da je ovaj prikaz jedinstven. Hajdemo to pretvarati str može se prikazati na dva načina a=sp+r I a=s 1 str+r 1 . Zatim

(2)

Jer r 1 prihvaća jedan od brojeva 0,1, ..., str−1, zatim apsolutna vrijednost r 1 −r manje str. Ali iz (2) slijedi da r 1 −r višestruki str. Stoga r 1 =r I s 1 =s.

Broj r nazvao minus brojevima a modulo str(drugim riječima, broj r zove se ostatak broja a na str).

Izjava 2. Ako dva broja a I b usporedivi po modulu str, To a−b podjeljeno sa str.

Stvarno. Ako dva broja a I b usporedivi po modulu str, onda kada se podijeli sa str imaju isti ostatak str. Zatim

podjeljeno sa str, jer desna strana jednadžbe (3) podijeljena je s str.

Izjava 3. Ako je razlika dvaju brojeva djeljiva sa str, onda su ti brojevi usporedivi u modulu str.

Dokaz. Označimo sa r I r 1 diobeni ostatak a I b na str. Zatim

Primjeri 25≡39 (mod 7), −18≡14 (mod 4).

Iz prvog primjera slijedi da 25 kada se podijeli sa 7 daje isti ostatak kao 39. Doista, 25 = 3·7+4 (ostatak 4). 39=3·7+4 (ostatak 4). Kada razmatrate drugi primjer, trebate uzeti u obzir da ostatak mora biti nenegativan broj manji od modula (tj. 4). Tada možemo napisati: −18=−5·4+2 (ostatak 2), 14=3·4+2 (ostatak 2). Prema tome, −18 kada se podijeli s 4 ostavlja ostatak 2, a 14 kada se podijeli s 4 ostavlja ostatak 2.

Svojstva modulo usporedbi

Vlasništvo 1. Za bilo koga a I str Stalno

nema uvijek usporedbe

Gdje λ je najveći zajednički djelitelj brojeva m I str.

Dokaz. Neka λ najveći zajednički djelitelj brojeva m I str. Zatim

Jer m(a−b) podjeljeno sa k, To

Stoga

I m je jedan od djelitelja broja str, To

Gdje h=pqs.

Imajte na umu da možemo dopustiti usporedbe na temelju negativnih modula, tj. usporedba a≡b mod( str) znači u ovom slučaju da razlika a−b podjeljeno sa str. Sva svojstva usporedbi ostaju na snazi za negativne module.

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.

Operacija je pravilo prema kojem bilo koja dva elementa skupa G(a I b) podudara se s trećim elementom iz G: a b.

Puno elemenata G s operacijom se zove skupina, ako su zadovoljeni sljedeći uvjeti.

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 započ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