Modularna aritmetika

Clock group.svg

Teoriju kongruencija uveo je veliki njemački matematičar Carl Friedrich Gauss, koji je ovu tehniku, poznatu i pod nazivom modularna aritmetika, zasnovao u svom djelu Disquisitiones Arithmeticae (Istraživanja u aritmetici), 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 dvanaest sati.

MotivacijaUredi

Ovdje ćemo navesti i objasniti spomenuti primjer. Neka kazaljka na zidnom satu pokazuje 13. Ona će pokazivati 13 za višekratnike (pozitivne i negativne) broja 12. Ipak, razlikujemo 1h i 13h. Dakle, u jednom danu (od 0h do 24h) kazaljka očito obiđe svaki broj dvaput, tj. ovdje gledamo ostatke prirodnih brojeva pri dijeljenju a 24.

Možemo zamisliti i da namatamo uže u krug s   brojeva. Slikovito, oni brojevi koji se na takav način "preklope" kažemo da su kongruentni modulo  

DefinicijaUredi

Neka su   cijeli brojevi i   prirodan broj. Za brojeve   i   kažemo da su kongruentni po modulo   ako i samo vrijedi   tj. samo ako   daju isti ostatak pri dijeljenju s   Pišemo:   odnosno  

Kongruentnost u Uredi

Neka imamo prirodni broj   Tada očito postoji točno   različitih ostataka pri dijeljenju s  

U to se lako uvjerimo iz definicije ostatka. Svaki prirodni broj možemo napisati kao   Broj   nazivamo ostatkom pri dijeljenju broja   s   Za   nema smisla govoriti o "ostatku" kao takvom. Ipak, neka je   Tada očito za   tj.   postaje negativan. Vrijedi   Time smo dobili jednu svojevrsnu rezidualnu klasu. Dakle, tih klasa modulo   ima upravo  

Na pozitivan ostatak možemo gledati kao na višak broja   da bude djeljiv s   a na negativan ostatak kao na nedostajanje broja   da bude djeljiv s  

Operacije s kongurencijamaUredi

  • Očito je da ako vrijedi   onda je i  
  • Posljedica ovoga je da vrijedi   Obrnuto općenito ne vrijedi. Primjerice, za

  nije  

  • Naravno, vrijedi i  


Linearne kongruencijeUredi

Od svih kongruencija s polinomima, najjednostavnije su linearne kongruncije. To su kongruencije u obliku  

Postoji restrikcija rješenja karakteristična za linearne kongruencije koju ovdje navodimo.

Neka su dakle   prirodni, te   cijeli broj. Kongruencija   ima rješenja ako i samo ako   dijeli  . Ako je ovaj uvjet zadovoljen, onda gornja kongruencija ima točno   rješenja modulo  .

Za kongruencije s polinom stupnja   vrijedi poznati Lagrangeov teorem.

Mali Fermatov teoremUredi

Jedan od temeljnih teorema u teoriji brojeva koji je usko vezan uz modularnu aritmetiku jest tzv. Mali Fermatov teorem, nazvan prema jednom od najistaknutijih matematičara 17. stoljeća, francuskom matematičaru Pierreu de Fermatu.

Ovako glasi iskaz toga važnog teorema. Neka je   prost broj i   takav da   Tada je   tj.  .

Fermatov teorem je poseban slučaj Eulerovog teorema koji tvrdi da za svaka dva relativno prosta broja   vrijedi   gdje je   Eulerova funkcija, odnosno funkcija koja svakom prirodnom broju pridružuje broj relativno prostih brojeva manjih od njega.

IzvoriUredi