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(\mathrm{mod}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(\mathrm{mod}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(\mathrm{mod}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(\mathrm{mod}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 $a{x}_1\equiv b(\mathrm{mod}n)$ i $a{x}_2\equiv b(\mathrm{mod}n)$, dobivamo $a{x}_1\equiv a{x}_2(\mathrm{mod}n)$.

Lagano slijedi $x_1\equiv x_2(\mathrm{mod}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(\mathrm{mod}p)$ nema rješenja, tada nemamo što dokazivati. Nasuprot, pretpostavimo kako je $P(x_0)\equiv 0(\mathrm{mod}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)(\mathrm{mod}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)(\mathrm{mod}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(\mathrm{mod}p)$ pokazuje kako je $x-x_0\equiv 0(\mathrm{mod}p)$ ili $Q(x)\equiv 0(\mathrm{mod}p)$.

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