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 [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

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
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
Propozicija 1
  • Neka su   cijeli brojevi te   prirodan broj. Neka je

  i   tada vrijedi

  1.  
  2.  
  3.  

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

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

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

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

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

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
  1. UVOD U TEORIJU BROJEVA / 2014
  2. Modular Arithmetic
  3. Modular arithmetic

Reference

uredi
  1. ^ Disquisitiones arithmeticae
  2. ^ Congruence