Lagrangeov teorem (teorija brojeva): razlika između inačica
Izbrisani sadržaj Dodani sadržaj
Nema sažetka uređivanja |
Oznake: mobilni uređaj m.wiki |
||
Redak 2:
== Dokaz ==
Dokaz provodimo indukcijom po stupnju polinoma <math>P(x)</math>. Ako je stupanj promatranog polinoma jednak 1, tvrdnja teorema
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>
Odatle je <math>P(x) \equiv P(x) - P(x_0) \pmod p</math>, tj. </math>P(x)
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> rješenja pa kongruencija <math>P(x) \equiv 0 \pmod p</math> ima najviše <math>n</math>
rješenja (<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>
| |||