Lagrangeov teorem (teorija brojeva) – Hrvatska internetska enciklopedija

# Lagrangeov teorem (teorija brojeva)

Izvor: Hrvatska internetska enciklopedija
More actions

Lagrangeov teorem je jedan od najvažnijih teorema u teoriji brojeva, a kaže da ako je p {\displaystyle p} prost broj i P ( x ) {\displaystyle P(x)} polinom stupnja n {\displaystyle n} s cjelobrojnim koeficijentima, koji nisu svi djeljivi s p {\displaystyle p} , tada kongruencija P ( x ) ≡ 0 ( mod p ) {\displaystyle P(x)\equiv 0{\pmod {p}}} ima najviše n {\displaystyle n} rješenja modulo p {\displaystyle p} .

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 a {\displaystyle a} i n {\displaystyle n} prirodni brojevi. Ako je M ( a , n ) = 1 {\displaystyle M(a,n)=1} , tada kongruencija a x ≡ b ( mod n ) {\displaystyle ax\equiv b{\pmod {n}}} ima jedinstveno rješenje modulo n {\displaystyle n} , tj. ako je S = { a 1 , a 2 , . . . , a n } {\displaystyle S=\{a_{1},a_{2},...,a_{n}\}} potpuni sustav ostataka modulo n {\displaystyle n} tada postoji jedinstveni a i ∈ S {\displaystyle a_{i}\in S} takav da je x ≡ a i ( mod n ) {\displaystyle x\equiv a_{i}{\pmod {n}}} rješenje polazne kongruencije.

Dokaz. Kako su a , n {\displaystyle a,n} relativno prosti, prema Bézoutovom identitetu slijedi da postoje cijeli brojevi k , l {\displaystyle k,l} za koje vrijedi a k + n l = 1 {\displaystyle ak+nl=1} , odakle je a k b + n k b = b {\displaystyle akb+nkb=b} . Očito, a k b ≡ b ( mod n ) {\displaystyle akb\equiv b{\pmod {n}}} pa je x = k b {\displaystyle x=kb} rješenje polazne kongruencije.

Neka su sada x 1 , x 2 {\displaystyle x_{1},x_{2}} dva rješenja polazne kongruencije. Dokažimo da su ova rješenja međusobno kongruentna modulo n {\displaystyle n} . Naime, kako je a x 1 ≡ b ( mod n ) {\displaystyle ax_{1}\equiv b{\pmod {n}}} i a x 2 ≡ b ( mod n ) {\displaystyle ax_{2}\equiv b{\pmod {n}}} , dobivamo a x 1 ≡ a x 2 ( mod n ) {\displaystyle ax_{1}\equiv ax_{2}{\pmod {n}}} .

Lagano slijedi x 1 ≡ x 2 ( mod n ) {\displaystyle x_{1}\equiv x_{2}{\pmod {n}}} , što je i trebalo pokazati.

## Dokaz

Dokaz provodimo indukcijom po stupnju polinoma P ( x ) {\displaystyle P(x)} . Ako je stupanj promatranog polinoma jednak 1, tvrdnja teorema vrijedi zbog gore dokazane leme.

Pretpostavimo kako tvrdnja vrijedi za polinome stupnja manjeg od n {\displaystyle n} te neka je P ( x ) {\displaystyle P(x)} polinom stupnja n {\displaystyle n} .

Najprije, ako kongruencija P ( x ) ≡ 0 ( mod p ) {\displaystyle P(x)\equiv 0{\pmod {p}}} nema rješenja, tada nemamo što dokazivati. Nasuprot, pretpostavimo kako je P ( x 0 ) ≡ 0 ( mod p ) {\displaystyle P(x_{0})\equiv 0{\pmod {p}}} , za neki cijeli broj x 0 {\displaystyle x_{0}} te neka je P ( x ) = a n x n + a n − 1 x n − 1 + . . . + a 1 x + a 0 , {\displaystyle P(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+...+a_{1}x+a_{0},} gdje su a 0 , a 1 , . . . , a n ∈ Z {\displaystyle a_{0},a_{1},...,a_{n}\in \mathbb {Z} } . Odatle je P ( x ) ≡ P ( x ) − P ( x 0 ) ( mod p ) {\displaystyle P(x)\equiv P(x)-P(x_{0}){\pmod {p}}} , tj. P ( x ) ≡ a n ( x n − x 0 n ) + a n − 1 ( x n − 1 − x 0 n − 1 ) + . . . + a 1 ( x − x 0 ) ( mod p ) . {\displaystyle P(x)\equiv a_{n}(x^{n}-{x_{0}}^{n})+a_{n-1}(x^{n-1}-{x_{0}}^{n-1})+...+a_{1}(x-x_{0}){\pmod {p}}.}

Kako za k ∈ N {\displaystyle k\in \mathbb {N} } vrijedi x k − x 0 k = ( x − x 0 ) ( x k − 1 + x k − 2 x 0 + . . . + x x 0 k − 2 + x 0 k − 1 ) , {\displaystyle x^{k}-{x_{0}}^{k}=(x-x_{0})(x^{k-1}+x^{k-2}x_{0}+...+x{x_{0}}^{k-2}+{x_{0}}^{k-1}),} desnu stranu prethodne kongruencije možemo zapisati u obliku ( x − x 0 ) Q ( x ) {\displaystyle (x-x_{0})Q(x)} , gdje je Q ( x ) {\displaystyle Q(x)} polinom stupnja n − 1 {\displaystyle n-1} s cjelobrojnim koeficijentima. Kako je p {\displaystyle p} prost broj, kongruencija P ( x ) ≡ 0 ( mod p ) {\displaystyle P(x)\equiv 0{\pmod {p}}} pokazuje kako je x − x 0 ≡ 0 ( mod p ) {\displaystyle x-x_{0}\equiv 0{\pmod {p}}} ili Q ( x ) ≡ 0 ( mod p ) {\displaystyle Q(x)\equiv 0{\pmod {p}}} .

Prema pretpostavci indukcije, kongruencija Q ( x ) ≡ 0 ( mod p ) {\displaystyle Q(x)\equiv 0{\pmod {p}}} ima najviše n − 1 {\displaystyle n-1} pa kongruencija P ( x ) ≡ 0 ( mod p ) {\displaystyle P(x)\equiv 0{\pmod {p}}} ima najviše n {\displaystyle n} rješenja (dakle x 0 {\displaystyle x_{0}} i rješenja kongruencije Q ( x ) ≡ 0 ( mod p ) {\displaystyle Q(x)\equiv 0{\pmod {p}}} ), što je i trebalo dokazati.[1]

## Izvori

1. ↑ https://www.mathos.unios.hr/~imatic/uvod%20u%20teoriju%20brojeva.pdf

Dobavljeno iz "https://enciklopedija.cc/index.php?title=Lagrangeov_teorem_(teorija_brojeva)&oldid=441242"