Modularna aritmetika

Izvor: Wikipedija
Prijeđi na navigaciju Prijeđi na pretraživanje
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, 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.

Motivacija[uredi VE | uredi]

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

Definicija[uredi VE | uredi]

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 VE | 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 kongurencijama[uredi VE | uredi]

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

Mali Fermatov teorem[uredi VE | uredi]

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

Izvori[uredi VE | uredi]