Lagrangeov teorem (teorija brojeva)

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.

Korisna lemaUredi

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.

DokazUredi

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]

IzvoriUredi