Toggle menu
310,1 tis.
50
18
525,6 tis.
Hrvatska internetska enciklopedija
Toggle preferences menu
Toggle personal menu
Niste prijavljeni
Your IP address will be publicly visible if you make any edits.

Lagrangeov teorem (teorija brojeva)

Izvor: Hrvatska internetska enciklopedija
Inačica 392713 od 12. prosinac 2021. u 02:35 koju je unio WikiSysop (razgovor | doprinosi) (Bot: Automatski unos stranica)
(razl) ←Starija inačica | vidi trenutačnu inačicu (razl) | Novija inačica→ (razl)

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 lema

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

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]

Izvori