Vidi kôd stranice Lagrangeov teorem (teorija brojeva)

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

Teorem je nazvan prema [[Italija|talijanskom]] [[Matematika|matematičaru]] i astronomu [[Joseph-Louis Lagrange|Lagrangeu]].

== Korisna lema ==
Dokazat ćemo lemu koja će se pokazati korisnom pri dokazivanju Lagrangeovog teorema.

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

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

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

Lagano slijedi <math> x_1 \equiv x_2 \pmod n </math>, što je i trebalo pokazati.

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

Najprije, ako kongruencija <math>P(x) \equiv 0 \pmod p</math> nema rješenja, tada nemamo što
dokazivati. Nasuprot, pretpostavimo kako je <math>P(x_0) \equiv 0 \pmod p</math>, za neki cijeli broj <math>x_0</math>
te neka je <math>P(x) = a_nx^n + a_{n-1}x^{n - 1} + ... + a_1x + a_0,</math> gdje su <math>a_0, a_1, ... , a_n \in \mathbb{Z}</math>.
Odatle je <math>P(x) \equiv P(x) - P(x_0) \pmod p</math>, tj. <math>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>k \in \mathbb{N} </math> vrijedi <math>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>(x - x_0)Q(x)</math>, gdje je <math>Q(x)</math> polinom stupnja <math>n - 1</math> s cjelobrojnim koeficijentima. Kako je <math>p</math> prost broj, kongruencija <math>P(x) \equiv 0 \pmod p</math> pokazuje kako je <math>x - x_0 \equiv 0
\pmod p </math> ili <math>Q(x) \equiv 0 \pmod p</math>. 

Prema pretpostavci indukcije, kongruencija <math> Q(x) \equiv 0
\pmod p </math> ima najviše <math>n - 1</math> pa kongruencija <math>P(x) \equiv 0 \pmod p</math> ima najviše <math>n</math>
rješenja (dakle <math> x_0 </math> i rješenja kongruencije <math>Q(x) \equiv 0 \pmod p</math>), što je i trebalo dokazati.<ref>https://www.mathos.unios.hr/~imatic/uvod%20u%20teoriju%20brojeva.pdf</ref>

==Izvori==
{{izvori}}

[[Kategorija:Matematika]]