Lagrangeov teorem (teorija brojeva)

Lagrangeov teorem je jedan od najvažnijih teorema u teoriji brojeva, a kaže da ako je $p$ prost broj i $P(x)$ polinom stupnja $n$ s cjelobrojnim koeficijentima, koji nisu svi djeljivi s $p$, tada kongruencija $P(x)\equiv 0{\pmod {p}}$ ima najviše $n$ rješenja modulo $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$ i $n$ prirodni brojevi. Ako je $M(a,n)=1$, tada kongruencija $ax\equiv b{\pmod {n}}$ ima jedinstveno rješenje modulo $n$, tj. ako je $S=\{a_{1},a_{2},...,a_{n}\}$ potpuni sustav ostataka modulo $n$ tada postoji jedinstveni $a_{i}\in S$ takav da je $x\equiv a_{i}{\pmod {n}}$ rješenje polazne kongruencije.

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

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

Lagano slijedi $x_{1}\equiv x_{2}{\pmod {n}}$, što je i trebalo pokazati.

Dokaz

Dokaz provodimo indukcijom po stupnju polinoma $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$ te neka je $P(x)$ polinom stupnja $n$.

Najprije, ako kongruencija $P(x)\equiv 0{\pmod {p}}$ nema rješenja, tada nemamo što dokazivati. Nasuprot, pretpostavimo kako je $P(x_{0})\equiv 0{\pmod {p}}$, za neki cijeli broj $x_{0}$ te neka je $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}\in \mathbb {Z}$. Odatle je $P(x)\equiv P(x)-P(x_{0}){\pmod {p}}$, tj. $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\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}),$ desnu stranu prethodne kongruencije možemo zapisati u obliku $(x-x_{0})Q(x)$, gdje je $Q(x)$ polinom stupnja $n-1$ s cjelobrojnim koeficijentima. Kako je $p$ prost broj, kongruencija $P(x)\equiv 0{\pmod {p}}$ pokazuje kako je $x-x_{0}\equiv 0{\pmod {p}}$ ili $Q(x)\equiv 0{\pmod {p}}$.

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