Modularna aritmetika
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 7 + 8 = 15, 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
urediModularna 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 n, sta dve števili a in b kongruentni v modulu n, če je njuna razlika a − b celi večkratnik od n (torej če obstaja tako celo število k, da velja a − b = kn). Ta kongruenčna relacija se običajno šteje, ko sta a in b celi števili, označi pa se jo z:
Oklepaji pomenijo, da (mod n) 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 0 ≤ a < n.
Število n se imenuje modul kongruence.
Kongruenčna relacija se lahko zapiše tudi kot
kar eksplicitno prikaže Evklidsko deljenje. Kaj pa če b ni ostanek števila a pri deljenju z n? Bolj natančno lahko relacijo a ≡ b mod n opišemo tako, da morata tako a, kot tudi b imeti enak ostanek pri deljenju z n. Torej
kjer je 0 ≤ r < n skupni delitelj. Če odštejemo ta dva izraza, pridemo do prejšnje relacije:
kjer definiramo k = p − q.
Primeri
urediNa primer
ker je 38 − 14 = 24, 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
urediKongruenčna relacija zadovolji vsem pogojem za ekvivalenčno relacijo:
- Refleksivnost: a ≡ a (mod n)
- Simetrija: a ≡ b (mod n) če b ≡ a (mod n) za vse a, b in n.
- Tranzitivnost: Če a ≡ b (mod n) in b ≡ c (mod n), potem a ≡ c (mod n)
Če velja a1 ≡ b1 (mod n) in a2 ≡ b2 (mod n), ali če velja a ≡ b (mod n), potem:
- a + k ≡ b + k (mod n) za katerokoli celo število k (kar se sklada s premikom)
- k a ≡ k b (mod n) za katerokoli celo število k (kar je skladno s povečanjem)
- a1 + a2 ≡ b1 + b2 (mod n) (skladno s seštevanjem)
- a1 – a2 ≡ b1 – b2 (mod n) (skladno z odštevanjem)
- a1 a2 ≡ b1 b2 (mod n) (skladno z množenjem)
- ak ≡ bk (mod n) za katerokoli nenegativno celo število k (skladno s potenciranjem)
- p(a) ≡ p(b) (mod n), za katerikoli polinom p(x) s celimi koeficienti (kar je skladno s polinomsko evaluacijo)
Če je a ≡ b (mod n), potem v splošnem ni pravilno ka ≡ kb (mod n). A to velja, če velja sledeči pogoj:
- Če velja c ≡ d (mod φ(n)), kjer je φ Eulerjeva funkcija, potem ac ≡ ad (mod n), če je a tuja z n
Za pokrajšanje skupnih členov, poznamo sledeča pravila:
- Če je a + k ≡ b + k (mod n) za katerokoli celo število k, potem je a ≡ b (mod n)
- Če je k a ≡ k b (mod n) in sta si k in n tuji si števili, potem je a ≡ b (mod n)
Modularni multiplikativni inverz je definiran s sledečimi pravili:
- Obstoj: obstaja celo število, ki je označeno z a–1, da velja aa–1 ≡ 1 (mod n) če in samo če je a tuje z n. To število a–1 se imenuje modularni multiplikativni inverz modula n.
- Če je a ≡ b (mod n) in obstaja a–1, potem je a–1 ≡ b–1 (mod n) (skladno z multiplikativnim inverzom in če ima a = b edinstven modul n)
- Če je a x ≡ b (mod n) in a je tuje n, potem je rešitev te linearne kongruence podana z x ≡ a–1b (mod n)
Multiplikativni inverz x ≡ a–1 (mod n) se lahko učinkovito izračuna z uporabo Bézoutove identitete za z uporabo razširjenega Evklidovega algoritma. V posebnem, če je p praštevilo, potem sta si a in p tuji za vsak a, da velja 0 < a < p; torej multiplikativni inverz obstaja za vse a, ki niso kongruentni ničelnemu modulu p.
Nekaj nekaterih bolj naprednih lastnosti kongruenčnih relacij je zbranih tukaj:
- Fermatov mali izrek: Če je p praštevilo in ne deli a, potem a p – 1 ≡ 1 (mod p).
- Eulerjev izrek: Če sta si a in n tuji si števili, potem velja a φ(n) ≡ 1 (mod n), kjer je φ Eulerjeva funkcija fi
- Preprosta posledica Fermatovega malega izreka je: če je p praštevilo, potem je a−1 ≡ a p − 2 (mod p) multiplikativni inverz od 0 < a < p. Še bolj splošno iz Eulerjevega izreka: če sta si a in n tuji, potem je a−1 ≡ a φ(n) − 1 (mod n).
- Druga preprosta posledica je, da če velja a ≡ b (mod φ(n)), kjer je φ Eulerjeva fi funkcija, potem velja ka ≡ kb (mod n), kjer je k tuje z n.
- Wilsonov izrek: p je praštevilo, če in samo če velja (p − 1)! ≡ −1 (mod p).
- Kitajski izrek o ostankih: Za katerakoli a in b ter tuji števili m in n, obstaja unikatno celo število x (mod mn), da velja x ≡ a (mod m) in x ≡ b (mod n). Velja tudi x ≡ b mn–1 m + a nm–1 n (mod mn), kjer je mn−1 inverz od m modulo n in nm−1 je inverz od n modulo m.
- Lagrangeov izrek: Kongruenca f (x) ≡ 0 (mod p), kjer je p praštevilo in f (x) = a0 xn + ... + an je polinom s celimi koeficienti, da ima a0 ≠ 0 (mod p) največ n korenov.
- Primitivni koren modula n: Število g je primitivni koren modula n, če obstaja za vsako celo število a, ki je tuje n, neko celo število k, da velja gk ≡ a (mod n). Primitivni koren modula n obstaja če in samo če je n enak 2, 4, pk ali 2pk, kjer je p liho praštevilo in je k naravno število. Če obstaja primitivni koren modula n, potem obstaja natanko φ(φ(n)) takšnih primitivnih korenov, kjer je φ Eulerjeva fi funkcija.
- Kvadratični ostanek: Celo število a je kvadratični ostanek modula n, če obstaja tako celo število x, da velja x2 ≡ a (mod n). Eulerjev kriterij nam pravi, da če je p liho praštevilo in a ni večkratnik od p, potem je a kvadratični ostanek modula p če in samo če
Kongruenčni razredi
urediKot katerakoli kongruenčna relacija, je kongruenčni modulo n ekvivalenčna relacija ter ekvivalenčni razred celega števila a, ki se označi z an, je množica {… , a − 2n, a − n, a, a + n, a + 2n, …}. Ta množica, ki jo sestavljajo cela števila, ki so kongruentna a po modulu n, se imenuje kongruenčni razred ali razred ostankov ali preprosto ostanek celega števila a, po modulu n. Če je modulo n razpoznaven iz besedila, se lahko ta ostanek označi z [a].
Primeri implementacij
urediSpodaj 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 mul_mod, 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 m prekoračiti 63 bitov.
Glej tudi
uredi- 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:
- 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
urediViri
uredi- 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-7ISBN 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-3ISBN 0-486-41449-3.
- Long, Calvin T. (1972). Elementary Introduction to Number Theory (2. izd.). Lexington: D. C. Heath and Company. LCCN 77171950.
- Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970). Elements of Number Theory. Englewood Cliffs: Prentice Hall. LCCN 71081766.
- Sengadir, T. (2009). Discrete Mathematics and Combinatorics. Chennai, India: Pearson Education India. ISBN 978-81-317-1405-8. OCLC 778356123.
Zunanje povezave
uredi- Hazewinkel, Michiel, ed. (2001) [1994], "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.
- Weisstein, Eric Wolfgang. »Modular Arithmetic«. MathWorld.
- Članek o modularni aritmetiki na wikiju GIMPS
- Modularna aritmetika in vzorci v seštevanju in tabele množenja