Modularna aritmetika

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

Motivacija

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 [math]\displaystyle{ m }[/math] brojeva. Slikovito, oni brojevi koji se na takav način "preklope" kažemo da su kongruentni modulo [math]\displaystyle{ m. }[/math]

Definicija

Neka su [math]\displaystyle{ a, b }[/math] cijeli brojevi i [math]\displaystyle{ m }[/math] prirodan broj. Za brojeve [math]\displaystyle{ a }[/math] i [math]\displaystyle{ b }[/math] kažemo da su kongruentni po modulo [math]\displaystyle{ m }[/math] ako i samo vrijedi [math]\displaystyle{ m | a - b, }[/math] tj. samo ako [math]\displaystyle{ a, b }[/math] daju isti ostatak pri dijeljenju s [math]\displaystyle{ m. }[/math] Pišemo: [math]\displaystyle{ a - b \equiv 0 \pmod m, }[/math] odnosno [math]\displaystyle{ a \equiv b \pmod m. }[/math]

Kongruentnost u [math]\displaystyle{ \mathbb{Z} }[/math]

Neka imamo prirodni broj [math]\displaystyle{ n. }[/math] Tada očito postoji točno [math]\displaystyle{ n }[/math] različitih ostataka pri dijeljenju s [math]\displaystyle{ n. }[/math]

U to se lako uvjerimo iz definicije ostatka. Svaki prirodni broj možemo napisati kao [math]\displaystyle{ n = km + r, r = \{0, 1, 2, ...\}, n, k, m \in \mathbb{N}. }[/math] Broj [math]\displaystyle{ r }[/math] nazivamo ostatkom pri dijeljenju broja [math]\displaystyle{ n }[/math] s [math]\displaystyle{ m. }[/math] Za [math]\displaystyle{ r \lt 0 }[/math] nema smisla govoriti o "ostatku" kao takvom. Ipak, neka je [math]\displaystyle{ r = \{0, 1, 2, ..., m\}. }[/math] Tada očito za [math]\displaystyle{ n = (k + i)m + r',r' := r - im, }[/math] tj. [math]\displaystyle{ r }[/math] postaje negativan. Vrijedi [math]\displaystyle{ ... \equiv r - 2m \equiv r - m \equiv r \equiv r + m, \equiv r + 2m \equiv ... }[/math] Time smo dobili jednu svojevrsnu rezidualnu klasu. Dakle, tih klasa modulo [math]\displaystyle{ m }[/math] ima upravo [math]\displaystyle{ m. }[/math]

Na pozitivan ostatak možemo gledati kao na višak broja [math]\displaystyle{ n }[/math] da bude djeljiv s [math]\displaystyle{ m, }[/math] a na negativan ostatak kao na nedostajanje broja [math]\displaystyle{ n }[/math] da bude djeljiv s [math]\displaystyle{ m. }[/math]

Operacije s kongurencijama

• Očito je da ako vrijedi [math]\displaystyle{ a \equiv b \pmod m, }[/math] onda je i [math]\displaystyle{ a \pm c \equiv b \pm c \pmod m, \forall c \in \mathbb{N}. }[/math]

• Posljedica ovoga je da vrijedi [math]\displaystyle{ ac \equiv bc \pmod m. }[/math] Obrnuto općenito ne vrijedi.

Primjerice, za [math]\displaystyle{ 6 \equiv 3 \pmod 3 }[/math] nije [math]\displaystyle{ 2 \equiv 1 \pmod 3. }[/math]

• Naravno, vrijedi i [math]\displaystyle{ a \equiv b \pmod m \iff a^n \equiv b^n \pmod m. }[/math]

Linearne kongruencije

Od svih kongruencija s polinomima, najjednostavnije su linearne kongruncije. To su kongruencije u obliku [math]\displaystyle{ ax \equiv b \pmod n. }[/math]

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

Neka su dakle [math]\displaystyle{ a, m }[/math] prirodni, te [math]\displaystyle{ b }[/math] cijeli broj. Kongruencija [math]\displaystyle{ ax \equiv b \pmod m }[/math] ima rješenja ako i samo ako [math]\displaystyle{ d = M(a, m) }[/math] dijeli [math]\displaystyle{ b }[/math]. Ako je ovaj uvjet zadovoljen, onda gornja kongruencija ima točno [math]\displaystyle{ d }[/math] rješenja modulo [math]\displaystyle{ m }[/math].

Za kongruencije s polinom stupnja [math]\displaystyle{ n }[/math] vrijedi poznati Lagrangeov teorem.

Mali Fermatov teorem

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 [math]\displaystyle{ p }[/math] prost broj i [math]\displaystyle{ a \in \mathbb{N} }[/math] takav da [math]\displaystyle{ p \nmid a. }[/math] Tada je [math]\displaystyle{ a^{p - 1} \equiv 1 \pmod p, }[/math] tj. [math]\displaystyle{ a^p \equiv a \pmod p }[/math].

Fermatov teorem je poseban slučaj Eulerovog teorema koji tvrdi da za svaka dva relativno prosta broja [math]\displaystyle{ a, n \in \mathbb{N} }[/math] vrijedi [math]\displaystyle{ a^{\varphi(n)} \equiv 1 \pmod n, }[/math] gdje je [math]\displaystyle{ \varphi(n) }[/math] Eulerova funkcija, odnosno funkcija koja svakom prirodnom broju pridružuje broj relativno prostih brojeva manjih od njega.