Lagrangeov teorem (teorija brojeva)

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

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

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

Neka su sada [math]\displaystyle{ x_1, x_2 }[/math] dva rješenja polazne kongruencije. Dokažimo da su ova rješenja međusobno kongruentna modulo [math]\displaystyle{ n }[/math]. Naime, kako je [math]\displaystyle{ ax_1 \equiv b \pmod n }[/math] i [math]\displaystyle{ ax_2 \equiv b \pmod n }[/math], dobivamo [math]\displaystyle{ ax_1 \equiv ax_2 \pmod n }[/math].

Lagano slijedi [math]\displaystyle{ x_1 \equiv x_2 \pmod n }[/math], što je i trebalo pokazati.

Dokaz

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

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

Najprije, ako kongruencija [math]\displaystyle{ P(x) \equiv 0 \pmod p }[/math] nema rješenja, tada nemamo što dokazivati. Nasuprot, pretpostavimo kako je [math]\displaystyle{ P(x_0) \equiv 0 \pmod p }[/math], za neki cijeli broj [math]\displaystyle{ x_0 }[/math] te neka je [math]\displaystyle{ P(x) = a_nx^n + a_{n-1}x^{n - 1} + ... + a_1x + a_0, }[/math] gdje su [math]\displaystyle{ a_0, a_1, ... , a_n \in \mathbb{Z} }[/math]. Odatle je [math]\displaystyle{ P(x) \equiv P(x) - P(x_0) \pmod p }[/math], tj. [math]\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. }[/math]

Kako za [math]\displaystyle{ k \in \mathbb{N} }[/math] vrijedi [math]\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}), }[/math] desnu stranu prethodne kongruencije možemo zapisati u obliku [math]\displaystyle{ (x - x_0)Q(x) }[/math], gdje je [math]\displaystyle{ Q(x) }[/math] polinom stupnja [math]\displaystyle{ n - 1 }[/math] s cjelobrojnim koeficijentima. Kako je [math]\displaystyle{ p }[/math] prost broj, kongruencija [math]\displaystyle{ P(x) \equiv 0 \pmod p }[/math] pokazuje kako je [math]\displaystyle{ x - x_0 \equiv 0 \pmod p }[/math] ili [math]\displaystyle{ Q(x) \equiv 0 \pmod p }[/math].

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