WikiSysop: bnz

2022-05-01T13:13:01Z

bnz

←Starija inačica		Inačica od 13:13, 1. svibnja 2022.
Redak 1:		Redak 1:
	~~<!--'''Bézoutova lema'''-->~~'''Bézoutova lema''' ili '''Bézoutov identitet''' je jedan od najvažnijih rezultata u elementarnoj [[teorija brojeva\|teoriji brojeva]]. Lema tvrdi:		'''Bézoutova lema''' ili '''Bézoutov identitet''' je jedan od najvažnijih rezultata u elementarnoj [[teorija brojeva\|teoriji brojeva]]. Lema tvrdi:
	:Neka su <math> a, b </math> cijeli brojevi i neka je <math> d </math> [[najveća zajednička mjera]] brojeva <math> a, b. </math> Tada postoje <math> x, y \in \mathbb{Z} </math> takvi da je <math> ax + by = d. </math> Uz to, vrijedi <math> d = M(a, b).</math><ref>http://natjecanja.math.hr › N-...PDF		:Neka su <math> a, b </math> cijeli brojevi i neka je <math> d </math> [[najveća zajednička mjera]] brojeva <math> a, b. </math> Tada postoje <math> x, y \in \mathbb{Z} </math> takvi da je <math> ax + by = d. </math> Uz to, vrijedi <math> d = M(a, b).</math><ref>http://natjecanja.math.hr › N-...PDF
	Najveci zajednicki djeljitelj i najmanji zajednicki višekratnik</ref>		Najveci zajednicki djeljitelj i najmanji zajednicki višekratnik</ref>

WikiSysop: Bot: Automatski unos stranica

2021-12-09T18:12:22Z

Bot: Automatski unos stranica

Nova stranica

'''Bézoutova lema''' ili '''Bézoutov identitet''' je jedan od najvažnijih rezultata u elementarnoj [[teorija brojeva|teoriji brojeva]]. Lema tvrdi:
:Neka su <math> a, b </math> cijeli brojevi i neka je <math> d </math> [[najveća zajednička mjera]] brojeva <math> a, b. </math> Tada postoje <math> x, y \in \mathbb{Z} </math> takvi da je <math> ax + by = d. </math> Uz to, vrijedi <math> d = M(a, b).</math><ref>http://natjecanja.math.hr › N-...PDF
Najveci zajednicki djeljitelj i najmanji zajednicki višekratnik</ref>

Iako se lema zove po [[Francuska|francuskom]] [[matematika|matematičaru]] Étienne Bézoutu (1730. – 1783.), ovu je tvrdnju u svom radu ranije iskazao drugi francuski matematičar, Claude Gaspard Bachet de Méziriac (1581. – 1638.).

== Dokaz ==
Promotrimo skup <math> S = \{ax + by\ |\ x, y \in \mathbb{Z}, ax + by > 0\}. </math> Uočimo da su <math> a, b \in S. </math> Dakle, <math> S
</math> nije neprazan skup. Prema svojstvu ''[[dobro uređen skup|dobre uređenosti]]'' [[prirodan broj|prirodnih brojeva]] postoji najmanji element skupa <math> S. </math> Prema tome, neka je <math> d </math> najmanji član od <math> S.</math> To znači da ga možemo zapisati kao
<math> d = ak + bl,\ \ k, l \in \mathbb{Z}. </math> (1)

Dokaz ćemo da <math> d \mid a, d \mid b, </math> ali i da je <math> d = M(a, b). </math> Pretpostavimo bez smanjenja općenitosti (BSO) da <math> d \nmid a. </math> Prema ''teoremu o dijeljenju s ostatkom'' možemo pisati <math> a = dq + r,\ q \in \mathbb{Z},\ r = \{1, 2, ..., d - 1\}. </math> Dobivamo <math> r = a - dq. </math> Koristeći (1) dobivamo <math> r = a(1 - kq) + b(-ql), </math> što znači <math> r \in S </math>. No, <math> 0 < r < d, </math> što je kontradikcija jer je <math> d = \min S . </math> Dakle, <math> d \mid a </math> i analogno <math> d \mid b. </math>

Još valja dokazati da je <math> d = M(a, b). </math> Pretpostavimo da
<math> c \mid a, b </math> i BSO <math> c > 0. </math> Dakle
vrijedi <math> a = cs, b = ct, s, t \in \mathbb{N}. </math> Znamo da je <math> d = ka + lb </math> pa je preko gornjih jednakosti <math> d = c(ks + lt). </math> Vidimo da <math> c \mid d </math> pa je zaista <math> d = M(a, b) </math> čime je lema dokazana.

Dokaz je moguće zorno pokazati i primjenom [[Euklidov algoritam|Euklidovog algoritma]].

===Uvjet relativne prostosti ===

Iz dokaza se vidi da kada je <math> ax + by = 1 </math> slijedi <math> M(a, b) = 1 </math> i obrnuto, kada su <math> a, b </math> relativno [[Prosti broj|prosti]] mora biti
<math> ax + by = 1 </math> za neke
<math> x, y \in \mathbb{Z}. </math>

==Izvori==
{{izvori}}

== Vanjske poveznice ==
* [https://mathworld.wolfram.com/BezoutsIdentity.html Bézoutova lema na Mathworldu] {{eng oznaka}}
* [https://wims.univ-cotedazur.fr/wims/wims.cgi Kalkulator ''x'' i ''y'' prema Bézoutovoj lemi] {{eng oznaka}}

[[Kategorija:Teorija brojeva]]

Bézoutova lema - Povijest promjena

WikiSysop: bnz

WikiSysop: Bot: Automatski unos stranica