Modularna aritmetika

S Wikipedije, slobodne enciklopedije
Idi na: navigaciju, pretragu
Question book-new.svg Ovaj članak ili neka od njegovih sekcija nije dovoljno potkrijepljena izvorima (literatura, web-stranice ili drugi izvori).
Ako se pravilno ne potkrijepe validnim izvorima, sporne rečenice i navodi mogli bi biti obrisani. Pomozite Wikipediji tako što ćete navesti validne izvore putem referenci te nakon toga možete ukloniti ovaj šablon.
Preferences-system.svg Ovom članku potrebna je jezička standardizacija, preuređivanje ili reorganizacija.
Pogledajte kako poboljšati članak, kliknite na link uredi i doradite članak vodeći računa o standardima Wikipedije.
Clock group.svg

Teorija kongruencija predstavlja još jedno naslijeđe Carla Friedricha Gaußa, koji je ovu tehniku, poznatu i pod nazivom modularna aritmetika, zasnovao u svom djelu Disquisitiones Arithmeticae, objavljenom 1801 [1]. Spomenuta knjiga se sastojala od sedam poglavlja, od kojih je prvih šest bilo posvećeno teoriji brojeva. Svakodnevni primjer ove teorije srećemo pri mjerenju vremena, gdje koristimo takozvanu aritmetiku modulo 12 dijeleći dan na dva perioda u trajanju od 12 sati.

Relacija ekvivalencije[uredi | uredi izvor]

Relacija biti kongruentan modulo n je relacija ekvivalencije[2]

  • refleksivna a / a ( mod n)
  • simetrija a / b ( mod n) =>b / a ( mod n)
  • tranzitivnost ( a / b ( mod n) & b /c( mod n) ) => a /c ( mod n)
Dokaz

Pokažimo najprije da je a kongruentno b modulo n ako i samo ako a i b daju isti ostatak pri dijeljenju s n.

Pretpostavimo da je a kongruentno b modulo n te, korištenjem teorema o dijeljenju s ostatkom, napišimo

, pri čemu vrijedi

Sada je .

Kako n dijeli , dobijamo da n dijeli i te iz .

Ako a i b daju isti ostatak pri dijeljenju sa n, na analogan način slijedi da n dijeli , tj.

Iz dokazanog slijedi

Iz ako i samo ako vrrijedi i ako i samo ako

Neka su sada a, b, c cijeli brojevi te neka vrijedi

i (a i b te b i c daju isti ostatak prije dijeljenju sa n)

Definicija[uredi | uredi izvor]

Definicija 1

Neka su a i b cijeli brojevi i m prirodan broj. Za brojeve a i b kažemo da su kongruentni po modulu m ako vrijedi

Definicija 2

Skup koji dobijamo ako svaki član skupa Z pomnožimo sa n različitim od 0 označavamo sa nZ tj. nZ = (....,-3n, -2n, -n, 0, n, 2n. ....) Skup koji dobijamo ako svakom članu skupa nZ dodamo r (0 ≤ r < │n│ označavamo nZ +r

Primjer
  • ,

Napomena

Budući da ako i samo ako , gdje je , dovoljno je posmatrati samo pozitivne brojeve n.

Osobine kongruencije[uredi | uredi izvor]

Propozicija 1
  • Neka su cijeli brojevi te prirodan broj. Neka je

i tada vrijedi

Dokaz

Neka je i .

dijeli pa je

  • Neka su cijeli brojevi i prirodan broj. Neka su brojevi i relativno prosti.

Tada vrijedi

Dokaz

Kako su i relativno prosti, postoje cijeli brojevi i takvi da je . Iz kongruencije => postoji cijeli broj takav da je . Množenjem prethodne jednakosti sa , iz dobijamo . Očito dijeli pa je

Ova tvrdnja ( ne vrijedi opčenito, tj. ako i nisu relativno prosti.

Primjer
  • tačno
  • nije tačno
Propozicija 2

Neka je Tada vrijedi i , gdje je .

Dokaz.

postoji cijeli broj takav da vrijedi Odatle je pa

Kako su i relativno prosti, jer nemaju zajedničkih prostih faktora, dobijamo n čime je tvrdnja dokazana.

Propozicija 3

Neka je prirodan broj te i cijeli brojevi takvi da je Tada za polinom s cjelobrojnim koeficijentima vrijedi

Dokaz primjenom predhodnih propozicija na dobijamo

te

saberemo li dobijene kongruencije dobijamo

Propozicija 4

Neka su prirodni brojevi. Tada su sljedeće tvrdnje ekvivalentne:

Primjer

odrediti za koji vrijedi

(340 je djeljivo sa17)tj

Kako je imamo

Datu kongruenciju zadovoljava svaki cijeli broj koji je kongruentan modulo , tj. .

Potpuni i reducirani sistem ostataka[uredi | uredi izvor]

Neka je prirodan broj veći od . Skup se naziva potpuni sistem ostataka modulo ako za svaki cijeli broj postoji jedinstveni za koji vrijedi .

Svaki potpuni sistem ostataka modulo ima tačno elemenata. Također, svaki n-člani skup koji se sastoji od cijelih brojeva međusobno nekongruentnih modulo predstavlja jedan potpuni sustem ostataka modulo .

Najčešće korišten potpun sistem ostataka modulo je skup

Navedimo i nekoliko potpunih sistema ostataka modulo 5: , , ,

Postoji ih beskonačno mnogo.

Lema 1

Neka je potpuni sistem ostataka modulo . Tada je i potpuni sistem ostataka modulo , za svaki cijeli broj za koji vrijedi .

Lema 2

Neka su i prirodni brojevi. Kongruencija ima rješenja ako i samo ako dijeli . Ako je rjšenje kongruencije tada su sva međusobno nekongruentna rješenja modulo polazne kongruencije data s

Primjer

Skupovi {1, 2, 3, 4} i {-2,-6, 6, 7} su reducirani sistemi ostataka modulo , dok je {1, 5} reducirani sistem ostataka modulo .

Eulerova funkcija[uredi | uredi izvor]

Glavni članak: Eulerova funkcija

Neka je n prirodan broj. Broj prirodnih brojeva u nizu 1, 2, . . . , n koji su relativno prosti sa n se označava s ovim je definisana funkcija koja se naziva Eulerova funkcija.

je broj elemenata reduciranog sistema ostataka modulo n.

Wilsonova i Lagrangeova teorema[uredi | uredi izvor]

Neka je p prost broj i a < p prirodan broj. Tada postoji prirodan broj b za koji vrijedi a · b ≡ 1 (mod p) i takav broj b se naziva multiplikativni inverz od a modulo p.

Kako su a i p relativno prosti, postoje cijeli brojevi x, y za koje vrijedi ax+py = 1, odakle slijedi ax ≡ 1 (mod p) te možemo uzeti b = x.

Svaka dva multiplikativna inverza od a modulo p međusobno su kongruentni modulo p, pa postoji jedinstveni multiplikativni inverz od a modulo p koji je prirodan broj manji od p. Općenito, ako je a ∈ N te , tada postoji multiplikativni inverz od a modulo p.

Jedna od najistaknutijih primjena nultiplikativnih inverza se pojavljuje prilikom evaluacije proizvoda (p − 1)! = 1 · 2 · 3 · · · (p − 1) modulo p, gdje je p prost broj. Sljedeća teorema se pripisuju engleskom matematićaru iz XVIII vijeka Johnu Wilsonu, iako je vjerojatno otkrivena od strane Ibn al-Hayhama u X vijeku, a prvi poznati dokaz je Lagrangeov i datira iz 1770.

Wilsonova teorema[uredi | uredi izvor]

Glavni članak: Wilsonova teorema

Ako je p prost broj tada je (p−1)! ≡ −1 (mod p).

Dokaz

Za svaki od brojeva 1, 2, . . . , p−1 postoji multiplikativni inverz modulo p. Dakle, svaki od faktora u (p−1)! = 1·2 · · · (p−1) daje 1 modulo p uproizvodu sa svojim multiplikativnim inverzom, osim faktora koji su sami sebi inverzni.

Odredimo takve faktore.

Neka je x ∈ {1, 2, . . . , p − 1} takav da vrijedi ≡ 1 (mod p). Tada p | . Kako je p prost broj i 1 ≤ x ≤ p − 1, slijedi da je ili x − 1 = 0 ili x+1 = p. Prema tome, jedini faktori u (p−1)! koji su sami sebi inverzni su 1 i p-1. Odatle dobijamo (p − 1)! ≡ 1 · (p - 1) (mod p) te (p − 1)! ≡ −1 (mod p).

Prethodni teorem ustvari daje interesantnu karakterizaciju prostih brojeva, jer vrijedi i obrat:

Propozicija

Ako prirodan broj n zadovoljava kongruenciju (n − 1)! ≡ −1(mod n), tada je n prost. Dokaz.

(n−1)! ≡ −1 (mod n) => (n−1)! ≡ −1 (mod m) za svaki m koji dijeli n. Ako je m < n, tada se m pojavljuje kao faktor od (n−1)! pa je (n−1)! ≡ 0 (mod m)

−1 ≡ 0 (mod m). Odavde je m = 1 te n nema pozitivnih djelitelja različitih od 1 i n pa je n prost.

Primjer

100! ≡ −1 (mod 101), tj. 101 | 100! + 1.

Korolar 1

Neka je p neparan prost broj. Kongruencija + 1 ≡ 0 (mod p) ima rješenja ako i samo ako je p ≡ 1 (mod 4).

Dokaz

Neka je p neparan prost broj te neka je Korištenjem kongruencije p − i ≡ −i (mod p) u proizvodu (p − 1)! = 1 · 2 · · · k · (k + 1) · · · (p − 2) · (p − 1) za i = 1, 2, . . . , k, dobijamo (p − 1)! ≡ (mod p).

Wilsonova teorema daje (p - 1)! ≡ −1 (mod p) te slijedi ≡ −1 (mod p) odakle dobijamo i

(mod p).

Kako je k paran za p ≡ 1 (mod 4) slijedi ≡ −1 (mod p) te je

rješenje kongruencije + 1 ≡ 0 (mod p).

Neka je sada , neparan. Ako je x rješenje kongruencije

, tada su x i p relativno prosti te je, prema Malom Fermatovom teoremu, . Prema tome, nije moguće jer je p neparan te u ovom slučaju polazna kongruencija nema rješenja.

Činjenica da kongruencija ima najviše dva rješenja (nekongruentna modulo p) ima važnu generalizaciju

Lagrangeova teorema[uredi | uredi izvor]

Glavni članak: Lagrangeova teorema

Ako je p prost broj i P(x) polinom stepana n sa cjelobrojnim koeficijentima, koji nisu svi djeljivi sa p, tada kongruencija ima najviše n rješenja modulo p

Izvori[uredi | uredi izvor]

  1. UVOD U TEORIJU BROJEVA / 2014
  2. Modular Arithmetic
  3. Modular arithmetic

Reference[uredi | uredi izvor]

  1. ^ Disquisitiones arithmeticae
  2. ^ Congruence