Za dva cijela broja X I at Hajde da uvedemo relaciju uporedivosti po paritetu ako je njihova razlika paran broj. Lako je provjeriti da su sva tri prethodno uvedena uslova ekvivalencije zadovoljena. Ovako uvedena relacija ekvivalencije ceo skup celih brojeva deli na dva disjunktna podskupa: podskup parnih brojeva i podskup neparnih brojeva.
Uopštavajući ovaj slučaj, reći ćemo da su dva cijela broja koja se razlikuju za višekratnik nekog fiksnog prirodnog broja ekvivalentna. Ovo je osnova za koncept uporedivosti po modulu, koji je uveo Gauss.
Broj A, uporedivo sa b modulo m, ako je njihova razlika djeljiva s fiksnim prirodni broj m, to je a - b podijeljena m. Simbolično se ovo piše kao:
a ≡ b(mod m),
a glasi ovako: A uporedivi sa b modulo m.
Ovako uvedena relacija, zahvaljujući dubokoj analogiji između poređenja i jednakosti, pojednostavljuje proračune u kojima se brojevi razlikuju za višestruko m, zapravo se ne razlikuju (pošto je poređenje jednakost do nekog višekratnika m).
Na primjer, brojevi 7 i 19 su uporedivi po modulu 4, ali ne i po modulu 5, jer 19-7=12 je deljivo sa 4 i nije deljivo sa 5.
Takođe se može reći da je broj X modulo m jednak ostatku kada se dijeli cijelim brojem X on m, jer
x=km+r, r = 0, 1, 2, ... , m-1.
Lako je provjeriti da uporedivost brojeva prema datom modulu ima sva svojstva ekvivalencije. Stoga je skup cijelih brojeva podijeljen na klase brojeva uporedivih po modulu m. Broj takvih klasa je jednak m, i svi brojevi iste klase kada se dijele sa m dati isti ostatak. Na primjer, ako m= 3, onda dobijamo tri klase: klasu brojeva koji su višestruki od 3 (daju ostatak 0 kada se podijele sa 3), klasu brojeva koji ostavljaju ostatak 1 kada se podijele sa 3, i klasu brojeva koji ostavljaju ostatak 2 kada se podijeli sa 3.
Primjeri korištenja poređenja daju dobro poznati kriteriji djeljivosti. Reprezentacija uobičajenih brojeva n brojevi u decimalnom brojevnom sistemu imaju oblik:
n = c10 2 + b10 1 + a10 0,
Gdje a, b, c,- cifre broja ispisane s desna na lijevo, dakle A- broj jedinica, b- broj desetica itd. Od 10k ≡ 1(mod9) za bilo koji k≥0, onda iz napisanog proizilazi da
n ≡ c + b + a(mod9),
odakle slijedi test djeljivosti sa 9: n je djeljiv sa 9 ako i samo ako je zbir njegovih cifara djeljiv sa 9. Ovo razmišljanje vrijedi i kada se 9 zamijeni sa 3.
Dobijamo test djeljivosti sa 11. Poređenja se vrše:
10≡- 1(mod11), 10 2 ≡ 1(mod11) 10 3 ≡- 1(mod11) i tako dalje. Zbog toga n ≡ c - b + a - ….(mod11).
dakle, n je djeljiv sa 11 ako i samo ako naizmjenična suma njegove cifre a - b + c -... su djeljive sa 11.
Na primjer, naizmjenični zbir cifara broja 9581 je 1 - 8 + 5 - 9 = -11, djeljiv je sa 11, što znači da je broj 9581 djeljiv sa 11.
Ako postoje poređenja: , onda se mogu dodavati, oduzimati i množiti član po član na isti način kao i jednakosti:
Poređenje se uvijek može pomnožiti cijelim brojem:
ako onda
Međutim, smanjenje poređenja bilo kojim faktorom nije uvijek moguće, na primjer, ali ga je nemoguće smanjiti zajedničkim faktorom 6 za brojeve 42 i 12; takvo smanjenje dovodi do netočnog rezultata, budući da .
Iz definicije uporedivosti po modulu slijedi da je redukcija za faktor dopuštena ako je ovaj faktor kopriman sa modulom.
Već je gore navedeno da je svaki cijeli broj uporediv mod m sa jednim od sljedećih brojeva: 0, 1, 2,... , m-1.
Pored ove serije, postoje i drugi nizovi brojeva koji imaju isto svojstvo; tako, na primjer, bilo koji broj je uporediv mod 5 sa jednim od sljedećih brojeva: 0, 1, 2, 3, 4, ali i uporediv s jednim od sljedećih brojeva: 0, -4, -3, -2, - 1, ili 0, 1, -1, 2, -2. Svaki takav niz brojeva naziva se kompletan sistem ostataka po modulu 5.
Dakle, kompletan sistem ostataka mod m bilo koju seriju m brojevi, od kojih nema dva međusobno uporediva. Obično se koristi kompletan sistem odbitaka koji se sastoji od brojeva: 0, 1, 2, ..., m-1. Oduzimanje broja n modulo m je ostatak podjele n on m, što proizlazi iz prikaza n = km + r, 0<r<m- 1.
PERVUSHKIN BORIS NIKOLAEVICH
Privatna obrazovna ustanova "Sankt Peterburg škola "Tete-a-Tete"
Nastavnik matematike najviše kategorije
Poređenje brojeva po modulu
Definicija 1. Ako dva broja1 ) aIbkada se podijeli sastrdati isti ostatakr, tada se takvi brojevi nazivaju equiremainder iliuporedivi po modulu str.
Izjava 1. Nekastrneki pozitivan broj. Zatim svaki brojauvijek i, štaviše, na jedini način može biti predstavljen u obliku
| a=sp+r, | (1) |
Gdjes- broj irjedan od brojeva 0,1, ...,str−1.
1 ) U ovom članku riječ broj će se shvatiti kao cijeli broj.
Zaista. Akosće dobiti vrijednost od −∞ do +∞, zatim brojevesppredstavljaju skup svih brojeva koji su višestrukistr. Pogledajmo brojeve izmeđuspi (s+1) p=sp+p. Jerstrje pozitivan cijeli broj, zatim izmeđuspIsp+ppostoje brojevi
Ali ovi brojevi se mogu dobiti postavljanjemrjednako 0, 1, 2,...,str−1. Daklesp+r=aće dobiti sve moguće cjelobrojne vrijednosti.
Pokažimo da je ovaj prikaz jedinstven. Pretvarajmo se tostrmože se predstaviti na dva načinaa=sp+rIa=s1 str+ r1 . Onda
ili
| (2) |
Jerr1 prihvata jedan od brojeva 0,1, ...,str−1, zatim apsolutnu vrijednostr1 − rmanjestr. Ali iz (2) proizilazi dar1 − rvišestrukostr. Dakler1 = rIs1 = s.
Brojrpozvaooduzeti brojeviamodulostr(drugim riječima, brojrzove ostatak brojaaonstr).
Izjava 2. Ako dva brojaaIbuporedivi po modulustr, Toa−bpodijeljenastr.
Zaista. Ako dva brojaaIbuporedivi po modulustr, zatim kada se podijeli sastrimaju isti ostatakstr. Onda
GdjesIs1 neki cijeli brojevi.
Razlika ovih brojeva
| (3) |
podijeljenastr, jer desna strana jednačine (3) je podijeljena sastr.
Izjava 3. Ako je razlika dva broja djeljiva sastr, onda su ovi brojevi uporedivi po modulustr.
Dokaz. Označimo sarIr1 ostatke podjeleaIbonstr. Onda
gdje
Premaa−bpodijeljenastr. Dakler− r1 je također djeljiv sastr. Ali zatorIr1 brojevi 0,1,...,str−1, tada apsolutna vrijednost |r− r1 |< str. Zatim, da bir− r1 podijeljenastruslov mora biti ispunjenr= r1 .
Iz tvrdnje proizilazi da su uporedivi brojevi oni brojevi čija je razlika djeljiva modulom.
Ako treba da zapišete te brojeveaIbuporedivi po modulustr, tada koristimo notaciju (koju je uveo Gauss):
| a≡bmod (str) |
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. Zaista, 25 = 3·7+4 (ostatak 4). 39=3·7+4 (ostatak 4). Kada razmatrate drugi primjer, morate 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). Stoga, −18 kada se podijeli sa 4 ostavlja ostatak od 2, a 14 kada se podijeli sa 4 ostavlja ostatak od 2.
Svojstva modulo poređenja
Nekretnina 1. Za bilo kogaaIstrUvijek
| a≡amod (str). |
Nekretnina 2. Ako dva brojaaIcuporedivo sa brojembmodulostr, ToaIcmeđusobno uporedivi prema istom modulu, tj. Ako
| a≡bmod (str), b≡cmod (str). |
To
| a≡cmod (str). |
Zaista. Iz stanja imovine 2 proizilazia−bIb−cse dijele nastr. Zatim njihov zbira−b+(b−c)=a−ctakođe podeljen nastr.
Nekretnina 3. Ako
| a≡bmod (str) Im≡nmod (str), |
To
| a+m≡b+nmod (str) Ia−m≡b−nmod (str). |
Zaista. Jera−bIm−nse dijele nastr, To
| ( a−b)+ ( m−n)=( a+m)−( b+n) , |
| ( a−b)−( m−n)=( a−m)−( b−n) |
takođe podeljen nastr.
Ovo svojstvo se može proširiti na bilo koji broj poređenja koja imaju isti modul.
Nekretnina 4. Ako
| a≡bmod (str) Im≡nmod (str), |
To
Daljem−npodijeljenastr, dakleb(m−n)=bm−bntakođe podeljen nastr, znači
| bm≡bnmod (str). |
Dakle, dva brojaamIbnuporediv po modulu sa istim brojembm, stoga su međusobno uporedivi (svojstvo 2).
Nekretnina 5. Ako
| a≡bmod (str). |
To
| ak≡bkmod (str). |
Gdjekneki nenegativni cijeli broj.
Zaista. Imamoa≡bmod (str). Iz imovine 4 slijedi
| ................. |
| ak≡bkmod (str). |
Predstavite sva svojstva 1-5 u sljedećoj izjavi:
Izjava 4. Nekaf( x1 , x2 , x3 , ...) je cijela racionalna funkcija s cjelobrojnim koeficijentima i neka
| a1 ≡ b1 , a2 ≡ b2 , a3 ≡ b3 , ... mod (str). |
Onda
| f( a1 , a2 , a3 , ...)≡ f( b1 , b2 , b3 , ...) mod (str). |
Sa podjelom je sve drugačije. Iz poređenja
Izjava 5. Neka
Gdjeλ Ovonajveći zajednički djeliteljbrojevimIstr.
Dokaz. Nekaλ najveći zajednički djelitelj brojevamIstr. Onda
Jerm(a−b)podijeljenak, To
ima nulti ostatak, tj.m1 ( a−b) podijeljenak1 . Ali brojevim1 Ik1 brojevi su relativno prosti. Daklea−bpodijeljenak1 = k/λi onda,p,q,s.
Zaista. Razlikaa≡bmora biti višestruki odp,q,s.i stoga mora biti višestrukah.
U posebnom slučaju, ako su modulip,q,sonda koprosti brojevi
| a≡bmod (h), |
Gdjeh=pqs.
Imajte na umu da možemo dozvoliti poređenja na osnovu negativnih modula, tj. poređenjea≡bmod (str) znači u ovom slučaju da je razlikaa−bpodijeljenastr. Sva svojstva poređenja ostaju na snazi za negativne module.
Poređenje sa jednom nepoznatom x izgleda kao
Gdje . Ako a n nije djeljivo sa m, tako se zove stepen poređenja.
Odlukom poređenje je bilo koji cijeli broj x 0 , za koji
Ako X 0 zadovoljava poređenje, onda su, prema svojstvu 9 poređenja, svi cijeli brojevi uporedivi sa x 0 modulo m. Dakle, sva rješenja poređenja koja pripadaju istoj klasi ostatka po modulu T, mi ćemo to smatrati kao jedno rješenje. Dakle, poređenje ima onoliko rješenja koliko ima elemenata kompletnog sistema ostataka koji ga zadovoljavaju.
Pozivaju se poređenja čiji se skupovi rješenja poklapaju ekvivalentno.
2.2.1 Poređenja prvog stepena
Poređenje prvog stepena sa jednom nepoznatom X izgleda kao
(2.2)
Teorema 2.4. Da bi poređenje imalo barem jedno rješenje, potrebno je i dovoljno da broj b podijeljeno sa GCD( a, m).
Dokaz. Prvo dokazujemo neophodnost. Neka d
=
GCD( a,
m)
I X 0
- rešenje za poređenje. Onda 
, odnosno razlika Oh 0
−
b
podijeljena T. Dakle, postoji takav cijeli broj q,
Šta Oh 0
−
b
=
qm.
Odavde b= ah 0
−
qm.
I od tada d,
kao zajednički djelitelj, dijeli brojeve A I T, tada se minuend i subtrahend dijele sa d,
i zbog toga b
podijeljena d.
Sada dokažemo dovoljnost. Neka d- najveći zajednički djelitelj brojeva A I T, I b podijeljena d. Tada, prema definiciji djeljivosti, postoje sljedeći cijeli brojevi a 1 , b 1 ,T 1 , Šta .
Koristeći prošireni Euklidski algoritam, nalazimo linearni prikaz broja 1 = gcd( a 1 , m 1 ):
za neke x 0 , y 0 . Pomnožimo obje strane posljednje jednakosti sa b 1 d:
ili, šta je isto,
,
odnosno i predstavlja rešenje za poređenje. □
Primjer 2.10. Poređenje 9 X= 6 (mod 12) ima rješenje jer je gcd(9, 12) = 3 i 6 je deljivo sa 3. □
Primjer 2.11. Poređenje 6x= 9 (mod 12) nema rješenja, jer je gcd(6, 12) = 6, a 9 nije djeljivo sa 6. □
Teorema 2.5. Neka je poređenje (2.2) rješivo i d = GCD( a, m). Tada se skup rješenja poređenja (2.2) sastoji od d modulo klase ostataka T, naime, ako X 0 - jedno od rješenja, onda su sva ostala rješenja
Dokaz. Neka X 0
- rješenje poređenja (2.2), tj 
I ,
.
Dakle, postoji takva stvar q, Šta Oh 0
−
b
=
qm.
Sada zamijenite posljednju jednakost umjesto X 0
proizvoljno rješenje oblika, gdje, dobijamo izraz
, djeljivo sa m. □
Primjer 2.12. Poređenje 9 X=6 (mod 12) ima tačno tri rješenja, pošto je gcd(9, 12)=3. Ova rješenja: X 0 = 2, x 0 + 4 = 6, X 0 + 2∙4=10.□
Primjer 2.13. Poređenje 11 X=2 (mod 15) ima jedinstveno rješenje X 0 = 7, budući da je GCD(11,15)=1.□
Pokazat ćemo vam kako riješiti poređenja prvog stepena. Bez gubitka općenitosti, pretpostavit ćemo da je GCD( a, t) = 1. Tada se rješenje za poređenje (2.2) može tražiti, na primjer, korištenjem Euklidovog algoritma. Zaista, koristeći prošireni Euklidski algoritam, broj 1 predstavljamo kao linearnu kombinaciju brojeva a I T:
Pomnožimo obje strane ove jednakosti sa b, dobijamo: b = abq + mrb, gdje abq - b = - mrb, to je a ∙ (bq) = b(mod m) I bq- rješenje poređenja (2.2).
Drugo rješenje je korištenje Ojlerove teoreme. Opet vjerujemo da GCD(a, T)= 1. Primjenjujemo Ojlerovu teoremu: 
. Pomnožite obje strane poređenja sa b:
.
Prepisivanje posljednjeg izraza kao 
, dobijamo da je to rješenje za poređenje (2.2).
Neka sada GCD( a, m) = d>1. Onda a = atd, m = mtd, gdje je GCD( A 1 , m 1) = 1. Osim toga, neophodno je b = b 1 d, kako bi poređenje bilo razrješivo. Ako X 0 - rešenje za poređenje A 1 x = b 1 (mod m 1), i jedini, od GCD( A 1 , m 1) = 1, dakle X 0 biće rešenje i poređenje A 1 xd = db 1 (mod m 1), odnosno originalno poređenje (2.2). Odmori se d- 1 rješenje je pronađeno po teoremi 2.5.
Ako su dva cijela broja a (\displaystyle a) I b (\displaystyle b) at divizije on m (\displaystyle m) daju identične ostatke, nazivaju se uporedivi(ili podjednako rezidualno) modulo broj m (\displaystyle m) . Šablon:/okvir Uporedivost brojeva a (\displaystyle a) I b (\displaystyle b) napisano kao formula ( poređenja):
Broj m (\displaystyle m) pozvao modul poređenja.
Definicija uporedivost brojevi a (\displaystyle a) I b (\displaystyle b) modulo m (\displaystyle m) ekvivalentno bilo koja od sljedećih izjava:
Dokaz
Pored gore navedenih svojstava, sljedeće tvrdnje su važeće za poređenje:
Dokaz
a ≡ b (mod m) . (\displaystyle a\equiv b(\pmod (m)).)dakle,
a − b = m t . (\displaystyle a-b=mt.)Jer d (\displaystyle d) je razdjelnik brojevi m (\displaystyle m), To
m = c d (\displaystyle m=cd).dakle,
a − b = m t = c d t = q d , (q = c t) (\displaystyle a-b=mt=cdt=qd,(q=ct)) a ≡ b (mod d) (\displaystyle a\equiv b(\pmod (d)))a-priorat.
Dokaz
a ≡ b (mod m i) , i = 1 , 2 , . . . , k . (\displaystyle a\equiv b(\pmod (m_(i))),i=1,2,...,k.)dakle,
a − b = m i t . (\displaystyle a-b=m_(i)t.)Od razlike a − b (\displaystyle a-b) je višekratnik svakog, onda je višestruki od njih najmanje uobičajeno više
Posljedica: U redu za brojeve a (\displaystyle a) I b (\displaystyle b) bili uporedivi po modulu m (\displaystyle m), kanonska dekompozicijačiji primarni faktori imaju oblik m = ∏ i = 1 d p i α i , (\displaystyle m=\prod _(i=1)^(d)p_(i)^(\alpha _(i)),)neophodno i dovoljno za
a ≡ b (mod p i α i) , i = 1 , 2 , … , d (\displaystyle a\equiv b(\pmod (p_(i)^(\alpha _(i)))),\quad i= 1,2,\tačke ,d) .Operacije sa poređenjem
Poređenja s obzirom na isti modul imaju mnoga svojstva običnih jednakosti. Na primjer, mogu se sabirati, oduzimati i množiti: ako su brojevi a 1 , a 2 , . . . , a n (\displaystyle a_(1),a_(2),...,a_(n)) I b 1 , b 2 , . . . , b n (\displaystyle b_(1),b_(2),...,b_(n)) parno uporedivi po modulu m (\displaystyle m), zatim njihove sume a 1 + a 2 + . . . + a n (\displaystyle a_(1)+a_(2)+...+a_(n)) I b 1 + b 2 + . . . + b n (\displaystyle b_(1)+b_(2)+...+b_(n)), kao i radovi a 1 ⋅ a 2 ⋅ . . . ⋅ a n (\displaystyle a_(1)\cdot a_(2)\cdot ...\cdot a_(n)) I b 1 ⋅ b 2 ⋅ . . . ⋅ b n (\displaystyle b_(1)\cdot b_(2)\cdot ...\cdot b_(n)) su takođe uporedivi u modulu m (\displaystyle m). Međutim, ne možete izvršiti ove operacije s poređenjem ako se njihovi moduli ne podudaraju.
Posebno treba napomenuti da se u oba dijela poređenja može dodati isti broj, a možete i prenijeti broj iz jednog dijela poređenja u drugi s promjenom predznaka. Ako su brojevi a (\displaystyle a) I b (\displaystyle b) uporedivi po modulu m (\displaystyle m), zatim njihove diplome a k (\displaystyle a^(k)) I b k (\displaystyle b^(k)) su takođe uporedivi u modulu m (\displaystyle m) pod bilo kojim prirodnim k (\displaystyle k) .
Bilo kojem od dijelova poređenja možete dodati cjelobrojni umnožak modula, odnosno ako su brojevi a (\displaystyle a) I b (\displaystyle b) uporediv po modulu neki broj m (\displaystyle m), onda a + t 1 (\displaystyle a+t_(1)) uporedivi sa b + t 2 (\displaystyle b+t_(2)) modulo m (\displaystyle m) (t 1 (\displaystyle t_(1)) I t 2 (\displaystyle t_(2))- proizvoljno cijeli brojevi).Takođe, oba dijela poređenja i modul mogu se pomnožiti istim brojem, odnosno ako su brojevi a (\displaystyle a) I b (\displaystyle b) uporedivi modulo neki cjelina brojevi m (\displaystyle m), zatim brojevi a q (\displaystyle aq) I b q (\displaystyle bq) brojevi su uporedivi po modulu m q (\displaystyle mq),Gdje q (\displaystyle q) - cijeli.
Međutim, poređenja se, općenito govoreći, ne mogu podijeliti jedno s drugim ili drugim brojevima. primjer: 14 ≡ 20 (mod 6) (\displaystyle 14\equiv 20(\pmod (6))), međutim, smanjivanjem za 2, dobijamo pogrešno poređenje: 7 ≡ 10 (mod 6) (\displaystyle 7\equiv 10(\pmod (6))). Pravila skraćenica za poređenje su sljedeća.
- Obje strane poređenja možete podijeliti brojem, ali samo uzajamno prime sa modulom: if
Ako, broj d (\displaystyle d) Ne obostrano pravedno sa modulom, kao što je bio slučaj u gornjem primjeru, zatim smanjite za d (\displaystyle d) zabranjeno je.
- Možete istovremeno podijeliti obje strane poređenja i modul njihovim zajedničkim djeliteljem:
Ako a c ≡ b c (mod m c) (\displaystyle (ac)\equiv (bc)(\pmod (mc))), To a ≡ b (mod m) (\displaystyle a\equiv b(\pmod (m))) .
Povezane definicije
Odbici
Skup svih brojeva uporedivih sa a (\displaystyle a) modulo m (\displaystyle m), zvao klasa odbitka a (\displaystyle a) modulo m (\displaystyle m) , i obično se označava [ a ] m (\displaystyle [a]_(m)) ili a ¯ m (\displaystyle (\bar (a))_(m)). Dakle poređenje a ≡ b (mod m) (\displaystyle a\equiv b(\pmod (m))) je ekvivalentna jednakosti klasa ostataka [ a ] m = [ b ] m (\displaystyle [a]_(m)=[b]_(m)) .
Poziva se bilo koji broj razreda oduzeti modulo m (\displaystyle m). Neka za sigurnost r (\displaystyle r)―ostatak divizije bilo koji od predstavnika odabrane klase na m (\displaystyle m), zatim bilo koji broj q (\displaystyle q) iz ove klase može se predstaviti kao q = m t + r (\displaystyle q=mt+r), Gdje t (\displaystyle t) -cijeli. Odbitak jednak podsjetnik r (\displaystyle r) pozvao najmanji nenegativni odbitak, i odbitak ρ (\displaystyle \rho ), najmanja po apsolutnoj vrijednosti, naziva se apsolutno najmanji odbitak. At r< m 2 {\displaystyle r<{\frac {m}{2}}} mi to shvatamo ρ = r (\displaystyle \rho =r), inače ρ = r − m (\displaystyle \rho =r-m). Ako m (\displaystyle m)-čak I r = m 2 (\displaystyle r=(\frac (m)(2))), To ρ = − m 2 (\displaystyle \rho =-(\frac (m)(2))) .
Pošto modulo uporedivost m (\displaystyle m) je odnos ekvivalencije na skupu cijelih brojeva, zatim modulo klase ostataka m (\displaystyle m) predstavljaju klase ekvivalencije; njihov broj je jednak m (\displaystyle m).
Skup svih klasa ostataka po modulu m (\displaystyle m) označeno sa ili Z / m Z (\displaystyle \mathbb (Z) /m\mathbb (Z) ) ili Z / (m) (\displaystyle \mathbb (Z) /(m)) .
Operacije sabiranja i množenja sa Z (\displaystyle \mathbb (Z) ) inducirati odgovarajuće operacije na skupu Z m (\displaystyle \mathbb (Z)_(m)):
[ a ] m + [ b ] m = [ a + b ] m (\displaystyle [a]_(m)+[b]_(m)=_(m)) [ a ] m ⋅ [ b ] m = [ a ⋅ b ] m (\displaystyle [a]_(m)\cdot [b]_(m)=_(m))Što se tiče ovih operacija, ima ih mnogo Z m (\displaystyle \mathbb (Z)_(m)) je konačan prsten, i za jednostavno m (\displaystyle m) - konačno polje.
Sistemi odbitka
Sistem ostataka vam omogućava da izvodite aritmetičke operacije na konačnom skupu brojeva bez prelaska njegovih granica. Potpuni sistem odbitaka modulo m (\displaystyle m)- bilo koji set m (\displaystyle m) parno neuporediv modul m (\displaystyle m) cijeli brojevi. Obično kao kompletan sistem modulo odbitaka m (\displaystyle m) uzima se jedan od dva seta:
- najmanje nenegativnih ostataka, odnosno brojevi:
- ili apsolutno minimalni odbici, koji se sastoji od brojeva
Maksimalni skup parno neuporedivih modula m (\displaystyle m) brojevi, uzajamno prime With m (\displaystyle m), zvao dati sistem odbitaka modulo m (\displaystyle m). Bilo koji redukovani sistem modulo ostataka m (\displaystyle m) sadrži φ (m) (\displaystyle \varphi (m)) elemenata, gdje φ (⋅) (\displaystyle \varphi (\cdot)) - Eulerova funkcija.
Na primjer, za broj m = 42 (\displaystyle m=42). Potpuni sistem odbitaka može se predstaviti brojevima: 0 , 1 , 2 , 3 , … , 21 , 22 , 23 , … , 39 , 40 , 41 (\displaystyle 0,1,2,3,\ldots ,21,22,23,\ldots ,39,40, 41), A dato - 1 , 5 , 11 , 13 , 17 , 19 , 23 , 25 , 29 , 31 , 37 , 41 (\displaystyle 1,5,11,13,17,19,23,25,29,31,37,41).
Poređenja u prstenu polinoma nad poljem
Rješavanje poređenja
Poređenja prvog stepena
IN teorija brojeva , kriptografija i drugim oblastima nauke, često se nameće zadatak pronalaženja rešenja za prvostepena poređenja oblika:
a x ≡ b (mod m) . (\displaystyle ax\equiv b(\pmod (m)).)Rješavanje takvog poređenja počinje računanjem d = (\displaystyle d=) GCD (a, m) (\displaystyle (a,m)). U ovom slučaju moguća su 2 slučaja:
a 1 x ≡ b 1 (mod m 1) (\displaystyle a_(1)x\equiv b_(1)(\pmod (m_(1)))) Gdje a 1 = a d (\displaystyle a_(1)=(\frac (a)(d))), b 1 = b d (\displaystyle b_(1)=(\frac (b)(d))) I m 1 = m d (\displaystyle m_(1)=(\frac (m)(d))) su cijeli brojevi, i m 1 (\displaystyle m_(1)) međusobno jednostavno. Stoga broj a 1 (\displaystyle a_(1)) može se invertirati po modulu m 1 (\displaystyle m_(1)), odnosno pronaći takav broj c (\displaystyle c), Šta c ⋅ a 1 ≡ 1 (mod m 1) (\displaystyle c\cdot a_(1)\equiv 1(\pmod (m_(1))))(drugim riječima, c ≡ a 1 − 1 (mod m 1) (\displaystyle c\equiv a_(1)^(-1)(\pmod (m_(1))))). Sada se rješenje nalazi množenjem rezultirajućeg poređenja sa c (\displaystyle c): x ≡ c a 1 x ≡ c b 1 ≡ a 1 − 1 b 1 (mod m 1) . (\displaystyle x\equiv ca_(1)x\equiv cb_(1)\equiv a_(1)^(-1)b_(1)(\pmod (m_(1))).)Praktično izračunavanje vrijednosti c (\displaystyle c) može se izvršiti na različite načine: korištenjem Ojlerova teorema , Euklidski algoritam, teorije kontinuirani razlomci(cm. algoritam) itd. Posebno, Ojlerova teorema omogućava vam da upišete vrijednost c (\displaystyle c) kao:
c ≡ a 1 − 1 ≡ a 1 φ (m 1) − 1 (mod m 1) (\displaystyle c\equiv a_(1)^(-1)\equiv a_(1)^(\varphi (m_(1) ))-1)(\pmod (m_(1)))) .Primjeri
Primjer 1. Za poređenje
6 x ≡ 26 (mod 22) (\displaystyle 6x\equiv 26(\pmod (22)))imamo d = 2 (\displaystyle d=2), dakle po modulu 22 poređenje ima dva rješenja. Zamenimo 26 sa 4, što je uporedivo po modulu 22, a zatim smanjimo sva tri broja za 2:
3 x ≡ 2 (mod 11) (\displaystyle 3x\equiv 2(\pmod (11)))Budući da je 3 kopriman modulu 11, može se invertirati po modulu 11 i naći
3 − 1 ≡ 4 (mod 11) (\displaystyle 3^(-1)\equiv 4(\pmod (11))).Pomnožeći poređenje sa 4, dobijamo rešenje po modulu 11:
x ≡ 8 (mod 11) (\displaystyle x\equiv 8(\pmod (11))),ekvivalentno kombinaciji dva rješenja po modulu 22:
x ≡ 8 (mod 22) (\displaystyle x\equiv 8(\pmod (22))) I x ≡ 19 (mod 22) (\displaystyle x\equiv 19(\pmod (22))).Primjer 2. Dato poređenje:
100 x ≡ 41 (mod 65537) . (\displaystyle 100x\ekviv. 41(\pmod (65537)).) Imajte na umu da je modul prost broj.Prvo rješenje je korištenje omjer bez. Korišćenjem Euklidski algoritam ili programa datog u članku o Bezoutovoj relaciji, nalazimo da je to relacija za brojeve 100 (\displaystyle 100) I 65537 (\displaystyle 65537) ima oblik:
17695 ⋅ 100 + (− 27) ⋅ 65537 = 1 , (\displaystyle 17695\cdot 100+(-27)\cdot 65537=1,) ili 17695 ⋅ 100 ≡ 1 (mod 65537) (\displaystyle 17695\cdot 100\equiv 1(\pmod (65537)))Pomnožimo obe strane ovog poređenja sa 41, dobijamo:
100 ⋅ 725495 ≡ 41 (mod 65537) (\displaystyle 100\cdot 725495\equiv 41(\pmod (65537)))Iz toga slijedi da postoji rješenje za originalno poređenje. Pogodnije ga je zamijeniti nečim sličnim 4588 (\displaystyle 4588)(ostatak divizije 725495 (\displaystyle 725495) on 65537 (\displaystyle 65537)). odgovor: x ≡ 4588 (mod 65537) . (\displaystyle x\equiv 4588(\pmod (65537)).)
Druga metoda rješenja, jednostavnija i brža, ne zahtijeva konstrukciju Bezoutove relacije, ali je također ekvivalentna Euklidskom algoritmu.
Korak 1. Podijelite modul koeficijentom od x sa ostatkom: 65537 = 100 ⋅ 655 + 37 (\displaystyle 65537=100\cdot 655+37). Pomnožite obje strane originalnog poređenja s količnikom 655 (\displaystyle 655) i dodati 37 x (\displaystyle 37x); dobijamo: 65537 x ≡ 26855 + 37 x (mod 65537) (\displaystyle 65537x\equiv 26855+37x(\pmod (65537))), ali lijeva strana je višestruka 65537 (\displaystyle 65537), odnosno uporedivo sa nulom, od čega:
37 x ≡ − 26855 (mod 65537) (\displaystyle 37x\equiv -26855(\pmod (65537)))Primili smo u x (\displaystyle x) koeficijent 37 umjesto 100. U svakom sljedećem koraku smanjujemo na isti način dok ne dobijemo jedan.
Korak 2. Slično, podijelite s novim koeficijentom za x: 65537 = 37 ⋅ 1771 + 10 (\displaystyle 65537=37\cdot 1771+10). Pomnožimo obje strane poređenja dobivene u prethodnom koraku količnikom 1771 (\displaystyle 1771) i dodati 10 x (\displaystyle 10x); ponovo zamjenjujući lijevu stranu sa nulom, dobijamo.