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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle P(x)} polinom stupnja $n$ s cjelobrojnim koeficijentima, koji nisu svi djeljivi s $p$, tada kongruencija Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle ax\equiv b{\pmod {n}}} ima jedinstveno rješenje modulo $n$, tj. ako je Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle S=\{a_{1},a_{2},...,a_{n}\}} potpuni sustav ostataka modulo $n$ tada postoji jedinstveni $a_{i}\in S$ takav da je Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle x\equiv a_{i}{\pmod {n}}} rješenje polazne kongruencije.

Dokaz. Kako su Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle a,n} relativno prosti, prema Bézoutovom identitetu slijedi da postoje cijeli brojevi Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle k,l} za koje vrijedi Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle ak+nl=1} , odakle je Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle akb+nkb=b} . Očito, Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle akb\equiv b{\pmod {n}}} pa je $x=kb$ rješenje polazne kongruencije.

Neka su sada Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle x_{1},x_{2}} dva rješenja polazne kongruencije. Dokažimo da su ova rješenja međusobno kongruentna modulo $n$. Naime, kako je Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle ax_{1}\equiv b{\pmod {n}}} i Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle ax_{2}\equiv b{\pmod {n}}} , dobivamo Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle ax_{1}\equiv ax_{2}{\pmod {n}}} .

Lagano slijedi Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle x_{1}\equiv x_{2}{\pmod {n}}} , što je i trebalo pokazati.

Dokaz

Dokaz provodimo indukcijom po stupnju polinoma Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\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$ te neka je $P(x)$ polinom stupnja $n$.

Najprije, ako kongruencija Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle P(x)\equiv 0{\pmod {p}}} nema rješenja, tada nemamo što dokazivati. Nasuprot, pretpostavimo kako je Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle P(x_{0})\equiv 0{\pmod {p}}} , za neki cijeli broj $x_{0}$ te neka je Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle P(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+...+a_{1}x+a_{0},} gdje su Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle a_{0},a_{1},...,a_{n}\in \mathbb {Z} } . Odatle je Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle P(x)\equiv P(x)-P(x_{0}){\pmod {p}}} , tj. Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\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\in \mathbb {N}$ vrijedi Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle (x-x_{0})Q(x)} , gdje je Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle Q(x)} polinom stupnja Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle n-1} s cjelobrojnim koeficijentima. Kako je Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} prost broj, kongruencija Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(x) \equiv 0 \pmod p} pokazuje kako je Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x - x_0 \equiv 0 \pmod p } ili Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Q(x) \equiv 0 \pmod p} .

Prema pretpostavci indukcije, kongruencija Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Q(x) \equiv 0 \pmod p } ima najviše Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n - 1} pa kongruencija Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle P(x)\equiv 0{\pmod {p}}} ima najviše $n$ rješenja (dakle $x_{0}$ i rješenja kongruencije Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle Q(x)\equiv 0{\pmod {p}}} ), što je i trebalo dokazati.