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 |
Nema sažetka uređivanja Oznake: mobilni uređaj m.wiki |
||
Redak 2:
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 ==
| |||