Lagrangeov teorem (teorija brojeva)

Izvor: Wikipedija
Prijeđi na navigaciju Prijeđi na pretraživanje

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[uredi | uredi kôd]

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[uredi | uredi kôd]

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[uredi | uredi kôd]