MD-liburua/Zenbaki-teoria

4. Gaia: Zenbaki-teoria

4.1 Zenbaki osoak

4.1.1 Eragiketak zenbaki osoen artean. Ordena onaren printzipioa

Atal honetan, [multzo] atalean aipatu genuen zenbaki osoen ${\textstyle \mathbb {Z} }$ multzoa aztertuko dugu, baita bertan defini daitezkeen eragiketak eta ${\textstyle \leq }$, “txikiago edo berdin” erlazioa ere.

• Gogora dezagun ${\textstyle \mathbb {Z} }$ multzo azpimultzo disjuntutan deskonposa daitekeela, honela: $$\mathbb {Z} =\mathbb {Z} ^{+}\,{\dot {\cup }}\,\mathbb {Z} ^{-}\,{\dot {\cup }}\,\{0\}.$$

• ${\textstyle \mathbb {Z} }$ multzoa itxia da ${\textstyle (+)}$ batuketarako, ${\textstyle (\cdot )}$ biderketarako eta ${\textstyle (-)}$ kenketarako: $$x,y\in \mathbb {Z} \,\Longrightarrow \,x+y,\,x\cdot y,\,x-y\,\in \mathbb {Z} ;$$ baina ez da itxia ${\textstyle (/)}$ zatiketarako; adibidez: ${\textstyle 2,3\in \mathbb {Z} }$, baina ${\textstyle {\dfrac {2}{3}}\not \in \mathbb {Z} }$.

  Hala ere, zatiketa murriztua, zatiketa euklidestarra, definituko dugu ${\textstyle \mathbb {Z} }$ multzoan, eta ${\textstyle \mathbb {Z} ^{+}}$ multzoaren elementu berezi batzuetan, zenbaki lehenak, jarriko dugu arreta.

• Bestalde, ${\textstyle \leq }$ ordena-erlazioa da ${\textstyle \mathbb {Z} }$ multzoan, Erlazioen Gaian definituko ditugun propietateak betetzen dituelako:

  • Bihurtze-propietatea: ${\textstyle (\forall x\in \mathbb {Z} )\quad x\leq x}$.

  • Antisimetri propietatea: ${\textstyle (\forall x,y\in \mathbb {Z} )\quad x\leq y\;\wedge \;x\leq y\;\Rightarrow \;x=y}$.

  • Iragate-propietatea: ${\textstyle (\forall x,y,z\in \mathbb {Z} )\quad x\leq y\;\wedge \;y\leq z\;\Rightarrow \;x\leq z}$.

  Are gehiago, ordena osoko erlazioa da (Erlazioen Gaia); hau da, ${\textstyle \leq }$ erlazioak osoki ordenatzen du ${\textstyle \mathbb {Z} }$ multzoa; horrek esan nahi du ${\textstyle x}$ eta ${\textstyle y}$ zeinahi zenbaki osoak emanik, beti konparatu ahal izango ditugu: $$(\forall x,y\in \mathbb {Z} )\quad x\leq y\,\vee \,y\leq x.$$

  ${\textstyle \leq }$ erlazioaren propietate horiek ${\textstyle \mathbb {Q} }$ eta ${\textstyle \mathbb {R} }$ multzoetan ere betetzen dira. ${\textstyle \mathbb {N} }$ edo ${\textstyle \mathbb {Z} ^{+}}$ multzoa ${\textstyle \mathbb {Q} ^{+}}$ eta ${\textstyle \mathbb {R} ^{+}}$ multzoetatik bereizten duena da lehena multzo ongi ordenatua dela, bestela esanda, Ordena Onaren Printzipioa betetzen dela: ${\textstyle \mathbb {N} }$ edo ${\textstyle \mathbb {Z} ^{+}}$ multzoaren edozein azpimultzo ez-hutsek elementu minimo bat dauka.

  Printzipio hori ez da ${\textstyle \mathbb {Q} ^{+}}$ multzoan betetzen, ezta ${\textstyle \mathbb {R} ^{+}}$ multzoan ere. Esate baterako, $$(0,8)=\{x\in \mathbb {R} \;:\;0<x<8\}$$ tarte irekia ${\textstyle \mathbb {R} ^{+}}$ multzoaren azpimultzo ez-hutsa da, baina ez du elementu minimorik. Hori frogatzeko, demagun tarteak ${\textstyle m}$ elementu minimoa duela. Orduan, ${\textstyle 0<m<8}$; hortik, ${\textstyle 0<{\dfrac {m}{2}}<4<8}$ dugu, ${\textstyle {\dfrac {m}{2}}\in (0,8)}$ izanik. Baina ${\textstyle {\dfrac {m}{2}}<m}$ betetzen da; beraz, kontraesan batera heldu gara, ${\textstyle m}$ baita ${\textstyle (0,8)}$ tartearen minimoa.

4.1.2 Zatigarritasuna. Zenbaki lehenak

${\textstyle \mathbb {Z} ^{*}}$ multzoa ${\textstyle /}$ zatiketarako itxia ez bada ere, badira kasu batzuk non zenbaki oso batek beste bat zehazki zatitzen duen. Esaterako, ${\textstyle 4}$-ak ${\textstyle 12}$-a zehazki zatitzen du (${\textstyle 12=3\cdot 4}$). Hau da, ${\textstyle 12}$ zati 4 egitean, zatiduratzat ${\textstyle 3}$ zenbaki osoa eta hondartzat ${\textstyle 0}$ lortuko ditugu.

Definizioa. ${\textstyle a,b\in \mathbb {Z} }$ zenbakiak emanik, ${\textstyle a\neq 0}$ izanik, esango dugu ${\textstyle a}$ zenbakiak ${\textstyle b}$ zenbakia zatitzen duela, eta ${\textstyle a\mid b}$ adieraziko dugu, baldin $$\exists k\in \mathbb {Z} \;{\mbox{ non }}\;b=ka{\mbox{ den }}$$ Hori gertatzen denean, esango dugu ${\textstyle a}$ zenbakia ${\textstyle b}$ zenbakiaren zatitzaile bat dela, edo ${\textstyle b}$ zenbakia ${\textstyle a}$ zenbakiaren multiplo bat dela.
Hitzarmena. ${\textstyle a\mid b}$ idazten dugunean, ${\textstyle a\neq 0}$ dela suposatuko dugu.

• ${\textstyle a,b\in \mathbb {Z} ^{+}}$ bada, berehala egiazta daiteke emaitza hau: $$a\mid b\;\Rightarrow \;a\leq b$$

Ondoko teoreman zatigarritasunaren propietate batzuk frogatuko ditugu.

Teorema. [propietateak] ${\textstyle a,b,c\in \mathbb {Z} }$ emanik,

1. ${\textstyle 1\mid a}$; ${\textstyle a\mid a}$; ${\textstyle a\mid 0}$. (${\textstyle a\neq 0}$)
2. ${\textstyle (a\mid b)\;\wedge \;(b\mid a)\;\Rightarrow \;a=b\;\vee \;a=-b}$. (${\textstyle a\neq 0,b\neq 0}$)
3. ${\textstyle (a\mid b)\;\wedge \;(b\mid c)\;\Rightarrow \;a\mid c}$. (${\textstyle a\neq 0,b\neq 0}$)
4. ${\textstyle a\mid b\;\Rightarrow \;(\forall x\in \mathbb {Z} )\;\;a\mid xb}$. (${\textstyle a\neq 0}$)
5. ${\textstyle (a\mid b)\wedge (a\mid c)\;\Rightarrow \;(\forall x,y\in \mathbb {Z} )\;\;a\mid xb+yc}$. (${\textstyle a\neq 0}$)

Froga.

1. ${\textstyle a=1a.}$ Hortaz,   ${\textstyle 1\mid a}$ eta ${\textstyle a\mid a}$. Bestalde, ${\textstyle 0=0a.}$ Hortaz,   ${\textstyle a\mid 0}$.
2. Hasteko daukagu, ${\textstyle (a\mid b)\;\wedge \;(b\mid a)}$, hau da, $$\left.{\begin{array}{c}a\mid b\\\wedge \\b\mid a\end{array}}\right\}\;\Rightarrow \;\left.{\begin{array}{c}b=k_{1}a,\;k_{1}\in \mathbb {Z} {\mbox{ izanik}}\\\wedge \\a=k_{2}b,\;k_{2}\in \mathbb {Z} {\mbox{ izanik}}\end{array}}\right\}\;\Rightarrow \;b=k_{1}(k_{2}b)=(k_{1}k_{2})b,$$ $$k_{1},k_{2}\in \mathbb {Z} {\mbox{ izanik}}\Rightarrow \;k_{1}k_{2}=1,\;k_{1},k_{2}\in \mathbb {Z} {\mbox{ izanik}}\;\Rightarrow \;\left.{\begin{array}{c}k_{1}=k_{2}=1\\\vee \\k_{1}=k_{2}=-1\end{array}}\right\}\;\Rightarrow \;\left.{\begin{array}{c}a=b\\\vee \\a=-b.\end{array}}\right.$$
3. Kasu honetan ${\textstyle (a\mid b)\;\wedge \;(b\mid c)}$ daukagu, $$\left.{\begin{array}{c}a\mid b\\\wedge \\b\mid c\end{array}}\right\}\;\Rightarrow \;\left.{\begin{array}{c}b=k_{1}a,\;k_{1}\in \mathbb {Z} {\mbox{ izanik}}\\\wedge \\c=k_{2}b,\;k_{2}\in \mathbb {Z} {\mbox{ izanik}}\end{array}}\right\}\;\Rightarrow \;c=k_{2}(k_{1}a)=(k_{2}k_{1})a,$$ ${\textstyle k_{2}k_{1}\in \mathbb {Z} {\mbox{ izanik }}\;\Rightarrow a\mid c}$.
4. Edozein ${\textstyle x\in \mathbb {Z} }$ emanik, $$a\mid b\;\Rightarrow \;b=ka,\;k\in \mathbb {Z} {\mbox{ izanik}}\;\Rightarrow \;xb=x(ka)=(xk)a,\;xk\in \mathbb {Z} {\mbox{ izanik}}\;\Rightarrow \;a\mid xb.$$
5. Edozein ${\textstyle x,y\in \mathbb {Z} }$ emanik, $$\left.{\begin{array}{c}a\mid b\\\wedge \\a\mid c\end{array}}\right\}\;\Rightarrow \;\left.{\begin{array}{c}b=k_{1}a,\;k_{1}\in \mathbb {Z} {\mbox{ izanik}}\\\wedge \\c=k_{2}a,\;k_{2}\in \mathbb {Z} {\mbox{ izanik}}\end{array}}\right\}\;\Rightarrow xb+yc=x(k_{1}a)+y(k_{2}a)=$$ $$=(xk_{1}+yk_{2})a,\;xk_{1}+yk_{2}\in \mathbb {Z} {\mbox{ izanik }}\;\Rightarrow \;a\mid xb+yc.$$ ${\textstyle \Box }$

• ${\textstyle b,c\in \mathbb {Z} }$ emanik, $$xb+yc,\quad x,y\in \mathbb {Z} {\mbox{ izanik}},$$ adierazpenari ${\textstyle b,c\in \mathbb {Z} }$ zenbakien konbinazio lineal deituko diogu.

  ${\textstyle a}$ zenbakiak ${\textstyle b}$ eta ${\textstyle c}$ zenbakiak zatitzen baditu, [propietateak]-5 Teoremaren arabera, ${\textstyle a}$ zenbakiak ${\textstyle b}$ eta ${\textstyle c}$ zenbakien edozein konbinazio lineal zatituko du. Propietate hori zabal daiteke honela:

• ${\textstyle b_{1},\cdots ,b_{n}\in \mathbb {Z} }$ emanik, $$x_{1}b_{1}+\cdots +x_{n}b_{n},\quad x_{1},\ldots ,x_{n}\in \mathbb {Z} {\mbox{ izanik}},$$ adierazpenari ${\textstyle b_{1},\ldots ,b_{n}}$ zenbakien konbinazio lineal deituko diogu.

  ${\textstyle a}$ zenbakiak ${\textstyle b_{1},\ldots ,b_{n}}$ zenbakiak zatitzen baditu, ${\textstyle a}$ zenbakiak ${\textstyle b_{1},\ldots ,b_{n}}$ zenbakien edozein konbinazio lineal zatituko du: $$a\mid b_{i},\;i=1,\cdots ,n\;\Rightarrow \;(\forall x_{1},\cdots ,x_{n}\in \mathbb {Z} )\quad a\mid x_{1}b_{1}+\cdots +x_{n}b_{n}.$$

Adibidea. [Grimaldi4.20] Ba al daude ${\textstyle 5x+10y+20z=1003}$ ekuazioa betetzen duten zenbaki osoak?

Demagun ${\textstyle x,y,z}$ zenbaki oso horiek daudela. ${\textstyle 5\mid 5}$, ${\textstyle 5\mid 10}$ eta ${\textstyle 5\mid 20}$ betetzen direnez, ${\textstyle 5\mid 1003}$ ere beteko litzateke; baina hori ez da gertatzen. Hortaz, ez daude ekuazioa betetzen duten ${\textstyle x,y,z}$ zenbaki osoak.
Definizioa. Izan bedi ${\textstyle n\in \mathbb {Z} ^{+}}$, ${\textstyle n>1}$.

Esango dugu ${\textstyle n}$ zenbaki lehena dela bere zatitzaile positibo bakarrak ${\textstyle n}$ eta ${\textstyle 1}$ badira: $$m\mid n,\quad m\in \mathbb {Z} ^{+}\,\Longrightarrow \,m=1\,\vee \,m=n;$$ eta esango dugu ${\textstyle n}$ zenbaki konposatua dela ez bada lehena: $$\exists m_{1},m_{2}\in \mathbb {Z} ^{+}\;{\mbox{ non }}\;n=m_{1}m_{2},\,\quad 1<m_{1}<n,\;1<m_{2}<n.$$
Adibidea. ${\textstyle 12}$ zenbaki konposatua da, ${\textstyle 12>1}$ delako eta ${\textstyle 1}$, ${\textstyle 2}$, ${\textstyle 3}$, ${\textstyle 4}$, ${\textstyle 6}$ eta ${\textstyle 12}$ zatitzaileak dituelako.

${\textstyle 11}$ zenbaki lehena da, ${\textstyle 11>1}$ delako eta bere zatitzaile positibo bakarrak ${\textstyle 1}$ eta ${\textstyle 11}$ direlako.
Hurrengo Teoreman zenbaki lehenen eta konposatuen arteko erlazio bat frogatuko dugu.

Teorema. [lekon] Zenbaki konposatu orok zatitzaile lehenen bat dauka. Hau da, ${\textstyle n\in \mathbb {Z} ^{+}}$, ${\textstyle n>1}$ emanik, $$n\,{\mbox{ konposatua }}\,\Longrightarrow \exists p\in \mathbb {Z} ^{+},\,p\,{\mbox{ lehena eta }}\,p\mid n.$$

Froga.

Izan bedi ${\textstyle S}$ zatitzaile lehenik ez duten zenbaki oso konposatu guztien multzoa: $$S=\{x\in \mathbb {Z} ^{+}\;:\;x\;{\mbox{ konposatua da eta ez du zatitzaile lehenik}}\}.$$ Frogatuko dugu, absurdora eramanez, ${\textstyle S=\emptyset }$ dela.

Demagun ${\textstyle S\neq \emptyset }$ dela. ${\textstyle S}$ multzoa ${\textstyle \mathbb {Z} ^{+}}$ multzoaren azpimultzo ez-hutsa denez, ordena onaren printzipioaren arabera, ${\textstyle S}$ multzoak lehen elementua izango du, ${\textstyle m}$.

${\textstyle m\in S}$ denez, ${\textstyle m}$ konposatua da; beraz, ${\textstyle m_{1},m_{2}\in \mathbb {Z} ^{+}}$ badaude, non ${\textstyle m=m_{1}m_{2}}$ den, ${\textstyle 1<m_{1}<m,\;1<m_{2}<m}$ izanik.

${\textstyle m}$ da ${\textstyle S}$ multzoaren minimoa eta ${\textstyle m_{1}<m}$ da; beraz, ${\textstyle m_{1}\not \in S}$ beteko da. Hortaz, ${\textstyle m_{1}}$ lehena da edo zatitzaile lehenen bat dauka.

${\textstyle m_{1}}$ lehena bada, ${\textstyle m_{1}}$ lehena da eta ${\textstyle m_{1}\mid m}$ betetzen da.

${\textstyle m_{1}}$ zenbakiak ${\textstyle p}$ zatitzaile lehen bat badauka, ${\textstyle p}$ lehena da eta ${\textstyle p\mid m_{1}}$ eta ${\textstyle m_{1}\mid m}$; hortaz, ${\textstyle p\mid m}$.

Bi kasuetan kontraesan bat aurkitu dugu, ${\textstyle m}$ zenbakiak ez baitauka zatitzaile lehenik. Hortaz, ${\textstyle S=\emptyset }$ da, eta zenbaki konposatu orok zatitzaile lehenen bat badauka. ${\textstyle \Box }$

Teorema. (Euklides, Elementuak, IX, 20)

Infinitu zenbaki lehen daude.

Froga.

Absurdora eramanez frogatuko dugu.

Suposa dezagun zenbaki lehenen kopurua finitua dela: ${\textstyle p_{1},\ldots ,p_{k}}$.

Izan bitez ${\textstyle a=p_{1}\ldots p_{k}}$ eta ${\textstyle A=a+1}$.

Orduan, ${\textstyle p_{i}\mid a}$, ${\textstyle i=1,\ldots ,k}$ dugu eta, hortaz, ${\textstyle a\geq p_{i}}$, ${\textstyle i=1,\ldots ,k}$; hortik ${\textstyle A\neq p_{i}}$, ${\textstyle i=1,\ldots ,k}$ aterako dugu. Beraz, ${\textstyle A}$ konposatua da. [lekon] Teoremaren arabera, badago ${\textstyle p_{j}\in \{p_{1},\ldots ,p_{k}\}}$ zenbaki lehenen bat, non ${\textstyle p_{j}\mid A}$ betetzen den.

Orduan, ${\textstyle p_{j}\mid A}$ eta ${\textstyle p_{j}\mid a}$ betetzen dira; hortaz, ${\textstyle p_{j}\mid 1A+(-1)a}$ ere beteko da. Baina ${\textstyle 1A+(-1)a=A-a=1}$ dugu; beraz, ${\textstyle p_{j}\mid 1}$ dugu; eta hori ezinezkoa da ${\textstyle p_{j}>1}$ delako.

Beraz, zenbaki lehenen kopuruak ezin du kopuru finitua izan. Hau da, infinitu zenbaki lehen daude. ${\textstyle \Box }$

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}}$$

4.1.4 Zatitzaile komun handiena

Definizioa. . Izan bitez ${\textstyle a,b\in \mathbb {Z} }$ eta izan bedi ${\textstyle c\in \mathbb {Z} ^{+}}$. Esango dugu ${\textstyle c}$ zenbakia ${\textstyle a}$ eta ${\textstyle b}$ zenbakien zatitzaile komun bat dela ${\textstyle c\mid a}$ eta ${\textstyle c\mid b}$ betetzen badira.

Adibidea. [zatikomu] ${\textstyle -24}$ zenbakiaren zatitzaile positiboak ${\textstyle 1}$, ${\textstyle 2}$, ${\textstyle 3}$, ${\textstyle 4}$, ${\textstyle 6}$, ${\textstyle 8}$, ${\textstyle 12}$ eta ${\textstyle 24}$ dira. ${\textstyle 32}$ zenbakiaren zatitzaile positiboak ${\textstyle 1}$, ${\textstyle 2}$, ${\textstyle 4}$, ${\textstyle 8}$, ${\textstyle 16}$ eta ${\textstyle 32}$ dira. Bion zatitzaile positibo komunak ${\textstyle 1}$, ${\textstyle 2}$, ${\textstyle 4}$ eta ${\textstyle 8}$ dira.

Definizioa. . Izan bitez ${\textstyle a,b\in \mathbb {Z} }$, ${\textstyle a\neq 0}$ edo ${\textstyle b\neq 0}$, eta izan bedi ${\textstyle d\in \mathbb {Z} ^{+}}$. Esango dugu ${\textstyle d}$ zenbakia ${\textstyle a}$ eta ${\textstyle b}$ zenbakien zatitzaile komun handienetako bat dela baldin

1. ${\textstyle d}$ bada ${\textstyle a}$ eta ${\textstyle b}$ zenbakien zatitzaile komun bat: $$d\mid a\,{\mbox{ eta }}\,d\mid b;$$
2. ${\textstyle a}$ eta ${\textstyle b}$ zenbakien edozein zatitzaile komunek ${\textstyle d}$ zatitzen badu (${\textstyle d}$ “handienetakoa” da zatigarritasunaren arabera): $$(\forall c\in \mathbb {Z} ^{+})\quad c\mid a,\quad c\mid b\,\Rightarrow \,c\mid d.$$

Adibidea. [zatikomu] Adibidean ikus dezakegu ${\textstyle -24}$ eta ${\textstyle 32}$ zenbakien zatitzaile komun handiena ${\textstyle 8}$ dela.

Galdera batzuk egin ditzakegu: beti aurkitu ahal izango dugu zatitzaile komun handienetako bat? bi zenbaki osok zenbait zatitzaile komun handien izan ditzakete?

Azkenekoari erantzuteko hona hemen teorema hau.

Teorema. (Zatitzaile komun handiena bakarra da)

${\textstyle a,b\in \mathbb {Z} }$ emanik, ${\textstyle a}$ eta ${\textstyle b}$ zenbakien zatitzaile komun handiena, existitzen bada, bakarra da.

Froga.

Suposa dezagun ${\textstyle a}$ eta ${\textstyle b}$ zenbakien bi zatitzaile komun handien daudela, ${\textstyle d_{1}}$ eta ${\textstyle d_{2}}$. Frogatuko dugu ${\textstyle d_{1}=d_{2}}$ dela.

${\textstyle d_{1}}$ ${\textstyle a}$ eta ${\textstyle b}$ zenbakien zatitzaile komuna da ${\textstyle \Rightarrow }$ ${\textstyle d_{1}\mid a}$ eta ${\textstyle d_{1}\mid b}$ ${\textstyle \Rightarrow }$ ${\textstyle d_{1}\mid d_{2}}$, ${\textstyle d_{2}}$ delako ${\textstyle a}$ eta ${\textstyle b}$ zenbakien zatitzaile komun handienetako bat.

Antzeko eran frogatuko genuke ${\textstyle d_{2}\mid d_{1}}$ ere betetzen dela. Orduan, $$\left.{\begin{array}{ll}d_{1}\mid d_{2}\\d_{2}\mid d_{1}\\\end{array}}\right\}\Rightarrow d_{1}=d_{2}\,{\mbox{ edo }}\,d_{1}=-d_{2}.$$ ${\textstyle d_{1},d_{2}\in \mathbb {Z} ^{+}}$ denez, aukera bakarra ${\textstyle d_{1}=d_{2}}$ da. ${\textstyle \Box }$

Oharrak.

1. ${\textstyle a,b\in \mathbb {Z} }$ emanik, ${\textstyle a}$ eta ${\textstyle b}$ zenbakien zatitzaile komun handiena badago, ${\textstyle {\mbox{zkh}}(a,b)}$ adieraziko dugu.
2. ${\textstyle {\mbox{zkh}}(a,b)}$ badago, ${\textstyle {\mbox{zkh}}(b,a)={\mbox{zkh}}(a,b)}$ beteko da.
3. ${\textstyle {\mbox{zkh}}(0,0)}$ ez dago definiturik.
4. ${\textstyle a\in \mathbb {Z} ^{*}}$ bada, erraz froga daiteke ${\textstyle {\mbox{zkh}}(a,0)}$ badagoela, eta ${\textstyle {\mbox{zkh}}(a,0)=\mid a\mid }$ betetzen dela.
   • ${\textstyle \mid a\mid }$ zenbakia ${\textstyle a}$ eta ${\textstyle 0}$ zenbakien zatitzaile komuna da: $$a=\mid a\mid {\mbox{ edo }}a=(-1)\cdot \mid a\mid \quad \Rightarrow \;\mid a\mid {\big |}\;a$$

$$\mid a\mid \;{\big |}\;0{\mbox{ (edozein zenbaki oso da 0 zenbakiaren zatitzailea).}}$$

1. • ${\textstyle \mid a\mid }$ zenbakia ${\textstyle a}$ eta ${\textstyle 0}$ zenbakien zatitzaile komun handiena da: ${\textstyle c\in \mathbb {Z} ^{+}}$ emanik, $$\left.{\begin{array}{ll}c\mid a\\c\mid 0\\\end{array}}\right\}\;\Rightarrow \;c\mid a\;\Rightarrow \;c\;{\big |}\;\mid a\mid {\mbox{ (}}\mid a\mid =a{\mbox{ edo }}\mid a\mid =-a{\mbox{ delako).}}$$

Laburbilduz, ${\textstyle a}$ edo ${\textstyle b}$ zenbakietako bat bakarrik ${\textstyle 0}$ bada, badago ${\textstyle {\mbox{zkh}}(a,b)}$. Beraz, ${\textstyle {\mbox{zkh}}(a,b)}$ existitzen dela frogatzeko ${\textstyle a}$ eta ${\textstyle b}$ positiboak direla suposatuko dugu.

Teorema. (Zatitzaile komun handiena existitzen da) [zkhex]

${\textstyle a,b\in \mathbb {Z} ^{+}}$ zenbaki oso positibo guztietarako existitzen da zatitzaile komun handiena.

Froga.

Har dezagun ${\textstyle a}$ eta ${\textstyle b}$ zenbakien konbinazio lineal positibo guztien multzoa: $$S=\{xa+yb\;:\;x,y\in \mathbb {Z} \quad {\mbox{eta}}\quad xa+yb>0\}.$$

${\textstyle S\subseteq \mathbb {Z} ^{+}}$ da. ${\textstyle 0<a=1\cdot a+0\cdot b}$ betetzen denez, ${\textstyle a\in S}$ dugu eta, beraz, ${\textstyle S\neq \emptyset }$ da. Ordena onaren printzipioaren arabera, ${\textstyle S}$ multzoak elementu minimoa du; izan bedi ${\textstyle d:=\min S}$.

${\textstyle d\in S}$ denez, ${\textstyle d}$ izango da ${\textstyle a}$ eta ${\textstyle b}$ zenbakien konbinazio lineal positibo bat; hau da, ${\textstyle d\in \mathbb {Z} ^{+}}$ eta $$d=xa+yb,\quad x,y\in \mathbb {Z} {\mbox{ izanik}}.$$

Ikus dezagun ${\textstyle d={\mbox{zkh}}(a,b)}$ dela:

• ${\textstyle d}$ zenbakia ${\textstyle a}$ eta ${\textstyle b}$ zenbakien zatitzaile komun bat da:

  • Suposa dezagun ${\textstyle d\not \mid a}$ dela, eta kontraesan bat aurkituko dugu:

    ${\textstyle d\not \mid a}$ bada, ${\textstyle a}$ zati ${\textstyle d}$ zatiketa euklidestarra egitean, ${\textstyle 0}$ ez den hondar bat lortuko dugu: $${\begin{array}{rl}a&{\underline {\vline d}}\\r&q\end{array}},\quad \quad r>0.$$ Hau da, ${\textstyle a=qd+r}$ da, ${\textstyle 0<r<d}$ izanik. Hortaz, ${\textstyle 0<r=a-qd=a-q(xa+yb)=(1-qx)a+(-qy)b}$ ere izango dugu. Beraz, ${\textstyle r}$ hondarra ${\textstyle a}$ eta ${\textstyle b}$ zenbakien konbinazio lineal positibo bat da. Orduan, ${\textstyle r\in S}$ dugu eta, ondorioz, ${\textstyle r\geq d=\min S}$ beteko da; eta hori ezinezkoa da, ${\textstyle r<d}$ delako.

  • ${\textstyle d\mid b}$ betetzen dela frogatzeko, antzeko arrazoibidea erabiliko genuke.

• ${\textstyle d}$ zenbakia ${\textstyle a}$ eta ${\textstyle b}$ zenbakien zatitzaile komun handiena da: ${\textstyle c\in \mathbb {Z} ^{+}}$ emanik, $$\left.{\begin{array}{ll}c\mid a\\c\mid b\\\end{array}}\right\}\;\Rightarrow \;c\mid xa+yb=d$$ (zenbaki oso batek bi zenbaki zatitzen baditu, horien edozein konbinazio lineal zatituko duelako).

${\textstyle \Box }$

Oharrak.

1. Orain, erraza da frogatzea, ${\textstyle a,b\in \mathbb {Z} }$ emanik, beti existitzen dela ${\textstyle {\mbox{zkh}}(a,b)}$ (${\textstyle a=b=0}$ denean izan ezik).

   ${\textstyle {\mbox{zkh}}(\mid a\mid ,\mid b\mid )}$ existitzen dela jadanik frogatu dugu; eta ${\textstyle {\mbox{zkh}}(a,b)={\mbox{zkh}}(\mid a\mid ,\mid b\mid )}$ betetzen dela erraz froga dezakegu.

   Horretarako, izan bedi ${\textstyle d:={\mbox{zkh}}(\mid a\mid ,\mid b\mid )}$ (badakigu existitzen dena); ikus dezagun ${\textstyle d={\mbox{zkh}}(a,b)}$ dela:

   • ${\textstyle d}$ zenbakia ${\textstyle a}$ eta ${\textstyle b}$ zenbakien zatitzaile komun bat da: $$d={\mbox{zkh}}(\mid a\mid ,\mid b\mid )\;\Rightarrow \;\left\{{\begin{array}{ll}d{\big |}\;\mid a\mid \;\Rightarrow \;d\mid a\\\\d{\big |}\;\mid b\mid \;\Rightarrow \;d\mid b\\\end{array}}\right.$$

   • ${\textstyle d}$ zenbakia ${\textstyle a}$ eta ${\textstyle b}$ zenbakien zatitzaile komun handiena da: ${\textstyle c\in \mathbb {Z} ^{+}}$ emanik, $$\left.{\begin{array}{ll}c\mid a\\c\mid b\\\end{array}}\right\}\;\Rightarrow \;\left\{{\begin{array}{ll}c{\big |}\;\mid a\mid \\\\c{\big |}\;\mid b\mid \\\end{array}}\right\}\;\Rightarrow \;c\mid d,$$ ${\textstyle d}$ zenbakia ${\textstyle \mid a\mid }$ eta ${\textstyle \mid b\mid }$ zenbakien zatitzaile komun handiena delako.

2. ${\textstyle a,b\in \mathbb {Z} }$ emanik, ${\textstyle a\neq 0}$ edo ${\textstyle b\neq 0}$, ${\textstyle {\mbox{zkh}}(a,b)}$ izango da ${\textstyle a}$ eta ${\textstyle b}$ zenbakien konbinazio lineal bezala adieraz daitekeen zenbaki oso positiborik txikiena: $${\mbox{zkh}}(a,b)=\min\{xa+yb\,:\,x,y\in \mathbb {Z} \,{\mbox{ eta }}\,xa+yb>0\}.$$

   Emaitza hori [zkhex] Teoremaren frogatik atera dezakegu; ${\textstyle a\in \mathbb {Z} ^{-}}$ edo ${\textstyle b\in \mathbb {Z} ^{-}}$ direnean frogatzeko, nahikoa da kontuan hartzea ${\textstyle {\mbox{zkh}}(a,b)={\mbox{zkh}}(\mid a\mid ,\mid b\mid )}$ dela eta $$\{xa+yb\,:\,x,y\in \mathbb {Z} \,{\mbox{ eta }}\,xa+yb>0\}=$$ $$=\{x\mid a\mid +y\mid b\mid \,:\,x,y\in \mathbb {Z} \,{\mbox{ eta }}\,x\mid a\mid +y\mid b\mid >0\}\,{\mbox{dela}}.$$ Suposa dezagun, esaterako, ${\textstyle a<0}$ eta ${\textstyle b>0}$ direla. Orduan, $$z\in \{x\mid a\mid +y\mid b\mid \,:\,x,y\in \mathbb {Z} \,{\mbox{ eta }}\,x\mid a\mid +y\mid b\mid >0\}\;\Rightarrow$$ $$\Rightarrow \;z=x_{1}\mid a\mid +y_{1}\mid b\mid ,\,x_{1},y_{1}\in \mathbb {Z} \,{\mbox{ eta }}\,x_{1}\mid a\mid +y_{1}\mid b\mid >0\,{\mbox{ izanik}}\;\Rightarrow$$ $$\Rightarrow \;z=x_{1}(-a)+y_{1}b=(-x_{1})a+y_{1}b,\,(-x_{1}),y_{1}\in \mathbb {Z} \,{\mbox{ eta }}\,(-x_{1})a+y_{1}b>0\,{\mbox{ izanik}}\;\Rightarrow$$ $$\Rightarrow \;z\in \{xa+yb\,:\,x,y\in \mathbb {Z} \,{\mbox{ eta }}\,xa+yb>0\}.$$ Eta hortik hau aterako dugu: $$\{x\mid a\mid +y\mid b\mid \,:\,x,y\in \mathbb {Z} \,{\mbox{ eta }}\,x\mid a\mid +y\mid b\mid >0\}\subseteq \{xa+yb\,:\,x,y\in \mathbb {Z} \,{\mbox{ eta }}\,xa+yb>0\}.$$ Beste partekotasuna antzeko eran frogatuko genuke.

3. ${\textstyle a,b\in \mathbb {Z} }$ emanik, ${\textstyle a\neq 0}$ edo ${\textstyle b\neq 0}$, $${\mbox{zkh}}(a,b)=xa+yb,\,x,y\in \mathbb {Z} \,{\mbox{ izanik}};$$ baina ${\textstyle x,y}$ ez dira bakarrak; izan ere, ${\textstyle {\mbox{zkh}}(a,b)=xa+yb}$ bada, ${\textstyle p\in \mathbb {Z} }$ guztietarako hau beteko da: $${\mbox{zkh}}(a,b)=(x+pb)a+(y-pa)b.$$

Adibidea. $${\mbox{zkh}}(24,32)={\mbox{zkh}}(-24,32)=8$$ $${\begin{array}{rl}8=&(-1)24+1\cdot 32=(-1+32)24+(1-24))32=\\=&31\cdot 24+(-23)\cdot 32=(-1-64)24+(1+48)32=\\=&(-65)24+49\cdot 32=\cdots \end{array}}$$

${\textstyle a,b\in \mathbb {Z} }$ eta ${\textstyle d\in \mathbb {Z} ^{+}}$ emanik, $$d={\mbox{zkh}}(a,b)\;\Rightarrow \;d=xa+yb,x,y\in \mathbb {Z} \,{\mbox{ izanik}}.$$ Baina elkarrekikoa ez da orokorrean betetzen, ${\textstyle d=1}$ denean izan ezik. $$d=xa+yb,\,x,y\in \mathbb {Z} \,{\mbox{ izanik}}\;\Rightarrow d\geq {\mbox{zkh}}(a,b).$$

Definizioa. . ${\textstyle a,b\in \mathbb {Z} }$ emanik, esango dugu ${\textstyle a,b}$ zenbakiak zenbaki lehen erlatiboak direla ${\textstyle {\mbox{zkh}}(a,b)=1}$ denean.

. ${\textstyle a,b\in \mathbb {Z} }$ emanik, $$a,b\,{\mbox{ lehen erlatiboak}}\;\Longleftrightarrow \,\exists x,y\in \mathbb {Z} ,\,{\mbox{ non }}\,xa+yb=1\,{\mbox{den}}.$$

Adibidea. $$16=(-2)24+2\cdot 32.\,{\mbox{ Hortaz,}}\,{\mbox{zkh}}(24,32)\leq 16\,{\mbox{ da}}.$$ $$1=(-1)3+1\cdot 4.\,{\mbox{ Hortaz,}}\,{\mbox{zkh}}(3,4)=1\,{\mbox{ eta }}\,3,4{\mbox{ zenbaki lehen erlatiboak dira}}.$$

4.1.5 Euklidesen algoritmoa

${\textstyle a,b\in \mathbb {Z} ^{+}}$ emanik, ${\textstyle b\mid a}$ bada, ${\textstyle {\mbox{zkh}}(a,b)=b}$ izango da. Bestela, ${\textstyle {\mbox{zkh}}(a,b)}$ kalkulatzeko algoritmo hau erabiliko dugu:

Ondoko zatiketak egingo ditugu: $${\begin{array}{cllll}{\begin{array}{rrll}a&{\underline {\vline b}}\\r_{1}&q_{1}&\\\end{array}}&&a=q_{1}b+r_{1},&&0<r_{1}<b;\\\\{\begin{array}{rrll}b&{\underline {\vline r_{1}}}\\r_{2}&q_{2}&\\\end{array}}&&b=q_{2}r_{1}+r_{2},&&0<r_{2}<r_{1};\\\\{\begin{array}{rrll}r_{1}&{\underline {\vline r_{2}}}\\r_{3}&q_{3}&\\\end{array}}&&r_{1}=q_{3}r_{2}+r_{3},&&0<r_{3}<r_{2};\\\\\vdots &&\vdots &&\vdots \\\\{\begin{array}{rrll}r_{i}&{\underline {\vline r_{i+1}}}\\r_{i+2}&q_{i+2}&\\\end{array}}&&r_{i}=q_{i+2}r_{i+1}+r_{i+2},&&0<r_{i+2}<r_{i+1};\\\\\vdots &&\vdots &&\vdots \\\\\end{array}}$$

Gero eta hondar txikiagoak lortzen ditugunez, noizbait 0 hondarra lortuko dugu: $${\begin{array}{cllll}{\begin{array}{rl}r_{k-1}&{\underline {\vline r_{k}}}\\0&q_{k+1}&\\\end{array}}&&r_{k-1}=q_{k+1}r_{k}+0;&\quad &\end{array}}$$ $$b>r_{1}>r_{2}>\cdots >r_{k-1}>r_{k}>0\;(=r_{k+1}).$$

Orduan, ${\textstyle r_{k}}$, ${\textstyle 0}$ ez den azkeneko hondarra, ${\textstyle {\mbox{zkh}}(a,b)}$ da: $$r_{k}={\mbox{zkh}}(a,b).$$

Froga.

Berdintza hauek dauzkagu:\label{hiru} $$\left.{\begin{array}{l}a=q_{1}b+r_{1}\\b=q_{2}r_{1}+r_{2}\\r_{i}=q_{i+2}r_{i+1}+r_{i+2}\quad i=1,\ldots ,k-2\end{array}}\right\};{\mbox{ (hiru) }}$$ ${\textstyle r_{0}:=b}$ eta ${\textstyle r_{-1}:=a}$ izendatzen baditugu, ([hiru]) honela idatz ditzakegu: $$r_{i}=q_{i+2}r_{i+1}+r_{i+2}\quad i=-1,\ldots ,k-2;{\mbox{ (ri) }}$$ eta, horrez gain, beste hau ere badugu: $$r_{k-1}=q_{k+1}r_{k}.{\mbox{ (rk) }}$$

${\textstyle r_{k}={\mbox{zkh}}(a,b)}$ dela frogatzeko, ondokoa frogatu beharko dugu:

1. ${\textstyle r_{k}}$ hondarra ${\textstyle a}$ eta ${\textstyle b}$ zenbakien zatitzaile komun bat da; hau da, ${\textstyle r_{k}\mid a}$ eta ${\textstyle r_{k}\mid b}$ betetzen dira. Horretarako, ondoz ondo frogatuko dugu ${\textstyle r_{k}}$ hondarrak ${\textstyle r_{k}}$, ${\textstyle r_{k-1}}$, ${\textstyle r_{k-2}}$, ${\textstyle r_{k-3}}$, etab. zatitzen dituela, ${\textstyle r_{0}=b}$ eta ${\textstyle r_{-1}=a}$ ere zatitzen dituela frogatu arte.

   ([ri]) ekuazioan ikus dezakegu ${\textstyle i=-1,\ldots ,k-2}$ balioetarako ${\textstyle r_{i}}$ hondarra ${\textstyle r_{i+2}}$ eta ${\textstyle r_{i+1}}$ hondarren konbinazio lineala dela, eta hori erabiliko dugu.

   • Argi dago ${\textstyle r_{k}\mid r_{k}}$ betetzen dela.

   • Bestalde, ([rk]) ekuaziotik ${\textstyle r_{k}\mid r_{k-1}}$ ateratzen da.

   • ${\textstyle r_{k}\mid r_{k-2}}$ frogatzeko, ([ri]) ekuazioetako ${\textstyle i=k-2}$ kasuan, ${\textstyle r_{k-2}=q_{k}r_{k-1}+r_{k}}$ berdintza dugu; hau da, ${\textstyle r_{k-2}}$ hondarra ${\textstyle r_{k}}$ eta ${\textstyle r_{k-1}}$ hondarren konbinazio lineala da. ${\textstyle r_{k}\mid r_{k}}$ eta ${\textstyle r_{k}\mid r_{k-1}}$ frogatu ditugunez, ${\textstyle r_{k}\mid r_{k-2}}$ daukagu.

   • ${\textstyle r_{k}\mid r_{k-3}}$ frogatzeko, antzeko arrazoibidea erabiliko dugu: ([ri]) ekuazioetako ${\textstyle i=k-3}$ kasuan, ${\textstyle r_{k-3}=q_{k-1}r_{k-2}+r_{k-1}}$ berdintza dugu; hau da, ${\textstyle r_{k-3}}$ hondarra ${\textstyle r_{k-1}}$ eta ${\textstyle r_{k-2}}$ hondarren konbinazio lineala da. ${\textstyle r_{k}\mid r_{k-1}}$ eta ${\textstyle r_{k}\mid r_{k-2}}$ frogatuta daudenez, ${\textstyle r_{k}\mid r_{k-3}}$ ere beteko da.

   • Antzeko eran frogatuko ditugu ${\textstyle r_{k}\mid r_{k-4}}$, ${\textstyle r_{k}\mid r_{k-5}}$, etab. ${\textstyle r_{k}\mid r_{0}=b}$ eta ${\textstyle r_{k}\mid r_{-1}=a}$ kasuetara heldu arte.

2. ${\textstyle r_{k}}$ hondarra ${\textstyle a}$ eta ${\textstyle b}$ zenbakien zatitzaile komun handiena da; hau da, ${\textstyle a}$ eta ${\textstyle b}$ zenbakien edozein zatitzaile komun ${\textstyle r_{k}}$ hondarraren zatitzailea da.

   Izan bedi ${\textstyle c\in \mathbb {Z} ^{+}}$ ${\textstyle a}$ eta ${\textstyle b}$ zenbakien zatitzaile komun bat, hots, ${\textstyle c\mid a}$ eta ${\textstyle c\mid b}$ betetzen dira. Frogatu behar dugu ${\textstyle c\mid r_{k}}$ ere betetzen dela. Horretarako, ondoz ondo frogatuko dugu ${\textstyle c}$ zenbakiak ${\textstyle r_{-1}}$, ${\textstyle r_{0}}$, ${\textstyle r_{1}}$, ${\textstyle r_{2}}$, etab. zatitzen dituela, ${\textstyle r_{k}}$ hondarrera heldu arte.

   ([ri]) ekuazioetatik ${\textstyle r_{i+2}}$ bakanduz gero, ekuazio hauek lortuko ditugu: $$r_{i+2}=r_{i}-q_{i+2}r_{i+1}\quad i=-1,\ldots ,k-2.\;{\mbox{ (alder) }}$$ Ohar gaitezke, orduan, ${\textstyle i=-1,\ldots ,k-2}$ balioetarako ${\textstyle r_{i+2}}$ hondarra ${\textstyle r_{i}}$ eta ${\textstyle r_{i+1}}$ hondarren konbinazio lineala dela; propietate hori erabiliko dugu.

   • ${\textstyle c\mid a=r_{-1}}$.

   • ${\textstyle c\mid b=r_{0}}$.

   • ${\textstyle c\mid r_{1}}$ frogatzeko, ([alder]) ekuazioetako ${\textstyle i=-1}$ kasuan, ${\textstyle r_{1}=r_{-1}-q_{1}r_{0}}$ dugu; hau da, ${\textstyle r_{1}}$ hondarra ${\textstyle r_{-1}}$ eta ${\textstyle r_{0}}$ hondarren konbinazio lineala da. ${\textstyle c\mid r_{-1}}$ eta ${\textstyle c\mid r_{0}}$ betetzen direnez, ${\textstyle c\mid r_{1}}$ ere beteko da.

   • ${\textstyle c\mid r_{2}}$ frogatzeko, arrazoibidea antzekoa da: ([alder]) ekuazioetako ${\textstyle i=0}$ kasuan, ${\textstyle r_{2}=r_{0}-q_{2}r_{1}}$ dugu; hau da, ${\textstyle r_{2}}$ hondarra ${\textstyle r_{0}}$ eta ${\textstyle r_{1}}$ hondarren konbinazio lineala da. ${\textstyle c\mid r_{0}}$ eta ${\textstyle c\mid r_{1}}$ betetzen direla frogatu dugunez, ${\textstyle c\mid r_{2}}$ ere beteko da.

   • Antzeko eran frogatuko dugu ${\textstyle c\mid r_{3}}$, ${\textstyle c\mid r_{4}}$, etab. betetzen direla ${\textstyle c\mid r_{k}}$ betetzen dela frogatu arte.

${\textstyle \Box }$

Adibidea. [zkh] ${\textstyle {\mbox{zkh}}(250,12)}$ kalkulatzeko: $${\begin{array}{rrll}250&{\underline {\vline 12}}\\10&20&\\\end{array}}\quad \quad {\begin{array}{rrll}12&{\underline {\vline 10}}\\2&1&\\\end{array}}\quad \quad {\begin{array}{rrll}10&{\underline {\vline 2}}\\0&5&\\\end{array}}.$$ Hortaz, $${\mbox{zkh}}(250,12)={\mbox{zkh}}(-250,12)={\mbox{zkh}}(250,-12)={\mbox{zkh}}(-250,-12)=2.$$

Oharrak.

1. Euklidesen algoritmoa bai ${\textstyle a>b}$ denean bai ${\textstyle a<b}$ denean erabil daiteke; azken kasu horretan zatiketa bat gehiago egin beharko da.
2. Euklidesek algoritmoak ${\textstyle {\mbox{zkh}}(a,b)}$ ${\textstyle a,b}$ zenbakien konbinazio lineal bezala adierazteko metodoa erakutsi digu.

Adibideak.

1. [zkh] adibidean, ${\textstyle {\mbox{zkh}}(250,12)=2}$ kalkulatu dugu. ${\textstyle 2}$ emaitza ${\textstyle 250}$ eta ${\textstyle 12}$ zenbakien konbinazio lineal bezala adierazteko, ${\textstyle 2}$ azkeneko hondar ez-nulua ${\textstyle 10}$ eta ${\textstyle 12}$ zenbakien konbinazio lineal bezala adierazten hasiko gara: $${\begin{array}{cllll}{\begin{array}{rrll}12&{\underline {\vline 10}}\\2&1&\\\end{array}}&&12=1\cdot 10+2,&&2=12-1\cdot 10.\\\end{array}}$$ Orain, kontuan izanik ${\textstyle 10}$ dela aurreko hondarra, ${\textstyle 10}$ hori ${\textstyle 250}$ eta ${\textstyle 12}$ zenbakien konbinazio lineal bezala adieraz dezakegu: $${\begin{array}{cllll}{\begin{array}{rrll}250&{\underline {\vline 12}}\\10&20&\\\end{array}}&&250=20\cdot 12+10,&&10=250-20\cdot 12.\\\end{array}}$$ Orduan, hau lortuko dugu: $$2=12-1\cdot {\bf {10}}=12-1\cdot (250-20\cdot 12)=(-1)\cdot 250+21\cdot 12.$$
2. $${\mbox{zkh}}(-250,12)=2=1\cdot (-250)+21\cdot 12.$$ $${\mbox{zkh}}(250,-12)=2=(-1)\cdot 250+(-21)\cdot (-12).$$ $${\mbox{zkh}}(-250,-12)=2=1\cdot (-250)+(-21)\cdot (-12).$$
3. Euklidesen algoritmoa erabiliko dugu ${\textstyle {\mbox{zkh}}(250,111)}$ kalkulatzeko eta ${\textstyle 250}$ eta ${\textstyle 111}$ zenbakien konbinazio lineal bezala adierazteko: $${\begin{array}{cllll}{\begin{array}{rrll}250&{\underline {\vline 111}}\\28&2&\\\end{array}}&&250=2\cdot 111+28,&&28=250-2\cdot 111;\\\\{\begin{array}{rrll}111&{\underline {\vline 28}}\\27&3&\\\end{array}}&&111=3\cdot 28+27,&&27=111-3\cdot 28;\\\\{\begin{array}{rrll}28&{\underline {\vline 27}}\\1&1&\\\end{array}}&&28=1\cdot 27+1,&&1=28-1\cdot 27;\\\\{\begin{array}{rrll}27&{\underline {\vline 1}}\\0&27&\\\end{array}}&&27=1\cdot 27.&&\\\\\end{array}}$$ ${\textstyle {\mbox{zkh}}(250,111)=1}$; beraz, ${\textstyle 250}$ eta ${\textstyle 111}$ zenbaki lehen erlatiboak dira. $${\begin{array}{rl}1=&28-1\cdot 27=28-1\cdot (111-3\cdot 28)=\\=&(-1)\cdot 111+4\cdot 28=(-1)\cdot 111+4\cdot (250-2\cdot 111)=\\=&4\cdot 250+(-9)\cdot 111.\end{array}}$$

4.1.6 Multiplo komun txikiena

Definizioa. Izan bitez $a,b,c\in \mathbb {Z} ^{+}$, esango dugu $c$ zenbakia $a$ eta $b$ zenbakien multiplo komun bat dela baldin $a\mid c$ eta $b\mid c$ bada. Adibideak.

1. $40$ zenbakia $2$ eta $10$ zenbakien multiplo komun bat da; izan ere, $2\mid 40$ eta $10\mid 40$ betetzen dira.
2. $180$ zenbakia $12$ eta $18$ zenbakien multiplo komun bat da; izan ere, $12\mid 180$ eta $18\mid 180$ betetzen dira.

Definizioa. [mktdef] Izan bitez $a,b,m\in \mathbb {Z} ^{+}$, esango dugu $m$ zenbakia $a$ eta $b$ zenbakien multiplo komun txikiena dela ($m={\mbox{mkt}}(a,b)$) $a$ eta $b$ zenbakien multiplo komunen artean zenbaki oso txikiena bada; hau da,

1. $m$ zenbakia $a$ eta $b$ zenbakien multiplo komun bat da:

$a\mid m\,{\mbox{ eta }}\,b\mid m.$

1. $a$ eta $b$ zenbakien edozein multiplo komun $m$ baino handiago edo berdina da:

$(\forall c\in \mathbb {Z} ^{+})\quad a\mid c,\quad b\mid c\,\Rightarrow \,m\leq c.$

Adibideak.

1. $40$ zenbakia $2$ eta $10$ zenbakien multiplo komuna da, baina ez da ${\mbox{mkt}}(2,10)$; izan ere, $20$ ere $2$ eta $10$ zenbakien multiplo komuna da eta $20\leq 40$. Froga dezakegu ${\mbox{mkt}}(2,10)=10$ dela:
   • $2\mid 10$ $10\mid 10$.
   • $(\forall c\in \mathbb {Z} ^{+})\quad 2\mid c,\quad 10\mid c\,\Rightarrow \,10\mid c\,\Rightarrow 10\leq c$.
2. $180$ zenbakia $12$ eta $18$ zenbakien multiplo komuna da, baina ez da ${\mbox{mkt}}(12,18)$; izan ere, $72$ ere $12$ eta $18$ zenbakien multiplo komuna da eta $72\leq 180$. Froga genezake ${\mbox{mkt}}(12,18)=36$ dela.

Hurrengo teoreman frogatuko dugu $a$ eta $b$ zenbakien multiplo komun guztiak ${\mbox{mkt}}(a,b)$ zenbakiaren multiploak direla.

mkt Teorema. $a,b,m\in \mathbb {Z} ^{+}$ emanik, $m={\mbox{mkt}}(a,b)$ bada, $a$ eta $b$ zenbakien edozein multiplo komun $m$ zenbakiaren multiploa da: $(\forall c\in \mathbb {Z} ^{+})\quad a\mid c,\quad b\mid c\,\Rightarrow \,m\mid c.$

Froga.

Demagun $m={\mbox{mkt}}(a,b)$ dela; hau da, $m$ zenbakiak [mktdef] Definizioaren 1 eta 2 baldintzak betetzen ditu.

Izan bedi $c\in \mathbb {Z} ^{+}$ zenbakia $a$ eta $b$ zenbakien multiplo komun bat; beteko al da $m\mid c$?

Demagun $m\not \mid c$ betetzen dela; kontraesan bat bilatuko dugu.

$m\not \mid c$ bada, $c=qm+r$ izango da, $0<r<m$ izanik; beraz, $r=c-qm$ da; hau da, $r$ zenbakia $c$ eta $m$ zenbakien konbinazio lineala da.

Batetik $a\mid c$, bestetik $m={\mbox{mkt}}(a,b)\Rightarrow a\mid m$ ditugu; hortaz, $a\mid r$ ere beteko da.

Horrez gain, $b\mid c$ ere betetzen da, eta $m={\mbox{mkt}}(a,b)\Rightarrow b\mid m$; hortaz, $b\mid r$ ere beteko da.

Horrela, $r$ zenbakia $a$ eta $b$ zenbakien multiplo komun bat dela dugu; eta, beraz, $m\leq r$ bete beharko litzateke; baina hori $r<m$ izatearen kontra doa.

Ondorioz, $m\mid c$ dugu. $\Box$

Adibidea. ${\mbox{mkt}}(12,18)=36$ denez, $12$ eta $18$ zenbakien edozein multiplo komun $36$ zenbakiaren multiploa da. (Esaterako, $36\mid 72$). Ondoko teoreman zatitzaile komun handiena eta multiplo komun txikiena erlazionatuko ditugu.

Teorema. $a,b\in \mathbb {Z} ^{+}$ emanik,

$ab={\mbox{mkt}}(a,b){\mbox{zkh}}(a,b).$

Froga.

Izan bitez $d:={\mbox{zkh}}(a,b)$ eta $m:={\mbox{mkt}}(a,b)$. Frogatu beharko dugu $ab=md$ bela.

$d={\mbox{zkh}}(a,b)$ denez, $a=k_{1}d$ eta $b=k_{2}d$ ditugu, $k_{1},k_{2}\in \mathbb {Z}$ izanik. Gainera, $d=xa+yb$ da, $x,y\in \mathbb {Z}$ izanik.

Beste alde batetik, $m={\mbox{mkt}}(a,b)$ denez, $m=k'_{1}a$ eta $m=k'_{2}b$ ditugu, $k'_{1},k'_{2}\in \mathbb {Z}$ izanik.

• $md\mid ab$: $ab=ak_{2}d=bk_{1}d\,\Rightarrow \,{\dfrac {ab}{d}}=ak_{2}=bk_{1}\,\Rightarrow \,$ $\Rightarrow \,\left\{{\begin{array}{ll}a\mid {\dfrac {ab}{d}}\\\\b\mid {\dfrac {ab}{d}}\end{array}}\right\}\,\Rightarrow \,m\mid {\dfrac {ab}{d}}{\mbox{ (mkt Teoremaren arabera) }}\,\Rightarrow \,md\mid ab.$
• $ab\mid md$: $md=mxa+myb=k'_{2}bxa+k'_{1}ayb=(xk'_{2}+yk'_{1})ab\,\Rightarrow \,ab\mid md.$ $\left\{{\begin{array}{ll}ab\mid md\\md\mid ab\\\end{array}}\right\}\,\Rightarrow \,ab=md{\mbox{ edo }}ab=-md\,\Rightarrow \,ab=md\quad (ab,md\in \mathbb {Z} ^{+}{\mbox{ direlako)}}.$ $\Box$

$a,b\in \mathbb {Z} ^{+}$ bi zenbakiak emanik, ${\mbox{zkh}}(a,b)$ kalkula dezakegu Euklidesen algoritmoa erabiliz, eta aurreko teorema erabili ${\mbox{mkt}}(a,b)$ kalkulatzeko.

Adibideak.

1. ${\mbox{zkh}}(250,12)=2$; hortaz, ${\mbox{mkt}}(250,12)={\frac {250\cdot 12}{2}}=1500$ da.
2. ${\mbox{zkh}}(250,111)=1$; hortaz, ${\mbox{mkt}}(250,111)=250\cdot 111$ da.
3. ${\mbox{zkh}}(12,18)=6$; hortaz, ${\mbox{mkt}}(12,18)={\frac {12\cdot 18}{6}}=36$ da.

4.1.7 Aritmetikaren oinarrizko teorema

[lekon] Teoreman ikusi genuen edozein zenbaki konposatuk gutxienez zatitzaile lehen bat duela. Emaitza hura zabalduko dugu atal honetan eta beste hau frogatuko dugu: edozein $n\in \mathbb {Z} ^{+}$, $n>1$, emanik, $n$ lehena da edo $n$ zenbaki lehenen biderketa bezala idatz daiteke era bakarrean, faktoreen ordena kontuan izan gabe.

Emaitza hori frogatu baino lehen bi lema hauek frogatuko ditugu.

Lema. [pab] $a,b,p\in \mathbb {Z} ^{+}$ emanik,

$p$ lehena izanik, $p\mid ab\,\Longrightarrow \,(p\mid a)\,{\mbox{ edo }}\,(p\mid b).$

Froga.

Demagun $p\mid ab$ betetzen dela; hau da,

$ab=kp,\quad k\in \mathbb {Z} \,{\mbox{ izanik}}.$

Bietako bat betetzen dela frogatu behar dugu: $p\mid a$ edo $p\mid b$.

Horretarako, $p\not \mid a$ betetzen dela suposatuko dugu eta, orduan, $p\mid b$ betetzen dela ikusiko dugu.

Izan bedi $d:={\mbox{zkh}}(a,p)$.

$d\mid p$ denez eta $p$ lehena denez, $d=1$ edo $d=p$ ditugu. $d\mid a$ eta $p\not \mid a$ direnez, aukera bakarra $d=1$ izatea da.

Orduan, hau lortuko dugu: ${\mbox{zkh}}(a,p)=1\,\Rightarrow \,1=xa+yp,\quad x,y\in \mathbb {Z} \,{\mbox{ izanik }}\,\Rightarrow$ $\Rightarrow \,b=xab+ypb=xkp+ypb=(xk+yb)p,\quad xk+yb\in \mathbb {Z} \,{\mbox{ izanik }}\,\Rightarrow \,p\mid b.$ $\Box$

Lema. [pab2] $a_{1},\ldots ,a_{n},p\in \mathbb {Z} ^{+}$ emanik, $p$ lehena izanik,

$p\mid a_{1}\cdots a_{n}\,\Longrightarrow \,p\mid a_{j}\,j\in \{1,\cdots ,n\}{\mbox{ baterako}}.$

Froga.

Demagun $p\mid a_{1}\cdots a_{n}$ betetzen dela.

$n$-ren gaineko indukzioa erabiliz frogatuko dugu $j\in \{1,\cdots ,n\}$ baterako $p\mid a_{j}$ beteko dela.

$n=1$ denean, ez dago zer frogatu.

Demagun propietate hori betetzen dela $n=k$ denean, eta izan bedi $n=k+1$.

Orduan, $p\mid a_{1}\cdots a_{n}=a_{1}\cdots a_{k}a_{k+1}=(a_{1}\cdots a_{k})a_{k+1}.$

[pab] Lema aplikatuz, $p\mid a_{1}\cdots a_{k}$ edo $p\mid a_{k+1}$ lortuko dugu.

$p\mid a_{1}\cdots a_{k}$ betetzen bada, indukzio-hipotesiaren arabera, $p\mid a_{j}\,{\mbox{ beteko da }}\,j\in \{1,\cdots ,k\}\subset \{1,\cdots ,k+1\}=\{1,\cdots ,n\}\,{\mbox{ baterako}}.$

$p\mid a_{k+1}$ betetzen bada, $p\mid a_{j}$ betetzen da $j=k+1\in \{1,\cdots ,k+1\}=\{1,\cdots ,n\}$ kasurako. $\Box$

Adibidea. Ikus dezagun ${\sqrt {2}}$ zenbaki irrazionala dela.

Suposatuko dugu ez dela irrazionala. Orduan, ondoko hau idatzi ahal izango dugu:

${\sqrt {2}}={\dfrac {a}{b}}$, non $a,b\in \mathbb {Z}$ eta ${\mbox{zkh}}(a,b)=1$ diren.

Hortik,

${\sqrt {2}}={\dfrac {a}{b}}\,\Rightarrow \,2={\dfrac {a^{2}}{b^{2}}}\,\Rightarrow \,2b^{2}=a^{2}\,\Rightarrow \,2\mid a^{2}=a\cdot a$

atera dezakegu. [pab] Lema aplikatuz, $2\mid a$ ateratzen dugu. Eta hortik,

$2\mid a\,\Rightarrow \,a=2k,\quad k\in \mathbb {Z} \,{\mbox{ izanik }}\,\Rightarrow \,4k^{2}=a^{2}=2b^{2},\quad k\in \mathbb {Z} \,{\mbox{ izanik }}\,\Rightarrow$ $\Rightarrow \,b^{2}=2k^{2},\quad k^{2}\in \mathbb {Z} {\mbox{ izanik }}\,\Rightarrow \,2\mid b^{2}=b\cdot b.$

[pab] Lema aplikatuz, $2\mid b$ ateratzen dugu.

$2\mid a$ eta $2\mid b$ betetzen direnez, $2\mid {\mbox{zkh}}(a,b)=1$ ere beteko da; baina hori ezinezkoa da.

Teorema. Aritmetikaren oinarrizko teorema

Edozein $n\in \mathbb {Z} ^{+}$, $n>1$, emanik, $n$ lehena da edo $n$ zenbaki lehenen biderketa bezala idatz daiteke era bakarrean, faktoreen ordena kontuan izan gabe. ($n$ lehena bada, bera da faktore lehen bakarra)

Froga.

Izan bedi $S$ multzo hau:

$S:=\{n\;:\;n\in \mathbb {Z} ^{+},n>1,n{\mbox{ ezin da adierazi lehenen biderketa bezala}}\}.$

Frogatuko dugu, absurdora eramanez, $S=\emptyset$ dela. Horretarako, suposatuko dugu $S\neq \emptyset$ dela.

Ordena onaren printzipioaren arabera, $S$ multzoak elementu minimoa izango du; izan bedi $m:=\min S$. $m\in S$ denez, $m$ ez da lehena eta, hortaz, $m=m_{1}m_{2}$ izango da, $1<m_{1}<m$ eta $1<m_{2}<m$ izanik.

$m_{1}<m=\min S$ eta $m_{2}<m=\min S$ direnez, $m_{1},m_{2}\not \in S$ beteko da; beraz, badago adieraztea $m_{1}$ eta $m_{2}$ lehenen biderketa bezala; eta hori $m\in S$ hipotesiaren kontra doa.

Ondorioz, $S=\emptyset$ denez, edozein $n\in \mathbb {Z} ^{+}$, $n>1$, emanik, $n$ zenbakiaren faktorizazioa lor dezakegu zenbaki lehenekin.

Faktorizazioa bakarra dela frogatzea baino ez da geratzen. $n$-ren gaineko indukzioz frogatuko dugu.

• $n=2$ denean (lehenengo kasua), nabaria da faktorizazioa bakarra dela.

• Demagun faktorizazioa bakarra dela $n=3,\ldots ,k$ kasuetarako (indukzio-hipotesia) eta froga dezagun $n=k+1$ kasuan ere bakarra dela.

  Horretarako suposatuko dugu $k+1$ zenbakiak bi faktorizazio onartzen dituela: ${\begin{array}{l}k+1=p_{1}^{s_{1}}\cdots p_{r}^{s_{r}},p_{1}<\cdots <p_{r}\,{\mbox{ lehenak eta }}\,s_{i}>0,\,i=1,\ldots ,r,\,{\mbox{ izanik}};\\\\k+1=q_{1}^{t_{1}}\cdots q_{u}^{t_{u}},q_{1}<\cdots <q_{u}\,{\mbox{ lehenak eta }}\,t_{i}>0,\,i=1,\ldots ,u,\,{\mbox{ izanik}}.\end{array}}$
  Frogatu beharko dugu $r=u$ eta $p_{i}=q_{i}$, $s_{i}=t_{i}$ direla $i=1,\ldots ,r$ kasuetan.

$p_{1}\mid k+1=q_{1}^{t_{1}}\cdots q_{u}^{t_{u}}$ betetzen denez eta $p_{1}$ lehena denez, [pab2] Lemaren arabera, $p_{1}\mid q_{j}$ beteko da $j\in \{1,\ldots ,u\}$ baterako. $p_{1},q_{j}$ lehenak direnez eta $p_{1}\mid q_{j}$ betetzen denez, $p_{1}=q_{j}$ bete beharko da.

Ikus dezagun, absurdora eramanez, $j=1$ dela. Demagun $j\neq 1$ dela, kontraesan batera helduko gara. $j>1$ denez, $q_{1}<q_{j}$ izango da. $q_{1}\mid k+1=p_{1}^{s_{1}}\cdots p_{r}^{s_{r}}$ denez eta $q_{1}$ lehena denez, [pab2] Lemaren arabera, $q_{1}\mid p_{i}$ beteko da $i\in \{1,\ldots ,r\}$ baterako. $q_{1},p_{i}$ lehenak direnez eta $q_{1}\mid p_{i}$ denez, $q_{1}=p_{i}$ bete beharko da. Orduan, $p_{1}\leq p_{i}=q_{1}<q_{j}=p_{1}$ izango dugu, eta hori kontraesana da.

Hortaz, $j=1$ eta $p_{1}=q_{1}$ beteko dira.

Izan bedi $n_{1}:={\frac {k+1}{p_{1}}}={\frac {k+1}{q_{1}}}$. $n_{1}$ zenbakiaren bi faktorizazio dauzkagu:

${\begin{array}{lll}n_{1}=p_{1}^{s_{1}-1}\cdots p_{r}^{s_{r}},\\n_{1}=q_{1}^{t_{1}-1}\cdots q_{u}^{t_{u}}.\end{array}}$

Eta, $n_{1}<k+1$ denez, indukzio-hipotesiaren arabera, $r=u$, $p_{i}=q_{i}$, $i=1,\ldots ,r$ guztietarako, $s_{1}-1=t_{1}-1$ (hots, $s_{1}=t_{1}$) eta $s_{i}=t_{i}$ $i=2,\ldots ,r$ guztietarako. $\Box$

Adibidea. Kalkula dezagun $6552$ zenbakiaren faktorizazioa zenbaki lehenekin:

• $2\mid 6552$: $6552=2\cdot 3276.$
• $2\mid 3276$: $3276=2\cdot 1638\,\Rightarrow \,6552=2^{2}\cdot 1638.$
• $2\mid 1638$: $1638=2\cdot 819\,\Rightarrow \,6552=2^{3}\cdot 819.$
• $2\not \mid 819$; $3\mid 819$: $819=3\cdot 273\,\Rightarrow \,6552=2^{3}\cdot 3\cdot 273.$
• $3\mid 273$: $273=3\cdot 91\,\Rightarrow \,6552=2^{3}\cdot 3^{2}\cdot 91.$
• $3\not \mid 91$; $5\not \mid 91$; $7\mid 91$: $91=7\cdot 13\,\Rightarrow \,6552=2^{3}\cdot 3^{2}\cdot 7\cdot 13.$
• $13$ lehena da; beraz, bukatu dugu.

${\begin{array}{r|l}6552&2\\3276&2\\1638&2\\819&3\\273&3\\91&7\\13\end{array}}$ $6552=2^{3}\cdot 3^{2}\cdot 7\cdot 13.$

4.2 Aritmetika modularra

Atal honetan, zenbaki osoak $n$ zenbakiaz zatiketa euklidearraren arabera zatitzean lortuko den hondarrarekin erlazionatuko ditugu, eta hondar bereko elementuen multzoak hartuko ditugu kontuan. Horrez gain, multzo ezberdinetako elementuen arteko eragiketa aritmetikoak aztertuko ditugu.

4.2.1 n moduluko kongruentzia

Definizioa.

$n\in \mathbb {Z}$, $n>1$ izanik, $a,b\in \mathbb {Z}$ kongruenteak modulu $n$ dira, eta adieraziko dugu $a\equiv b\;{\mbox{mod }}n$, baldin $n\mid (a-b)$, hau da, $\exists k\in \mathbb {Z} \;\ /\ \;(a-b)=kn$, edo beste era batera esanda, $a-b$ zenbakia $n$ren multiploa da.

Definizioa ondo ulertzeko komeni da zatiketa euklidearra eta Euklidesen teorema kontuan izatea:

Hau da, $b,n\in \mathbb {Z}$ emanik, non $n>0$ den, orduan $\exists \mid q\in \mathbb {Z}$ eta $\exists \mid r\in \mathbb {Z}$ non $0\leq r<n$ den eta $b=qn+r$ den. $r$ hondarra da eta hondar posibleak $0,1,\dots ,n-1$ dira.

${\begin{array}{rl}b&{\underline {\vline n}}\\r&q\\\end{array}}\quad \quad b=qn+r,\quad 0\leq r<n.$

Euklidesen teorema eta kongruentziaren definizioa kontutan izanik, $a\equiv b\;{\mbox{mod }}n$ bada, hau da, $(a-b)=kn$ bada, orduan $a$ eta $b$ zenbakiek hondar bera izango dute $n$ zenbakiaz zatitzean, izan ere, $b$ zenbakiaren hondarra $r$ bada, orduan, $b=qn+r$ izango da; bestalde $(a-b)=kn$ denez, eta $a=b+(a-b)$ denez, $a=qn+r+kn$ izango da, ondorioz, $a=(q+k)n+r$ dela esan dezakegu, beraz, $a$ zenbakia $n$ zenbakiaz zatitzean hondarra $r$ izango da, alegia,$b$ zenbakiaren hondar bera:

${\begin{array}{rl}a&{\underline {\vline n}}\\r&q+k\\\end{array}}\quad \quad a=(q+k)n+r,\quad 0\leq r<n.$

Hondarren multzoa

$n$ moduluko kongruentzian, hondar posibleak $0,1,\dots ,n-1$ direnez, $n$ moduluko hondarren multzoa: $\mathbb {Z} _{n}=\{0,1,...,n-1\}$ da.

Multzo horretan $n$ elementu besterik ez daude, eta $\mathbb {Z}$ multzoko elementu oro $\mathbb {Z} _{n}$ multzoko elementu bakarrarekin erlazionatuta dago (baliokidetza erlazioa da $n$ moduluko kongruentzia). Hau da, $\mathbb {Z}$ multzoari $n$ klase dituen partiketa eragiten dio erlazio honek.

4.2.2 Batuketa eta Biderketa modularrak

Batuketa eta biderketa

$\mathbb {Z} _{n}$ multzoan batuketa eta biderketa modularra horrela egiten dira:

$((a{\mbox{ mod }}n)+(b{\mbox{ mod }}n)){\mbox{ mod }}n=(a+b){\mbox{ mod }}n$

$((a{\mbox{ mod }}n)\cdot (b{\mbox{ mod }}n)){\mbox{ mod }}n=(a\cdot b){\mbox{ mod }}n$

4.2.3 Alderantzizko modularra

Zatiketa

Zatiketa ez dago elementu guztietarako definituta, eta badagoenean alderantzizko modularraz biderkatuz kalkulatu ohi da.

• $\mathbb {Z}$ multzoko elementu guztiek ez dute alderantzizkorik, ez eta $\mathbb {Z} _{n}$ multzoko guztiek alderantzizko modularrik ere.
• $a$ elementua alderantzikagarria izateko $a\cdot a^{-1}=1$ beteko duen $a^{-1}$ existitu behar da multzoan.

Teorema [Alderantzizko modularraren existentzia]

$a^{-1}{\mbox{ mod }}n$ existitzen da baldin eta soilik baldin zkh$(a,n)=1$. $\mathbb {Z} _{n}$ multzoan alderantzikagarri diren elementuen multzoa $\mathbb {Z} _{n}^{*}$ da.

n moduluko hondarren multzo murriztua:

$\mathbb {Z} _{n}^{*}=\{a\in \mathbb {Z} _{n}\,:\,{\mbox{zkh}}(a,n)=1\}$.

Alderantzizko modularra existitzen denean, $a^{-1}{\mbox{ mod }}n$ kalkulatzeko Euklidesen algoritmoa erabiliko dugu.

Alderantzizko modularraren kalkulua

Euklidesen algoritmoa erabiliz

Izan bitez $a,n\in \mathbb {Z}$ lehen erlatiboak, zkh$(a,n)=1$.

Dakigunez, $\exists x,y\in \mathbb {Z} \,{\mbox{ non }}\,xa+yn={\mbox{zkh}}(a,n)$.

Hortaz, ${\mbox{zkh}}(a,n)=1\Leftrightarrow \exists x,y\in \mathbb {Z} {\mbox{ non }}ax+ny=1.$ $a$-ren alderantzizko modularra $x$ dela ondoriozta daiteke horrela: $ax+ny=1\Rightarrow ax=1+(-y)n\Rightarrow ax\equiv 1{\mbox{ mod }}n$ $\Rightarrow a^{-1}\equiv x{\mbox{ mod }}n.$

Euklidesen algoritmoa erabiliz $x$ kalkulatuko dugu, hau da, $a^{-1}$.

4.2.4 Euler-Fermat teoremak

Definizioa Euler-en funtzioa, $\phi (n)$

Eulerren funtzioa, $\phi (n)$, n moduluko hondarren multzo murriztuak duen elementu kopurua da, hau da, $\mathbb {Z} _{n}^{*}$ multzoaren kardinala.

Teorema $\phi (n)$ren kalkulurako

Izan bitez $p,q,n\in \mathbb {Z}$.

• $n$ zenbakia lehena bada, orduan $\phi (n)=n-1$.
• $n=pq$ bada, $p$ eta $q$ bi zenbaki lehen desberdinak izanik, orduan $\phi (n)=(p-1)(q-1)$.
• $n=p_{1}^{e_{1}}\cdots p_{r}^{e_{r}}$ moduan idatz daiteke, $p_{1},\ldots ,p_{r}$ lehen desberdinak izanik. $\phi (n)={\frac {n}{p_{1}\dots p_{r}}}(p_{1}-1)\dots (p_{r}-1)$.

Teorema [Euler-en teorema]

Izan bitez $a,n\in \mathbb {Z} ^{+}$ zenbaki lehen erlatiboak, zkh$(a,n)=1$. Zera betetzen da: $a^{\phi (n)}\equiv 1{\mbox{ mod }}n$

Euler-Fermat teoremak

$n$ zenbaki lehena izanik $\phi (n)=n-1$ denez, Euler-en teorema honela geratzen da.

Teorema [Fermat-en teorema txikia]

Izan bedi $n\in \mathbb {Z} ^{+}$ lehena. $a\in \mathbb {Z} ^{+}$ izanik, $a^{n-1}\equiv 1{\mbox{ mod }}n$

Oharrak:

1. Euler-Fermat teoremak erabiliz, berreketa modularra kalkulatzea posible bada ere, gehienetan ez da praktikoa.
   • $\phi (n)$ kalkulatzea ez da beti erraza gertatzen, $n$ oso handia denean zenbaki lehenetan faktorizatzea ez da erraza...
   • Teoremei esker zenbait kasutan berreketa modularraren kalkulua asko laburtzea lortzen da, baina ez beti...
2. Kriptografian, gako publikoko zifratze-algoritmoetan, oso garrantzitsuak gertatzen dira Euler-Fermat teoremak

4.2.5 Berreketa modularra

$a,x\in \mathbb {Z}$, $x\geq 0$ izanik, $a^{x}$ berreketa biderketen bidez kalkulatzean, $x$ berretzailea handia denean bi arazo mota sortzen dira:

• $a^{x}$ handiegia da. Kalkulatu nahi izateak arazoak sor ditzake!
• $a$ zenbakia bere buruarekin $x-1$ aldiz biderkatu behar da. Biderketa kopuru handia!

Aritmetika modularrean, $a^{x}{\mbox{ mod }}n$ kalkulatzean:

• Zenbaki handiegien arazoa ekiditen da, ez dago $a^{x}$ kalkulatu beharrik, horrela eragiten delako. $((a{\mbox{ mod }}n)\cdot (b{\mbox{ mod }}n)){\mbox{ mod }}n=(a\cdot b){\mbox{ mod }}n$
• Berreketa bitarraren metodoa. $x$ berretzailearen adierazpen bitarra erabiliz biderketa kopuru minimoa kalkulatuko da.

Berreketa bitarraren metodoa

• Berreketa handiak modu eraginkorrean kalkulatzeko metodoa.
• $x$ren adierazpen bitarra erabiltzen da.
• $a^{x}$ berreketa kalkulatzeko algoritmo errekurtsiboa: $$a^{x}=\left\{{\begin{array}{ll}a&{\mbox{ }}x=1{\mbox{ bada}}\\(a^{\frac {x}{2}})^{2}&{\mbox{ }}x{\mbox{ bikoitia bada}}\\aa^{x-1}&{\mbox{ }}x{\mbox{ bakoitia bada}}\end{array}}\right.$$

Berreketaren honako hiru propietateetan oinarritzen da:

1. $a^{1}=a,$
2. $a^{x+y}=a^{x}a^{y},$
3. $a^{xy}=(a^{x})^{y}$

4.3 RSA algoritmoa

Mezuak zifratzeko erabiltzen den sistema da RSA algoritmoa eta aritmetika modularraren aplikaziotzat har daiteke.

Zenbaki handien faktorizazioa lan nekeza da, hau da, zenbaki handi baten zatitzaile diren zenbaki lehenak zein diren ezagutzeko, ez dago algoritmo azkarrik; ondorioz, lehenak diren zenbakiak banan banan hartu eta zenbaki handiaren zatitzaile diren ala ez begiratzea beste erremediorik ez dago. RSA algoritmoaren segurtasuna horretantxe oinarritzen da: zenbaki oso handia aukeratzen du algoritmoak, eta bere zatitzaile lehenenetatik eratorritako aritmetika modularreko eragiketak baliatzen ditu mezuak zifratzeko.

4.3.1 RSA algoritmoaren jatorria

1977. urtean, Ronald Rivest, Adi Shamir eta Leonard Adleman-ek sortutako kriptografia-sistema da RSA. Zenbaki handien faktorizazioa eragiketa motela den heinean, kriptografia-sistema segurua da eta, lehen esan bezala, Zenbaki-Teorian eta Aritmetika Modularrean oinarritzen da. Terminologia aldetik esan behar da enkriptatzea eta zifratzea sinonimotzat erabili ohi direla. Mezu zifratua (enkriptatua) mezua jaso behar duenak bakarrik ulertuko du, eta ulertezina izango da gainerakoentzat. Gakoetan oinarritutako zifratze sistema da, eta bi gako ezberdin erabiltzen ditu. Bata publikoa da eta zifratzeko erabiltzen da; bestea, ordea, sekretua da, eta deszifratzeko beharrezkoa da. Beraz, sistema asimetrikoa da.

Mezua jaso behar duenak sortu behar ditu gakoak eta publikatu egin behar du gako publikoa; pribatua, ordea, ezkutuan jasoko du. Horrela, berari mezua bidali nahi dionak, publikoa den gako horixe erabiliko du mezua zifratzeko. Deszifratzeko, ezkutuan jaso duen gako pribatua behar da. Gakoaren sortzailea denez gakoa ezagutzen duen bakarra, bera izango da mezua deszifratzeko gai izango den bakarra. Hartzailearen gakoak dira, beraz, prozesuan erabiliko diren gakoak.

4.3.2 RSA algoritmoaren oinarri teorikoak

Zifratze-deszifratze prozesuaren oinarrian Euler-Fermat-en teorema dagoela esan dezakegu, bai eta Eulerren $\phi (n)$ funtzioaren propietate bat ere. Horrez gain, zenbaki baten alderantziko modularraren adierazpena ere kontuan izan behar da eta, sistema eraginkorra izan dadin, berreketa modularra era eraginkorrean programatzea komeni da.

Teorema. Izan bedi $n=p\ q,$ non $p$ eta $q$ zenbaki lehenak diren, eta izan bitez $r\equiv s^{-1}{\mbox{mod }}{\phi (n)}$ eta $a<\min(p,q)$, non $\phi (n)=(p-1)(q-1)$ Eulerren funtzioa den; orduan $a^{r*s}{\mbox{mod }}n\equiv a$ beteko da.

Froga.

Teoreman zehaztu da $n$ zenbakia $p$ eta $q$ bi zenbaki lehenen biderketa dela; beraz, badakigu $\phi (n)=(p-1)(q-1)$ dela. Bestalde, $r=s^{-1}{\mbox{mod }}{\phi (n)}$ denez, alderantzizko modularraren definizioaren arabera, $r\ s{\mbox{ mod }}{\phi (n)}=1$ izango da, eta ondorioz, badakigu badagoela $k\in \mathbb {Z}$ zeinarentzat $r\ s=1+k\ \phi (n)$ beteko den, eta beraz, $a^{r\ s}=a^{1+k\ \phi (n)}$ beteko da. Berdintza horretako bi aldeeetan $n$ modulua kalkulatzen badugu: $$a^{r\ s}{\mbox{mod }}n=a^{1+k\ \phi (n)}{\mbox{mod }}n=a\ (a^{\phi (n)})^{k}{\mbox{mod }}n.$$ Badakigu, ordea, Euler-Fermaten teoremaren arabera, $a$ eta $n$ zenbakiak elkarrekiko lehenak edo lehen erlatiboak badira, orduan, $a^{\phi (n)}{\mbox{mod }}n\equiv 1$ dela. Kontuan izan behar da, $a<\min(p,q)$ dela eta $n$ zenbakiaren zatitzaile bakarrak $p$ eta $q$ direla, beraz, esan dezakegu ez dagoela zatitzaile komunik $a$ eta $n$ zenbakien artean, hau da, elkarrekiko lehenak dira; ondorioz, Euler-Fermaten teorema aplikatuz iritsiko gara bila genbiltzan berdintzara: $a^{r\ s}{\mbox{mod }}n\equiv a$.

Teorema horretan oinarritzen da RSA algoritmoa: $a$ mezua bidali beharrean $z=a^{r}{\mbox{mod }}_{n}$ mezu zifratua bidaltzea proposatzen du algoritmoak, eta hori deszifratzeko $z^{s}{\mbox{mod }}_{n}$ kalkulatzea nahikoa da, bai baitakigu $z^{s}{\mbox{mod }}_{n}=a^{r*s}{\mbox{mod }}_{n}=a$ dela.

4.3.3 Gako publikoa eta gako pribatua

Demagun $a$ kodeak adierazten duela zifratu nahi dugun mezua. RSA algoritmoaren oinarriak kontuan hartuz, berreketa modularra erabiliz, $$z\equiv a^{r}{\mbox{mod }}n$$ kalkulatu beharko luke mezua bidali nahi duenak. Beraz, $(n,r)$ zenbakiek ezagunak izan behar dute. Hain zuzen ere gako publikoak bi zenbaki horiexek dira.

Mezua deszifratzeko $z^{s}{\mbox{mod }}n$ kalkulatu beharko du mezua jaso duenak. Izan ere, badakigu Euler-Fermaten teoremaren eta alderantzizko modularraren definizioaren ondorioz, $$z^{s}{\mbox{mod }}n\equiv (a^{r})^{s}{\mbox{mod }}n=a^{1+k*\phi (n)}{\mbox{mod }}n\equiv a$$ dela, non $k\in \mathbb {Z}$ baita. Beraz, mezu zifratua deszifratzeko behar den informazioa $(n,s)$ zenbakiek osatzen dute; gako pribatua horixe da, hain zuzen ere.

Gako publikoa ezagutzera ematen bada, alegia $(n,r)$ zenbakiak publikoak badira, $n$ zenbakiaren deskonposaketa eginez $p$ eta $q$ zenbakiak ezagutu daitezke, eta ondorioz $\phi (n)=(p-1)(q-1)$ ere ezagutzea lortuko genuke. Hori guztia ezagutuz, deszifratzeko falta zaigun bakarra $s$ zenbakia da, eta $r\equiv s^{-1}{\mbox{mod }}\phi (n)$ denez, hori ere ezagutzea lortuko genuke. Hau da, gako publikoa ezagutzera emanaz gako pribatua ezagutzeko bidea ematen da.

Nola esango dugu, bada, mezua sekretua dela? Sekretu izaera $s$ zenbaki sekretua kalkulatzeko behar den denborak ematen dio: lehen esan bezala, $n$ zenbakia oso handia bada, bere faktorizazioa egiteak eskatzen duen denbora ikaragarria da. Alegia, gako publikoak argitaratu arren, bere faktorizazioa egin beharko litzateke eta horrek denbora gehiegi behar du. Ondorioz, $p,$ $q$ eta $\phi (n)$ ezezagunak izango dira, eta ezin izango da $s$ kalkulatu.

Esandakoaren arabera, $n$ zenbakia ezagutu arren, $p$ eta $q$ ezkutuan geratzen dira, bai eta $\phi (n)$ ere; ondorioz, $r$ ezagutzera eman arren, $s$ ezkutuan gordetzen da; izan ere $s$ ezagutzeko, $r$-ren alderantzizkoa kalkulatu beharko genuke $Z_{\phi (n)}$ multzoan, baina multzo hori ezkutuan geratu da.

4.3.4 Gako publikoak eta pribatuak sortzeko prozesua

Adierazi dugun bezala, $r\equiv s^{-1}{\mbox{mod }}{\phi (n)}$ bete behar da, horrek ziurtatzen baitu $r\ s=1+k\ \phi (n)$, non $k\in \mathbb {Z}$ baita.

Gako publikoa $(n,r)$ zenbakiek osatzen dute. Hortaz, $n$ zenbakia zehaztu eta ezagutzera eman behar da. Baina $\phi (n)$ ezezaguna izan dadin, aukeratu behar den $n$ zenbakiak oso handia izan behar du, bestela, bere faktorizazioa denbora onargarrian egin ahal izango litzateke eta ondorioz $\phi (n)$ kalkulatu ahal izango litzateke.

Hori gerta ez dadin, $n=p\ q$ oso handia aukeratu behar da, hau da, bai $p$ eta bai $q$ zenbaki lehenak izateaz gain, zenbaki oso handiak aukeratu behar dira. Horrela, $\phi (n)=(p-1)(q-1)$ ezin izango da denbora laburrean kalkulatu. Kontuan izan behar da faktorizazioa beti egin daitekeela, alegia, $n$ ezaguna bada, faktorizazioa egin daiteke, baina handia den heinean, faktorizazio horrek denbora luzea hartuko du.

Beraz, $n$ zenbakia zehazteko, $p,q$ zenbaki lehenak aukeratu behar izan ditugu, eta bi zenbaki horiexek zehazten dute $\phi (n)$ zenbakia, bai eta $\mathbb {Z} _{\phi (n)}$ multzoa ere.

Orain $r$ eta $s$ zenbakiak aukeratu behar dira. Bete behar duten baldintza da $r\ s{\mbox{ mod }}\phi (n)\equiv 1$. Eta horretarako, $s$ eta $\phi (n)$ zenbakiek elkarren artean lehen erlatiboak izan behar dute, alegia, ${\mbox{zkh}}(\phi (n),s)=1$ bete behar da. Euklidesen algoritmoa erabil daiteke hala dela ziurtatzeko eta, era berean, algoritmo horrek berak bidea emango digu 1 zenbakia $s$ eta $\phi (n)$ zenbakien konbinazio lineal bezala adierazteko: $$1=r\ s+k\ \phi (n).$$ Horrela, $s^{-1}\equiv r{\mbox{ mod}}{\phi (n)}$ ere kalkulatu ahal izango dugu.

Laburbilduz, prozesuak urrats hauek ditu:

1. Aukeratu $p,q$ zenbaki lehenak eta oso handiak
2. Aukeratu $\phi (n)=(p-1)(q-1)$ zenbakiarekiko lehena izango den $s$ zenbakia.
3. Kalkulatu $r=s^{-1}{\mbox{mod }}{\phi (n)}$ zenbakia.
4. Publikatu $(n,r)$ gako publikoak eta ezkutuan ondo jaso $(n,s)$ gako pribatuak.

4.3.5 Mezu zifratua bidaltzeko prozesua

Norbaiti, demagun Jasoneri, RSA algoritmoa erabiliz mezu zifratua bidali nahi badiogu, Jasonek bere RSA gakoak aukeratuta izan behar ditu, eta gako publikoak ezagutzera emanda izan behar ditu. Jasonek lan hori egina baldin badauka, bere $(n,r)$ gako publikoak ezagunak izango dira, eta ondorioz, guk gure mezua Jasonek deszifratzeko moduan zifratu ahal izango dugu.

Guk mezuari dagokion kodea zifratu behar dugu, hau da, gure mezuari dagokion kodea $a$ baldin bada, $$z=a^{r}{\mbox{mod }}n$$ kalkulatu behar dugu eta Jasoneri $z$ bidaliko diogu.

Jasonek, beraz, $z$ mezua jasoko du, eta mezua deszifratzeko $$z^{s}{\mbox{mod }}n$$ kalkulatu beharko du. Baina badakigu eragiketa horren emaitza $a$ dela. Hau da, gure mezuari dagokion kodea kalkulatuko du Jasonek.

4.3.6 Mezu ziurtatua bidaltzeko prozesua

Gako publikoak eta pribatuak beste erabilera bat ere badute: mezu ziurtatua bidaltzeko aukera ere ematen dute. Alegia mezua bidali duena nor izan den ziurtatzeko aukera ematen dute.

Horretarako, Jasonek mezua bere gako pribatuarekin zifratu behar du, eta guk, bere gako publikoarekin deszifratu behar dugu: Jasonek $a$ mezua bere gako pribatuarekin zifratuta $$z=a^{s}{\mbox{mod }}n$$ lortuko du $z$ mezu ziurtatua, eta hori bidaliko baligu, guk $$a=z^{r}{\mbox{mod }}n$$ kalkulatu beharko genuke, eta horrela lortutako $a$ mezuak zentzurik balu, esan ahal izango genuke Jasonek sortutako mezua dela.