desno|sličica|250x250_pik|Ustaljen čas na tej se lahko izvaja z uporabo aritmetičnega modula 12. V matematiki je modularna aritmetika sistem aritmetike za cela števila, kjer se števila "ponovno vrtijo okoli", ko dosežejo določeno vrednost, ki se imenuje modulo (ali modul). Moderni približek modularni aritmetiki je uveljavil Carl Friedrich Gauss v svoji knjigi Disquisitiones Arithmeticae, ki jo je izdal leta 1801.
Vsem poznana uporaba modularne aritmetike je 12-urna ura, kjer je dan razdeljen na dve 12-urni periodi. Če je sedaj ura 7:00, bo čez 8 ur enaka 3:00. Navadno seštevanje bi nam dalo rezultat , a to ne bo odgovor, ker se čas po uri "obrne naokoli" na vsakih 12 ur. Ker se številke na uri ponastavijo, ko pridejo do 12, ima ura aritmetični modul enak 12. Če to izrazimo s spodnjo definicijo, je 15 kongruentno 3 v modulu 12, torej je (24-urni) čas "15:00" enak času "3:00" na uri.
Definicije relacij v konguencah Modularna aritmetika se lahko obravnava matematično z vpeljavo kongruenčne relacije na celih številih, ki se da združiti z operacijami na celih številih: seštevanje, odštevanje in množenje. Za naravno število , sta dve števili in , če je njuna razlika celi večkratnik od (torej če obstaja tako celo število , da velja ). Ta kongruenčna relacija se običajno šteje, ko sta in celi števili, označi pa se jo z:
Oklepaji pomenijo, da velja za celo enačbo, ne samo za desno stran (v tem primeru b). Včasih se uporablja tudi namesto . Če se oklepaje izpusti, pomeni to v splošnem, da označuje "mod" operacijo modulo, ki se nanaša samo na desno stran, spremeni pa se tudi v enakost, da velja .
Število se imenuje modul kongruence.
Kongruenčna relacija se lahko zapiše tudi kot
kar eksplicitno prikaže Evklidsko deljenje. Kaj pa če ni ostanek števila pri deljenju z ? Bolj natančno lahko relacijo opišemo tako, da morata tako , kot tudi imeti enak ostanek pri deljenju z . Torej
kjer je skupni delitelj. Če odštejemo ta dva izraza, pridemo do prejšnje relacije:
kjer definiramo
Primeri Na primer
ker je , kar je večkratnik od 12, ali, ekvivalentno, ker imata tako 38, kot tudi 14 enak ostanek 2 pri deljenju z 12.
Enako pravilo velja tudi za negativne vrednosti:
Ker se lahko pogosto pojavi več relacij, kjer so različni moduli naenkrat, smo v zgornji sistem vedno zapisali modulo. Kongruenčna relacija za dani modul velja za binarno relacijo.
Lastnosti Kongruenčna relacija zadovolji vsem pogojem za ekvivalenčno relacijo:
Refleksivnost: Simetrija: če za vse , in . Tranzitivnost: Če in , potem
Če velja in ali če velja potem:
za katerokoli celo število (kar se sklada s premikom) za katerokoli celo število (kar je skladno s povečanjem) (skladno s seštevanjem) (skladno z odštevanjem) (skladno z množenjem) za katerokoli nenegativno celo število (skladno s potenciranjem) , za katerikoli polinom s celimi koeficienti (kar je skladno s polinomsko evaluacijo)
Če je , potem v splošnem ni pravilno . A to velja, če velja sledeči pogoj:
Če velja kjer je Eulerjeva funkcija, potem , če je tuja z
Za pokrajšanje skupnih členov, poznamo sledeča pravila:
Če je za katerokoli celo število , potem je Če je in sta si in tuji si števili, potem je
Modularni multiplikativni inverz je definiran s sledečimi pravili:
Obstoj: obstaja celo število, ki je označeno z , da velja če in samo če je tuje z . To število se imenuje modularni multiplikativni inverz modula . Če je in obstaja , potem je (skladno z multiplikativnim inverzom in če ima edinstven modul ) Če je in je tuje , potem je rešitev te linearne kongruence podana z
Multiplikativni inverz se lahko učinkovito izračuna z uporabo Bézoutove identitete za z uporabo razširjenega Evklidovega algoritma. V posebnem, če je praštevilo, potem sta si in tuji za vsak , da velja ; torej multiplikativni inverz obstaja za vse , ki niso kongruentni ničelnemu modulu .
Nekaj nekaterih bolj naprednih lastnosti kongruenčnih relacij je zbranih tukaj:
Fermatov mali izrek: Če je praštevilo in ne deli , potem . Eulerjev izrek: Če sta si in tuji si števili, potem velja , kjer je Eulerjeva funkcija fi Preprosta posledica Fermatovega malega izreka je: če je praštevilo, potem je multiplikativni inverz od . Še bolj splošno iz Eulerjevega izreka: če sta si in tuji, potem je . Druga preprosta posledica je, da če velja kjer je Eulerjeva fi funkcija, potem velja , kjer je tuje z . Wilsonov izrek: je praštevilo, če in samo če velja . Kitajski izrek o ostankih: Za katerakoli in ter tuji števili in , obstaja unikatno celo število , da velja in . Velja tudi , kjer je inverz od modulo in je inverz od modulo . Lagrangeov izrek: Kongruenca , kjer je praštevilo in je polinom s celimi koeficienti, da ima največ korenov. Primitivni koren modula n: Število je primitivni koren modula , če obstaja za vsako celo število , ki je tuje , neko celo število , da velja . Primitivni koren modula obstaja če in samo če je enak ali , kjer je liho praštevilo in je naravno število. Če obstaja primitivni koren modula , potem obstaja natanko takšnih primitivnih korenov, kjer je Eulerjeva fi funkcija. Kvadratični ostanek: Celo število je kvadratični ostanek modula , če obstaja tako celo število , da velja . Eulerjev kriterij nam pravi, da če je liho praštevilo in a ni večkratnik od p, potem je kvadratični ostanek modula če in samo če
Kongruenčni razredi Kot katerakoli kongruenčna relacija, je kongruenčni modulo ekvivalenčna relacija ter ekvivalenčni razred celega števila , ki se označi z , je množica . Ta množica, ki jo sestavljajo cela števila, ki so kongruentna po modulu , se imenuje kongruenčni razred ali razred ostankov ali preprosto ostanek celega števila , po modulu . Če je modulo razpoznaven iz besedila, se lahko ta ostanek označi z .
Primeri implementacij Spodaj so tri dokaj hitre funkcije v jeziku C, dve za izvajanje modularnih množenj in ena za izvajanje modularnega potenciranja na neoznačenih celih (naravnih) številih, ki niso večja od 63 bitov.
Algoritemski način za izračunanje :uint64_t mul_mod(uint64_t a, uint64_t b, uint64_t m) { uint64_t d = 0, mp2 = m >> 1; int i; if (a >= m) a %= m; if (b >= m) b %= m; for (i = 0; i < 64; ++i)
d = (d > mp2) ? (d << 1) - m : d << 1; if (a & 0x8000000000000000ULL) d += b; if (d >= m) d -= m; a <<= 1;
return d; }Na računalnikih, kjer je mogoča tudi razširjena natančnost z najmanj 64 biti mantise (kot recimo tip long double na večini x86 C prevajalnikih), se lahko uporabi sledeča implementacija, saj po trdih komponentah množenje plavajoče vejice vodi v obdržane najbolj zanesljive bite, medtem ko množenje celih števil vodi v obdržane najmanj zanesljive bite:uint64_t mul_mod(uint64_t a, uint64_t b, uint64_t m) { long double x; uint64_t c; int64_t r; if (a >= m) a %= m; if (b >= m) b %= m; x = a; c = x * b / m; r = (int64_t)(a * b - c * m) % (int64_t)m; return r < 0 ? r + m : r; }Spodnja je C funkcija za izvajanje modularnega potenciranja, ki uporablja funkcijo , ki je bila implementirana zgoraj.
Algoritemski način za izračunanje :uint64_t pow_mod(uint64_t a, uint64_t b, uint64_t m) { uint64_t r = m==1?0:1; while (b > 0) { if (b & 1) r = mul_mod(r, a, m); b = b >> 1; a = mul_mod(a, a, m);
return r; }A da bi vse zgornje poti delovale, ne sme prekoračiti 63 bitov.
Glej tudi
Booleanov obroč Krožno blažilnik Deljenje (matematika) Končno polje Legendrov simbol Modularno potenciranje Pisanova perioda (Fibonaccijevo zaporedje modula n) Primitivni koren modula n Kvadratna recipročnost Kvadratni ostanek Racionalna rekonstrukcija (matematika) Zmanjšani sistem ostankov Aritmetika serijskih števil (poseben primer modularne aritmetike) Booleanova algebra dveh elementov Področja, ki se nanašajo na teorijo grup za modularno aritmetiko: Ciklična grupa Multiplikativna grupa celih števil modula n Ostali pomembni izreki, ki se nanašajo na modularno aritmetiko: Carmichaelov izrek Kitajski izrek o ostankih Eulerjev izrek Fermatov mali izrek (posebni primer Eulerjevega izreka) Lagrangeov izrek Thueova lema
Sklici
Viri
John L. Berggren. "modular arithmetic". Encyclopædia Britannica. Apostol, Tom M. (1976), Introduction to analytic number theory, Undergraduate Texts in Mathematics, New York-Heidelberg: Springer-Verlag, ISBN 978-0-387-90163-3, MR 0434929, Zbl 0335.10001. See in particular chapters 5 and 6 for a review of basic modular arithmetic. Maarten Bullynck "Modular Arithmetic before C.F. Gauss. Systematisations and discussions on remainder problems in 18th-century Germany" Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 31.3: Modular arithmetic, pp. 862–868. Anthony Gioia, Number Theory, an Introduction Reprint (2001) Dover. ISBN 0-486-41449-3.
Zunanje povezave
Hazewinkel, Michiel, ed. (2001) , "Congruence", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4 V tem članku o modularni umetnosti se lahko vsak nauči nekaj o uporabi modularne aritmetike v umetnosti.
Članek o modularni aritmetiki na wikiju GIMPS Modularna aritmetika in vzorci v seštevanju in tabele množenja
Kategorija:Teorija grup Kategorija:Končni kolobarji Kategorija:Modularna aritmetika