Lankide:Anazj/Proba orria

4.1.3 Zatiketa euklidearra

Hurrengo emaitzak aukera emango digu ${\textstyle 0}$ ez diren zenbaki osoen arteko zatiketarekin lan egiteko, zatiketa zehatza ez denean.

Adibidez, ${\textstyle 38}$ zati ${\textstyle 7}$ egiten badugu, zatidura ${\textstyle 5}$ eta hondarra ${\textstyle 3}$ aterako ditugu. Euklidesek (K. a. 300) frogatu zuen, ${\textstyle a}$ eta ${\textstyle b}$ bi zenbaki oso emanik, ${\textstyle b\neq 0}$ izanik, zatidura bakar bat, ${\textstyle q}$, eta hondar bakar bat, ${\textstyle r}$, ${\textstyle 0\leq r<b}$, lortzen ditugula beti.

Zatidura eta hondarra existitzen direla frogatzeko har dezagun kontuan nola egiten dugun ${\textstyle 38}$ zati ${\textstyle 7}$: $${\begin{array}{rrll}38&{\underline {\vline 7}}\\3&5\\\end{array}}$$ Zergatik ez da ${\textstyle 6}$ zatidura? ${\textstyle 6\cdot 7=42>38}$ delako. Hau da, ${\textstyle x}$ zenbaki bat bilatzen dugu, non ${\textstyle 38>x\cdot 7}$ den; bestela esanda, ${\textstyle 38-x\cdot 7>0}$ betetzen duena (beraz, ${\textstyle x<6}$ izango da). Zatidura ${\textstyle x}$ bada, hondarra ${\textstyle 38-x\cdot 7>0}$ izango da.

Zergatik ez da ${\textstyle 4}$ zatidura? ${\textstyle 38-4\cdot 7=10>38-5\cdot 7}$ delako. Izan ere, “hondar” positiboa sortzen duten zenbaki oso guztien artean, ahalik eta hondar txikiena uzten duena bilatzen dugu. Hau da, zatidura izango da ${\textstyle 38-x\cdot 7}$ ahalik eta txikiena, baina positiboa, egiten duen ${\textstyle x}$ zenbakia. Bestela esanda, $\{38-x\cdot 7>0\;:\;x\in \mathbb {Z} \}$ multzoaren minimoa bilatzen dugu.

Ikus dezagun beste adibide bat: $${\begin{array}{rrll}-38&{\underline {\vline 7}}&\\4&-6&\\\end{array}}$$ ${\textstyle -38-x\cdot 7>0}$ izan dadin ${\textstyle x<-5}$ bete behar da. $${\begin{array}{cc}x&-38-x\cdot 7\\\hline -4&-10\\-5&-3\\-6&4\\-7&11\\-8&18\\\vdots &\vdots \\\end{array}}$$

“Hondar” positibo txikiena ${\textstyle 4}$ da eta, beraz, zatidura ${\textstyle -6}$ da.

Euklidesek ideia hori teorema honetan zehaztu zuen:

Teorema. Euklidesen teorema

${\textstyle a,b\in \mathbb {Z} }$ emanik, ${\textstyle b>0}$ izanik, $$\exists \mid q\in \mathbb {Z} \;\;\exists \mid r\in \mathbb {Z} \;{\mbox{ non }}\;a=qb+r{\mbox{ den}},\;0\leq r<b{\mbox{ izanik}};$$

${\textstyle q}$ zatidura da, ${\textstyle r}$ hondarra, ${\textstyle a}$ zatikizuna eta ${\textstyle b}$ zatitzailea.

Froga.

${\textstyle q}$ eta ${\textstyle r}$ existitzen dira.

Bi kasu bereiziko ditugu: ${\textstyle b\mid a}$ eta ${\textstyle b\not \mid a}$.

1. ${\textstyle b\mid a}$.

   Orduan, ${\textstyle \exists k\in \mathbb {Z} }$, non ${\textstyle a=kb}$ den. Hortaz, nahikoa da ${\textstyle q:=k}$ eta ${\textstyle r:=0}$ hartzea, eta ${\textstyle a=qb+r}$ beteko da, ${\textstyle 0\leq r<b}$ izanik.

2. ${\textstyle b\not \mid a}$.

   Izan bedi ${\textstyle S:=\{a-xb\;:\;x\in \mathbb {Z} {\mbox{ eta }}a-xb>0\}}$ multzoa. Lehendabizi, ${\textstyle S\neq \emptyset }$ dela frogatuko dugu:

   1. ${\textstyle a>0}$ bada, ${\textstyle a=a-0\cdot b>0}$ beteko da, eta, hortaz, ${\textstyle a\in S}$ da.

   2. ${\textstyle a\leq 0}$ bada, izan bedi ${\textstyle t:=a-1}$. Beraz, ${\textstyle t\in \mathbb {Z} }$ eta $$a-tb=a-(a-1)b=a-ab+b=(1-b)a+b.$$ beteko dira. Orduan, $$b>0\Rightarrow b\geq 1\Rightarrow 1-b\leq 0\Rightarrow (1-b)a\geq 0\Rightarrow (1-b)a+b\geq b>0\Rightarrow$$ $$\Rightarrow a-tb>0\Rightarrow a-tb\in S.$$

   Hortaz, ${\textstyle S\neq \emptyset }$ da, eta ordena onaren printzipioaren arabera, ${\textstyle S}$ multzoak elementu minimoa du; izan bedi ${\textstyle r:=\min S}$. $$r\in S\Rightarrow r=a-qb>0,q\in \mathbb {Z} {\mbox{ izanik}}\Rightarrow a=qb+r,\,q,r\in \mathbb {Z} {\mbox{ eta }}r>0{\mbox{ izanik}}.$$

   ${\textstyle r<b}$ dela frogatzea baino ez da geratzen. Demagun ${\textstyle r\geq b}$ dela; kontraesan batera helduko garela ikusiko dugu:

   1. ${\textstyle r=b}$ bada, ${\textstyle a=qb+b=(q+1)b}$ da eta, hortaz, ${\textstyle b\mid a}$ beteko da, suposatu dugun ${\textstyle b\not \mid a}$ baldintzaren kontrakoa dena.

   2. ${\textstyle r>b}$ bada, ${\textstyle r=b+c}$ beteko da, ${\textstyle c:=r-b>0}$ izanik. Eta hortik $$a=qb+r=qb+b+c=(q+1)b+c\Rightarrow 0<c=a-(q+1)b\Rightarrow c\in S\Rightarrow$$ $$\Rightarrow c\geq r=\min S\Rightarrow r-b\geq r\Rightarrow b\leq 0$$ lortuko dugu; eta hori ezinezkoa da ${\textstyle b>0}$ delako.

${\textstyle q}$ eta ${\textstyle r}$ bakarrak dira.

Demagun $$\exists q_{1},q_{2},r_{1},r_{2}\in \mathbb {Z} ,\,{\mbox{ non }}\;a=q_{1}b+r_{1}=q_{2}b+r_{2}\,{\mbox{ den}},$$ ${\textstyle 0\leq r_{1}<b}$ eta ${\textstyle 0\leq r_{2}<b}$ izanik. Orduan, $$(q_{1}-q_{2})b=r_{2}-r_{1}$$ beteko da.

Lehendabizi, ${\textstyle r_{1}=r_{2}}$ dela frogatuko dugu.

${\textstyle r_{1}\neq r_{2}}$ dela suposatuko dugu eta kontraesan bat aurkituko dugu.

1. ${\textstyle r_{2}>r_{1}}$ bada, ${\textstyle 0<(q_{1}-q_{2})b\leq r_{2}<b}$ izango dugu. ${\textstyle b>0}$ denez, ${\textstyle 0<q_{1}-q_{2}<1}$ aterako dugu; eta hori ezinezkoa da ${\textstyle q_{1}-q_{2}\in \mathbb {Z} }$ delako.
2. ${\textstyle r_{2}<r_{1}}$ bada, arrazoibidea bera da, kontuan izanik ${\textstyle (q_{2}-q_{1})b=r_{1}-r_{2}}$ dela.

Hortaz, ${\textstyle r_{1}=r_{2}}$ dugu; hortik ${\textstyle q_{1}b=q_{2}b}$ aterako dugu. ${\textstyle b\neq 0}$ denez, ${\textstyle q_{1}=q_{2}}$ lortuko dugu. ${\textstyle \Box }$

Adibidea. $${\begin{array}{rrll}27&{\underline {\vline 6}}&\\3&4&\\\end{array}}\quad \quad {\begin{array}{rrll}-27&{\underline {\vline 6}}&\\3&-5&\\\end{array}}\quad \quad {\begin{array}{rrll}6&{\underline {\vline 27}}&\\6&0&\\\end{array}}\quad \quad {\begin{array}{rrll}-6&{\underline {\vline 27}}&\\21&-1&\\\end{array}}$$