Lagrangeov teorem je jedan od najvažnijih teorema u teoriji brojeva, a kaže da ako je
prost broj i
polinom stupnja
s cjelobrojnim koeficijentima, koji nisu svi djeljivi s
, tada kongruencija
ima najviše
rješenja modulo
.
Teorem je nazvan prema talijanskom matematičaru i astronomu Lagrangeu.
Dokazat ćemo lemu koja će se pokazati korisnom pri dokazivanju Lagrangeovog teorema.
Neka su dakle
i
prirodni brojevi. Ako je
, tada
kongruencija
ima jedinstveno rješenje modulo
, tj. ako je
potpuni sustav ostataka modulo
tada postoji jedinstveni
takav
da je
rješenje polazne kongruencije.
Dokaz. Kako su
relativno prosti, prema Bézoutovom identitetu slijedi da postoje cijeli brojevi
za koje vrijedi
, odakle je
. Očito,
pa je
rješenje polazne kongruencije.
Neka su sada
dva rješenja polazne kongruencije. Dokažimo da su ova rješenja
međusobno kongruentna modulo
.
Naime, kako je
i
, dobivamo
.
Lagano slijedi
, što je i trebalo pokazati.
Dokaz provodimo indukcijom po stupnju polinoma
. Ako je stupanj promatranog polinoma jednak 1, tvrdnja teorema vrijedi zbog gore dokazane leme.
Pretpostavimo kako tvrdnja vrijedi za polinome stupnja manjeg od
te neka je
polinom stupnja
.
Najprije, ako kongruencija
nema rješenja, tada nemamo što
dokazivati. Nasuprot, pretpostavimo kako je
, za neki cijeli broj
te neka je
gdje su
.
Odatle je
, tj.
Kako za
vrijedi
desnu stranu prethodne kongruencije možemo zapisati u obliku
, gdje je
polinom stupnja
s cjelobrojnim koeficijentima. Kako je
prost broj, kongruencija
pokazuje kako je
ili
.
Prema pretpostavci indukcije, kongruencija
ima najviše
pa kongruencija
ima najviše
rješenja (dakle
i rješenja kongruencije
), što je i trebalo dokazati.[1]
- ↑ [1] Ivan Matić, Uvod u teoriju brojeva, Osijek, 2014., str. 27