Modularna aritmetika

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 Disquisitiones arithmeticae. 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
Relacija biti kongruentan modulo n je relacija ekvivalencijeCongruence
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
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
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 
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 

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 

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 

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 

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
 UVOD U TEORIJU BROJEVA / 2014
 Modular Arithmetic
 Modular arithmetic
Reference


Kategorija:Teorija grupa
Kategorija:Konačni prstenovi