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