Matematika Diskretua/Zenbaki teoria

4. Gaia: Zenbaki-teoria

4.1 Zenbaki osoak

4.1.1 Eragiketak zenbaki osoen artean. Ordena onaren printzipioa

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

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

• ${\textstyle \mathbb {Z} }$ multzoa itxia da ${\textstyle (+)}$ batuketarako, ${\textstyle (\cdot )}$ biderketarako eta ${\textstyle (-)}$ kenketarako: $$x,y\in \mathbb {Z} \implies 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 euklidearra, 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 3.3.2 Atalean definitu ditugun propietateak betetzen dituelako:

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

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

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

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

  ${\textstyle \leq }$ ordena-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, 4ak 12a zehazki zatitzen du ($12=3\cdot 4$). Hau da, 12 zati 4 egitean, zatidura gisa 3 eta hondar gisa 0 zenbaki osoak lortuko ditugu.

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

Hitzarmena. ${\textstyle a\mid b}$ idazten dugunean, ${\textstyle a\neq 0}$ dela pentsatuko dugu.

4.2 Lema. ${\textstyle a,b\in \mathbb {Z} ^{+}}$ bada, $a\mid b\implies a\leq b$.

Ondoko teoreman zatigarritasunaren propietate batzuk frogatuko ditugu.

4.3 Teorema. ${\textstyle a,b,c\in \mathbb {Z} }$ izanik,

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)\implies a=b\;\vee \;a=-b}$. (${\textstyle a\neq 0,b\neq 0}$)
3. ${\textstyle (a\mid b)\;\wedge \;(b\mid c)\implies a\mid c}$. (${\textstyle a\neq 0,b\neq 0}$)
4. ${\textstyle a\mid b\implies (\forall x\in \mathbb {Z} )\;\;a\mid xb}$. (${\textstyle a\neq 0}$)
5. ${\textstyle (a\mid b)\wedge (a\mid c)\implies (\forall x,y\in \mathbb {Z} )\;\;a\mid xb+yc}$. (${\textstyle a\neq 0}$)

Froga.

1. ${\textstyle a=1a.}$ da; beraz, ${\textstyle 1\mid a}$ eta ${\textstyle a\mid a}$. Bestalde, ${\textstyle 0=0a.}$ da; beraz, ${\textstyle a\mid 0}$.
2. Hasteko, ${\textstyle (a\mid b)\;\wedge \;(b\mid a)}$ daukagu, hau da, $$\left.{\begin{array}{c}a\mid b\\\wedge \\b\mid a\end{array}}\right\}\implies \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\}\implies b=k_{1}(k_{2}b)=(k_{1}k_{2})b,$$$$k_{1},k_{2}\in \mathbb {Z} {\mbox{ izanik}}\implies k_{1}k_{2}=1,\;k_{1},k_{2}\in \mathbb {Z} {\mbox{ izanik}}\implies \left.{\begin{array}{c}k_{1}=k_{2}=1\\\vee \\k_{1}=k_{2}=-1\end{array}}\right\}\implies \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\}\implies \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\}\implies c=k_{2}(k_{1}a)=(k_{2}k_{1})a,$$ ${\textstyle k_{2}k_{1}\in \mathbb {Z} {\mbox{ izanik }}\implies a\mid c}$.
4. Edozein ${\textstyle x\in \mathbb {Z} }$ izanik, $$a\mid b\implies b=ka,\;k\in \mathbb {Z} {\mbox{ izanik}}\implies xb=x(ka)=(xk)a,\;xk\in \mathbb {Z} {\mbox{ izanik}}\implies a\mid xb.$$
5. Edozein ${\textstyle x,y\in \mathbb {Z} }$ izanik, $$\left.{\begin{array}{c}a\mid b\\\wedge \\a\mid c\end{array}}\right\}\implies \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\}\implies xb+yc=x(k_{1}a)+y(k_{2}a)=$$ $$=(xk_{1}+yk_{2})a,\;xk_{1}+yk_{2}\in \mathbb {Z} {\mbox{ izanik }}\implies a\mid xb+yc.$$ $\square$ $\blacksquare$ $\square$

Oharrak.

1. ${\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, 4.3-5 Teoremaren arabera, ${\textstyle a}$ zenbakiak ${\textstyle b}$ eta ${\textstyle c}$ zenbakien edozein konbinazio lineal zatituko du.

2. Propietate hori honela zabal daiteke: ${\textstyle b_{1},\ldots ,b_{n}\in \mathbb {Z} }$ izanik, $$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,\ldots ,n\implies (\forall x_{1},\ldots ,x_{n}\in \mathbb {Z} )\quad a\mid x_{1}b_{1}+\cdots +x_{n}b_{n}.$$

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

Demagun ${\textstyle x,y,z}$ zenbaki oso horiek existitzen direla. ${\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.

4.5 Definizioa. Izan bedi ${\textstyle n\in \mathbb {Z} ^{+}}$, ${\textstyle n>1}$.

${\textstyle n}$ zenbaki lehena dela esango dugu bere zatitzaile positibo bakarrak ${\textstyle n}$ eta ${\textstyle 1}$ badira: $$m\mid n,\quad m\in \mathbb {Z} ^{+}\implies m=1\,\vee \,m=n.$$ Eta ${\textstyle n}$ zenbaki konposatua dela esango dugu ez bada lehena: $$\exists m_{1},m_{2}\in \mathbb {Z} ^{+},\;{\mbox{ non }}\;n=m_{1}m_{2}\;{\mbox{ den, }}\,\quad 1<m_{1}<n,\;1<m_{2}<n.$$

4.6 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.

4.7 Teorema. Zenbaki konposatu orok zatitzaile lehenen bat dauka. Hau da, ${\textstyle n\in \mathbb {Z} ^{+}}$, ${\textstyle n>1}$ izanik, $$n\,{\mbox{ konposatua }}\implies \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}}\}.$$ Absurdora eramanez, ${\textstyle S=\emptyset }$ dela frogatuko dugu.

Demagun ${\textstyle S\neq \emptyset }$ dela. ${\textstyle S}$ multzoa ${\textstyle \mathbb {Z} ^{+}}$ multzoaren azpimultzo ez-hutsa denez, ordena onaren printzipioaren arabera, ${\textstyle S}$ multzoak elementu minimoa 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. Beraz, ${\textstyle S=\emptyset }$ da; eta, ondorioz, zenbaki konposatu orok zatitzaile lehenen bat dauka. $\square$ $\blacksquare$ $\square$

4.8 Teorema. (Euklides, Elementuak, IX, 20)

Infinitu zenbaki lehen daude.

Froga.

Absurdora eramanez frogatuko dugu.

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

Izan bitez ${\textstyle a=p_{1}\cdots p_{k}}$, zenbaki lehenen biderkadura, eta ${\textstyle b=a+1}$.

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

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

Hortaz, zenbaki lehenen kopuruak ezin du kopuru finitua izan. Hau da, infinitu zenbaki lehen daude. $\square$ $\blacksquare$ $\square$

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 izanik, ${\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, ${\textstyle 38-x\cdot 7}$ ahalik eta txikiena, baina positiboa, egiten duen ${\textstyle x}$ zenbakia izango da zatidura. Bestela esanda, $\{x\in \mathbb {Z} \;/\;38-x\cdot 7>0\}$ 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:

4.9 Teorema. Zatiketa euklidearra

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

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

Froga.

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

Bi kasu bereiziko ditugu: ${\textstyle b\mid a}$ eta ${\textstyle b\not |\;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 |\;a}$.

   Izan bedi ${\textstyle S=\{a-xb\;/\;x\in \mathbb {Z} {\mbox{ eta }}a-xb>0\}}$ hondar positiboen 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\implies b\geq 1\implies 1-b\leq 0\implies (1-b)a\geq 0\implies (1-b)a+b\geq b>0\implies$$ $$\implies a-tb>0\implies 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\implies r=a-qb>0,q\in \mathbb {Z} {\mbox{ izanik}}\implies 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, hartu dugun ${\textstyle b\not |\;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\implies c=a-(q+1)b>0\implies c\in S.$$ $r=\min S$ denez, $c\geq r$ da; $c=r-b$ denez, $r-b\geq r\implies b\leq 0$ lortuko dugu; eta hori ezinezkoa da ${\textstyle b>0}$ delako.

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

Demagun ez direla bakarrak, hau da, $$\exists q_{1},q_{2},r_{1},r_{2}\in \mathbb {Z} ,\;{\mbox{ non }}\;a=q_{1}b+r_{1}\;{\mbox{ eta }}\;a=q_{2}b+r_{2}\,{\mbox{ den}},$$ ${\textstyle 0\leq r_{1}<b}$ eta ${\textstyle 0\leq r_{2}<b}$ izanik. Orduan, $$q_{1}b+r_{1}=q_{2}b+r_{2}\implies (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 pentsatuko 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, arrazoibide 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. $\square$ $\blacksquare$ $\square$

4.10 Adibidea. Adibide hauetan ematen diren zatidurak eta hondarrak existitzen dira eta bakarrak dira.

$${\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

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

4.12 Adibidea. ${\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. Bien zatitzaile positibo komunak ${\textstyle 1}$, ${\textstyle 2}$, ${\textstyle 4}$ eta ${\textstyle 8}$ dira.

4.13 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} ^{+}}$. ${\textstyle d}$ zenbakia ${\textstyle a}$ eta ${\textstyle b}$ zenbakien zatitzaile komun handienetako bat dela esango dugu 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\implies c\mid d.$$

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

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

Azkenekoari erantzuteko hona hemen teorema hau.

4.15 Teorema. Zatitzaile komun handienaren bakartasuna

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

Froga.

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

${\textstyle d_{1}}$ ${\textstyle a}$ eta ${\textstyle b}$ zenbakien zatitzaile komuna da; beraz, ${\textstyle d_{1}\mid a}$ eta ${\textstyle d_{1}\mid b}$; hortaz, ${\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\}\implies 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}}$ izatea da. $\square$ $\blacksquare$ $\square$

Idazkera. $a,b\in \mathbb {Z}$ izanik, $a$ eta $b$ zenbakien zatitzaile komun handiena badago, ${\mbox{zkh}}(a,b)$ adieraziko dugu.

Hitzarmena. ${\mbox{zkh}}(0,0)$ ez dago definiturik.

4.16 Propietateak.

1. ${\mbox{zkh}}(a,b)$ badago, ${\mbox{zkh}}(b,a)={\mbox{zkh}}(a,b)$ beteko da.
2. ${\textstyle a\in \mathbb {Z} ^{*}}$ bada, ${\textstyle {\mbox{zkh}}(a,0)}$ badagoela eta ${\textstyle {\mbox{zkh}}(a,0)=\mid a\mid }$ betetzen dela froga daiteke.
   • ${\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 \implies \;\mid a\mid {\big |}\;a$$
   $$\mid a\mid \;{\big |}\;0{\mbox{ (edozein zenbaki oso da 0 zenbakiaren zatitzailea).}}$$
   • ${\textstyle \mid a\mid }$ zenbakia ${\textstyle a}$ eta ${\textstyle 0}$ zenbakien zatitzaile komun handiena da: ${\textstyle c\in \mathbb {Z} ^{+}}$ izanik,
   $$\left.{\begin{array}{ll}c\mid a\\c\mid 0\\\end{array}}\right\}\implies c\mid a\implies c\;{\big |}\;\mid a\mid {\mbox{ (}}\mid a\mid =a{\mbox{ edo }}\mid a\mid =-a{\mbox{ delako).}}$$ $\square$ $\blacksquare$ $\square$

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 pentsatuko dugu.

4.17 Teorema. Zatitzaile komun handienaren existentzia

${\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:

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

   • Demagun ${\textstyle d\not |\,a}$ dela, eta kontraesan bat aurkituko dugu:

     ${\textstyle d\not |\,a}$ bada, ${\textstyle a}$ zati ${\textstyle d}$ zatiketa euklidearra 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.

2. ${\textstyle d}$ zenbakia ${\textstyle a}$ eta ${\textstyle b}$ zenbakien zatitzaile komun handiena da: ${\textstyle c\in \mathbb {Z} ^{+}}$ beste zatitzaile komun bat izanik, $$\left.{\begin{array}{ll}c\mid a\\c\mid b\\\end{array}}\right\}\implies c\mid xa+yb=d\implies c\leq d,$$ zenbaki oso batek bi zenbaki zatitzen baditu, horien edozein konbinazio lineal zatituko duelako. $\square$ $\blacksquare$ $\square$

Oharra. Aurreko teoreman, $a,b\in \mathbb {Z} ^{+}$ zenbakietarako ${\mbox{zkh}}(a,b)$ existitzen dela frogatu dugu. Orain, ${\textstyle a,b\in \mathbb {Z} }$ izanik, ${\textstyle {\mbox{zkh}}(a,b)}$ beti existitzen dela froga dezakegu (${\textstyle a=b=0}$ denean izan ezik).

${\textstyle {\mbox{zkh}}(\mid a\mid ,\mid b\mid )}$ existitzen dela jadanik frogatu dugu. Orain, ${\mbox{zkh}}(a,b)={\mbox{zkh}}(\mid a\mid ,\mid b\mid )$ betetzen dela frogatzea baino ez zaigu geratzen.

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

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

• ${\textstyle d}$ zenbakia ${\textstyle a}$ eta ${\textstyle b}$ zenbakien zatitzaile komun handiena da: ${\textstyle c\in \mathbb {Z} ^{+}}$ beste zatitzaile komun bat izanik,

$$\left.{\begin{array}{ll}c\mid a\\c\mid b\\\end{array}}\right\}\implies \left\{{\begin{array}{ll}c\;{\big |}\;\mid a\mid \\\\c\;{\big |}\;\mid b\mid \\\end{array}}\right\}\implies c\mid d\implies c\leq d,$$ $\quad \,d$ zenbakia $\mid a\mid$ eta $\mid b\mid$ zenbakien zatitzaile komun handiena delako.

4.18 Lema. Bézout-en lema

$a,b\in \mathbb {Z}$ badira, $a\neq 0$ edo $b\neq 0$ izanik, $\exists x,y\in \mathbb {Z}$, non ${\mbox{zkh}}(a,b)=xa+yb$ baita. Horrez gain, ${\mbox{zkh}}(a,b)$ da $a$ eta $b$ zenbakien konbinazio lineal moduan adieraz daitekeen zenbaki oso positiborik txikiena.

$${\mbox{zkh}}(a,b)=\min\{xa+yb\,/\,x,y\in \mathbb {Z} \,{\mbox{ eta }}\,xa+yb>0\}.$$

Froga.

$a,b\in \mathbb {Z} ^{+}$ direnean, emaitza hori 4.17 Teoremaren frogatik atera dezakegu.

$a\in \mathbb {Z} ^{-}$ edo $b\in \mathbb {Z} ^{-}$ direnean frogatzeko, nahikoa da ${\mbox{zkh}}(a,b)={\mbox{zkh}}(\mid a\mid ,\mid b\mid )$ dela kontuan hartzea konbinazio lineal positiboen $S$ eta $S'$ multzoak berdinak direla frogatzea, hots, berdintza hau betetzen dela:

$$S=\{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\}=S'.$$

$\supseteq$ )

Demagun, 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\}\implies$$ $$\implies 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}}\implies$$ $$\implies 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}}\implies$$ $$\implies z\in \{xa+yb\,/\,x,y\in \mathbb {Z} \,{\mbox{ eta }}\,xa+yb>0\}.$$ Eta hortik partekotasun hau aterako dugu: $$S'=\{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\}=S.$$

$\subseteq$ )

$S\subseteq S'$ beste partekotasuna antzeko eran frogatuko genuke. $\square$ $\blacksquare$ $\square$

Bézouten leman agertzen diren $x$ eta $y$ koefizienteak ez dira bakarrak; esate baterako, ${\mbox{zkh}}(a,b)=xa+yb$ bada, $p\in \mathbb {Z}$ guztietarako hau beteko da: $${\mbox{zkh}}(a,b)=(x+pb)a+(y-pa)b.$$ 4.19 Adibidea. 4.12 Adibidean ikusi dugu ${\mbox{zkh}}(24,32)=8$ dela eta 4.17 Teoremaren oharrean ${\mbox{zkh}}(-24,32)={\mbox{zkh}}(24,32)$ dela frogatu dugu; hortaz, $${\mbox{zkh}}(24,32)={\mbox{zkh}}(-24,32)=8.$$

Bestalde, Bezouten lemari esker badakigu $\exists x,y\in \mathbb {Z}$, non ${\mbox{zkh}}(24,32)=x24+y32$ baita; adibidez, $x=-1$ eta $y=1$ badira, $8=(-1)\cdot 24+1\cdot 32$.

Aurreko formula erabiliz, beste konbinazio lineal batzuk aurki ditzakegu:

• $p=1$ denean, $8=((-1)+1\cdot 32)\cdot 24+(1-1\cdot 24)\cdot 32=31\cdot 24+(-23)\cdot 32;$
• $p=2$ denean, $8=((-1)+2\cdot 32)\cdot 24+(1-2\cdot 24)\cdot 32=63\cdot 24+(-47)\cdot 32.$.

Badakigu $a,b\in \mathbb {Z}$ eta $d\in \mathbb {Z} ^{+}$ izanik, $d={\mbox{zkh}}(a,b)$ bada, $d$ zenbakia $a$ eta $b$ zenbakien konbinazio lineala dela, hau da, $$d={\mbox{zkh}}(a,b)\implies d=xa+yb,\;x,y\in \mathbb {Z} \,{\mbox{ izanik}}.$$

Baina elkarrekikoa ez da orokorrean betetzen $$d=xa+yb,\;\;x,y\in \mathbb {Z} \,{\mbox{ izanik}}\;\not \implies \nRightarrow d={\mbox{zkh}}(a,b).$$

Izan ere, orokorrean $d\geq {\mbox{zkh}}(a,b)$ betetzen da. Berdintza ziurtatzen duen kasu bakarra $d=1$ kasua da, hots, $$1=xa+yb,\;\;x,y\in \mathbb {Z} \,{\mbox{ izanik}}\;\iff {\mbox{zkh}}(a,b)=1.$$

Kasu horrek hurrengo definiziora garamatza:

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

4.21 Ondorioa. ${\textstyle a,b\in \mathbb {Z} }$ badira, $$a,b\,{\mbox{ lehen erlatiboak dira}}\iff \exists x,y\in \mathbb {Z} ,\,{\mbox{ non }}\,xa+yb=1\,{\mbox{den}}.$$

4.22 Adibidea.

1. $x=-2$ eta $y=2$ hartuz, $16=(-2)24+2\cdot 32.\,\,{\mbox{ Hortaz,}}\,\,{\mbox{zkh}}(24,32)\leq 16\,{\mbox{ da}}.$
2. Orain, $a=3$ eta $b=4$ zenbakiak hartuz, $1=(-1)3+1\cdot 4$ dugu. Hortaz, ${\mbox{zkh}}(3,4)=1$ eta $3$ eta $4$ zenbaki lehen erlatiboak dira.

4.1.5 Euklidesen algoritmoa

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

Euklidesen algoritmoa. 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}).$$

4.23 Teorema. $a,b\in \mathbb {Z} ^{+}$ izanik, Euklidesen algoritmoan lortzen den azken hondar ez-nulua $r_{k}$ bada, ${\mbox{zkh}}(a,b)=r_{k}$ beteko da.

Froga.

Berdintza hauek dauzkagu:

$$\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\}\quad {\mbox{ (4.1) }}$$

${\textstyle r_{0}=b}$ eta ${\textstyle r_{-1}=a}$ izendatzen baditugu, (4.1) honela idatz ditzakegu:

$$r_{i}=q_{i+2}r_{i+1}+r_{i+2},\quad i=-1,\ldots ,k-2.\quad {\mbox{ (4.2) }}$$

Eta horrez gain, beste hau ere badugu:

$$r_{k-1}=q_{k+1}r_{k}.\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad {\mbox{ (4.3) }}$$

${\textstyle {\mbox{zkh}}(a,b)=r_{k}}$ 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.

   (4.2) berdintzan 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.

   • Badakigu $r_{k}\mid r_{k}$ betetzen dela, $r_{k}\neq 0$ izanik.

   • Bestalde, (4.3) berdintzatik ${\textstyle r_{k}\mid r_{k-1}}$ ateratzen da.

   • ${\textstyle r_{k}\mid r_{k-2}}$ frogatzeko, (4.2) berdintzetako ${\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: (4.2) berdintzetako ${\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. ${\textstyle c\mid r_{k}}$ ere betetzen dela frogatu behar dugu. 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.

   (4.2) berdintzetatik ${\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.\quad \quad \quad \quad {\mbox{ (4.4) }}$$

   Ohar gaitezen, 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, (4.4) 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: (4.4) 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. $\square$ $\blacksquare$ $\square$

4.24 Adibidea. ${\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. Euklidesen algoritmoak ${\textstyle {\mbox{zkh}}(a,b)}$ ${\textstyle a,b}$ zenbakien konbinazio lineal bezala adierazteko metodoa erakutsi digu.

4.25 Adibideak.

1. 4.24 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

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

4.27 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.

4.28 Definizioa. Izan bitez $a,b,m\in \mathbb {Z} ^{+}$, $\,m$ zenbakia $a$ eta $b$ zenbakien multiplo komun txikiena dela esango dugu ($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.$$
2. $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\implies m\leq c.$$

4.29 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$. Gainera, ${\mbox{mkt}}(2,10)=10$ dela froga dezakegu:
   • $2\mid 10$ eta $10\mid 10$.
   • $(\forall c\in \mathbb {Z} ^{+})\quad 2\mid c,\quad 10\mid c\implies 10\mid c\implies 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 $a$ eta $b$ zenbakien multiplo komun guztiak ${\mbox{mkt}}(a,b)$ zenbakiaren multiploak direla frogatuko dugu.

4.30 Teorema. $a,b,m\in \mathbb {Z} ^{+}$ izanik, $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\implies m\mid c.$

Froga.

Demagun $m={\mbox{mkt}}(a,b)$ dela; hau da, $m$ zenbakiak 4.28 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 |\,c$ betetzen dela; kontraesan bat bilatuko dugu.

$m\not |\,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)\implies 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)\implies b\mid m$; hortaz, $b\mid r$ ere beteko da.

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

Ondorioz, $m\mid c$ dugu. $\square$ $\blacksquare$ $\square$

4.31 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.

4.32 Teorema. $a,b\in \mathbb {Z} ^{+}$ izanik, $ab={\mbox{mkt}}(a,b)\,{\mbox{zkh}}(a,b)$ betetzen da.

Froga.

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

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

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

1. $md\mid ab$:

   $ab=ak_{2}d=bk_{1}d\implies {\dfrac {ab}{d}}=ak_{2}=bk_{1}\implies \left\{{\begin{array}{ll}a\mid {\dfrac {ab}{d}}\\\\b\mid {\dfrac {ab}{d}}\end{array}}\right\}\implies m\mid {\dfrac {ab}{d}}$

   (4.30 Teoremaren arabera) $\implies md\mid ab.$

2. $ab\mid md$:

   $md=mxa+myb=k'_{2}bxa+k'_{1}ayb=(xk'_{2}+yk'_{1})ab\implies ab\mid md.$

$\left.{\begin{array}{ll}md\mid ab\\ab\mid md\\\end{array}}\right\}\implies ab=md{\mbox{ edo }}ab=-md\implies ab=md\quad (ab,md\in \mathbb {Z} ^{+}{\mbox{ direlako)}}.$ $\square$ $\blacksquare$ $\square$

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

4.33 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

4.7 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$, izanik, $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.

4.34 Lema. $a,b,p\in \mathbb {Z} ^{+}$ izanik, $\,p$ lehena izanik,

$\,p\mid ab\implies (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 $p\mid a$ edo $p\mid b$ betetzen dela frogatu behar dugu.

Horretarako, $p\not |\,a$ betetzen dela pentsatuko 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\implies 1=xa+yp,\quad x,y\in \mathbb {Z} \,{\mbox{ izanik }}\implies$

$\implies b=xab+ypb=xkp+ypb=(xk+yb)p,\quad xk+yb\in \mathbb {Z} \,{\mbox{ izanik }}\implies p\mid b.$ $\square$ $\blacksquare$ $\square$

4.35 Lema. $a_{1},\ldots ,a_{n},p\in \mathbb {Z} ^{+}$ izanik, $\,p$ lehena izanik,

$p\mid a_{1}\cdots a_{n}\implies 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, $p\mid a_{1}$ betetzen da.

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

4.34 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. $\square$ $\blacksquare$ $\square$

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

Irrazionala ez dela pentsatuko dugu. 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}}\implies 2={\dfrac {a^{2}}{b^{2}}}\implies 2b^{2}=a^{2}\implies 2\mid a^{2}=a\cdot a$

atera dezakegu. 4.34 Lema aplikatuz, $2\mid a$ ateratzen dugu. Eta hortik,

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

4.34 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.

4.37 Teorema. Aritmetikaren oinarrizko teorema

Edozein $n\in \mathbb {Z} ^{+}$, $n>1$, izanik, $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 zenbaki lehenen biderketa bezala}}\}.$

Absurdora eramanez, $S=\emptyset$ dela frogatuko dugu. Horretarako, $S\neq \emptyset$ dela pentsatuko dugu.

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 $m_{1}$ eta $m_{2}$ lehenen biderketa bezala adieraztea; eta hori $m\in S$ hipotesiaren kontra doa.

Ondorioz, $S=\emptyset$ da. Hortaz, edozein $n\in \mathbb {Z} ^{+}$, $n>1$, izanik, $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: $n=2$ da.

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

  Horretarako $k+1$ zenbakiak bi faktorizazio onartzen dituela pentsatuko dugu:

  $k+1=p_{1}^{s_{1}}\cdots p_{r}^{s_{r}}$, $p_{1}<\cdots <p_{r}$ zenbaki lehenak eta $s_{i}>0$, $i=1,\ldots ,r$, izanik;

  $k+1=q_{1}^{t_{1}}\cdots q_{u}^{t_{u}}$, $q_{1}<\cdots <q_{u}$ zenbaki lehenak eta $t_{i}>0$, $i=1,\ldots ,u$, izanik.

  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}$ zenbaki lehena denez, 4.35 Lemaren arabera, $p_{1}\mid q_{j}$ beteko da $j\in \{1,\ldots ,u\}$ baterako. $p_{1},q_{j}$ zenbaki 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}$ zenbaki lehena denez, 4.35 Lemaren arabera, $q_{1}\mid p_{i}$ beteko da $i\in \{1,\ldots ,r\}$ baterako. $q_{1},p_{i}$ zenbaki 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 hor dago kontraesana.

  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: $\quad \left\{{\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}}\right.$

  Baina, $n_{1}<k+1$ denez, indukzio-hipotesiaren arabera, $\,n_{1}$ zenbakiak faktorizazio bakarra dauka; beraz, hau dena beteko da: $\,r=u$, $\,p_{i}=q_{i}$, $i=1,\ldots ,r$ guztietarako, eta $\,s_{1}-1=t_{1}-1$ (hots, $s_{1}=t_{1}\,$) eta $\,s_{i}=t_{i}$, $\,i=2,\ldots ,r$ guztietarako. $\square$ $\blacksquare$ $\square$

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

• $2\mid 6552$: $\quad 6552=2\cdot 3276.$
• $2\mid 3276$: $\quad 3276=2\cdot 1638\implies 6552=2^{2}\cdot 1638.$
• $2\mid 1638$: $\quad 1638=2\cdot 819\implies 6552=2^{3}\cdot 819.$
• $2\not |\,819$; $\,3\mid 819$: $\quad 819=3\cdot 273\implies 6552=2^{3}\cdot 3\cdot 273.$
• $3\mid 273$: $\quad 273=3\cdot 91\implies 6552=2^{3}\cdot 3^{2}\cdot 91.$
• $3\not |\,91$; $\,5\not |\,91$; $\,7\mid 91$: $\quad 91=7\cdot 13\implies 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}}$ $\quad 6552=2^{3}\cdot 3^{2}\cdot 7\cdot 13.$

4.2 Aritmetika modularra

Atal honetan, zenbaki osoak $n$ zenbakiaz zatiketa euklidearra (4.1.3 Atala) egitean lortuko den hondarrarekin erlazionatuko ditugu, eta hondar bereko elementuen multzoak hartuko ditugu kontuan. Horrez gain, multzo horietako elementuen arteko eragiketa aritmetikoak aztertuko ditugu.

3.3.4 Atalean, $n$ moduluko kongruentziaren definizioa eman genuen:

$a\equiv b{\pmod {n}}\iff n\mid a-b\iff \exists k\in \mathbb {Z} \,/\,a=b+kn.$

Kasu horretan, $a-b$ zenbakia $n$-ren multiploa da.

Bestalde, 4.1.3 Atalean, zatiketa euklidearraren 4.9 Teorema eman genuen:

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

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

Horren arabera, hondar posible guztiak $0$, $1$, $\dots$, eta $b-1$ dira.

Oharrak.

1. Zatiketa euklidearra eta kongruentziaren definizioa kontutan izanik, $a\equiv b{\pmod {n}}$ bada, hau da, $a-b=kn$ bada, $a$ eta $b$ zenbakiek hondar bera emango dute $n$ zenbakiaz zatitzean; izan ere, $b$ zenbakiak $r$ hondarra ematen badu, $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$ zenbakiak, $n$ zenbakiaz zatitzean, $r$ hondarra emango du, alegia, $b$ zenbakiak ematen duen hondar bera: ${\begin{array}{rl}b&{\underline {\vline n}}\\r&q\\\end{array}}\quad b=qn+r,\quad 0\leq r<n.\quad \quad {\begin{array}{rl}a&{\underline {\vline n}}\\r&q+k\\\end{array}}\quad a=(q+k)n+r,\quad 0\leq r<n.$

2. $n$ moduluko kongruentzian, zatitzailea $n$ denez, hondar posible guztiak $0$, $1$, $\dots$, eta $n-1$ dira eta, ondorioz, $n$ moduluko hondarren multzoa $\mathbb {Z} _{n}=\{0,1,...,n-1\}$ da.

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

4.2.1 Eragiketa modularrak

4.39 Definizioa. $\mathbb {Z} _{n}$ multzoan, batuketa eta biderketa modularra honela definitzen dira:

$(a{\pmod {n}})+(b{\pmod {n}})=(a+b){\pmod {n}}.$

$(a{\pmod {n}})\cdot (b{\pmod {n}})=(a\cdot b){\pmod {n}}.$

Definizioak esaten digu $\mathbb {Z} _{n}$ multzoko $a{\pmod {n}}$ eta $b{\pmod {n}}$ bi klaseren arteko eragiketak egiteko, nahikoa dela klaseen $a$ eta $b$ ordezkarien arteko eragiketak egitea eta, ondoren, emaitzaren klasea ematea.

Gogoratu behar da $\mathbb {Z}$ multzoan elementu guztiek aurkakoa dutela, baina guztiek ez dutela alderantzizkorik. Berdin gertatzen da $\mathbb {Z} _{n}$ multzoan.

4.40 Definizioa.

1. $\mathbb {Z} _{n}$ multzoan, $a$ elementua izanik, $b\in \mathbb {Z} _{n}$ existitzen bada, non $a+b\equiv 0{\pmod {n}}$ den, $b$ elementuari $a$ elementuaren aurkako modularra deituko diogu eta $-a$ idatziko dugu.
2. $\mathbb {Z} _{n}$ multzoan, $a$ elementua alderantzikagarria da $\exists b\in \mathbb {Z} _{n}$, non $a\cdot b\equiv 1{\pmod {n}}$ den. $b$ elementuari $a$ elementuaren alderantzizko modularra deituko diogu eta $a^{-1}$ idatziko dugu.

$\mathbb {Z} _{n}$ multzoan, kenketa honela kalkulatuko dugu:

$(a{\pmod {n}})-(b{\pmod {n}})=(a+(-b)){\pmod {n}},$

non $-b$ elementua $b$-ren aurkakoa den $\mathbb {Z} _{n}$ multzoan.

$\mathbb {Z} _{n}$ multzoan, zatiketa ez dago elementu guztietarako definituta, eta existitzen denean honela kalkulatuko dugu:

$(a{\pmod {n}})\div (b{\pmod {n}})=(a\cdot (b^{-1})){\pmod {n}},$

non $b^{-1}$ elementua $b$-ren alderantzizkoa den $\mathbb {Z} _{n}$ multzoan.

4.41 Adibidea. Egin itzazu ondoko eragiketak $\mathbb {Z} _{12}$ multzoan:

$$5+7,\,\,3\cdot 8,\,\,4-9,\,\,5/7\,\,{\mbox{ eta }}\,\,10/3.$$

Formalki honela egingo genuke:

$(5{\pmod {12}})+(7{\pmod {12}})=(5+7){\pmod {12}}=12{\pmod {12}}\equiv 0{\pmod {12}}.$

$(3{\pmod {12}})\cdot (8{\pmod {12}})=(3\cdot 8){\pmod {12}}=24{\pmod {12}}\equiv 0{\pmod {12}}.$

$(4{\pmod {12}})-(9{\pmod {12}})=(4+(-9)){\pmod {12}}\equiv (4+3){\pmod {12}}=7{\pmod {12}},$ $-9\equiv 3{\pmod {12}}$ delako.

$(5{\pmod {12}})\div (7{\pmod {12}})=(5\cdot (7^{-1})){\pmod {12}}\equiv (5\cdot 7){\pmod {12}}=35{\pmod {12}}\equiv 11{\pmod {12}},$ $7^{-1}\equiv 7{\pmod {12}}$ delako.

$(10{\pmod {12}})\div (3{\pmod {12}})=(10\cdot (3^{-1})){\pmod {12}},$ ezin da egin ez delako existitzen $3^{-1}{\pmod {12}},$ hots, $\,\nexists p\in \mathbb {Z} _{12}\,/\,3\cdot p\equiv 1{\pmod {12}}.$

Idazkera sinplifikatuz, honela egingo dugu: $5+7=12\equiv 0{\pmod {12}}.$

Eta horrela egingo dugu kasu praktikoetan.

4.42 Teorema. Alderantzizko modularraren existentzia

$a^{-1}{\pmod {n}}$ existitzen da baldin eta soilik baldin ${\mbox{zkh}}(a,n)=1.$

Froga.

$\implies :$

$\exists x=a^{-1}{\pmod {n}}\implies xa\equiv 1{\pmod {n}}\implies n\mid xa-1\implies \exists y\in \mathbb {Z} \,/\,xa-1=yn\implies xa-yn=1\implies {\mbox{zkh}}(a,n)=1.$

$\Longleftarrow$ :

${\mbox{zkh}}(a,n)=1\implies \exists x,y\in \mathbb {Z} ,\,{\mbox{ non }}\,xa+yn=1\,{\mbox{den}}$. Hortik, $xa-1=yn\implies n\mid xa-1\implies xa\equiv 1{\pmod {n}}\implies \exists x=a^{-1}{\pmod {n}}$. $\square$ $\blacksquare$ $\square$

$\mathbb {Z} _{n}$ multzoan alderantzikagarri diren elementuen multzoari hondarren multzo murriztu deitzen zaio eta $\mathbb {Z} _{n}^{*}$ idatziko dugu: $\mathbb {Z} _{n}^{*}=\{a\in \mathbb {Z} _{n}\,/\,{\mbox{zkh}}(a,n)=1\}.$ Alderantzizko modularra existitzen denean, $a^{-1}{\pmod {n}}$ kalkulatzeko, Euklidesen algoritmoa erabiliko dugu.

Alderantzizko modularra kalkulatzeko bidea:

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

4.18 Bézouten lematik dakigunez, $\exists x,y\in \mathbb {Z}$, non $xa+yn={\mbox{zkh}}(a,n)=1$ den.

Hortik ondoriozta daiteke $a$-ren alderantzizko modularra $x$ dela:

$xa+yn=1\implies ax=1+(-y)n\implies xa\equiv 1{\pmod {n}}\implies a^{-1}=x{\pmod {n}}.$

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

4.43 Adibidea. Kalkula ditzagun elementu hauen alderantzizkoak $\mathbb {Z} _{12}$ multzoan: $$5,\quad 3,\quad 9,\quad 7\quad {\mbox{eta}}\quad 10.$$

Aurreko teoremak esaten digu $a$ elementu baten alderantzizkoa existitzeko $\mathbb {Z} _{12}$ multzoan, ${\mbox{zkh}}(a,12)=1$ bete behar dela.

${\mbox{zkh}}(3,12)=3$, ${\mbox{zkh}}(9,12)=3$ eta ${\mbox{zkh}}(10,12)=2$ direnez, $3$, $9$ eta $10$ elementuen alderantzizkoak ez dira existitzen.

${\mbox{zkh}}(5,12)=1$ eta ${\mbox{zkh}}(7,12)=1$ direnez, $5$ eta $7$ elementuen alderantzizkoak existitzen dira, eta kalkula ditzakegu.

Kalkula dezagun, orain, $5^{-1}{\pmod {12}})$. Badakigu, Bézouten lemagatik, $x,y\in \mathbb {Z}$ existitzen direla, non $5x+12y={\mbox{zkh}}(5,12)=1$ den.

Euklidesen algoritmoa erabiliko dugu $x=5^{-1}$ kalkulatzeko.

$${\begin{array}{cllll}{\begin{array}{rrll}12&{\underline {\vline 5}}\\2&2&\\\end{array}}&&12=2\cdot 5+2,&&2=12-2\cdot 5;\\\\{\begin{array}{rrll}5&{\underline {\vline 2}}\\1&2&\\\end{array}}&&5=2\cdot 2+1,&&1=5-2\cdot 2;\\\\{\begin{array}{rrll}2&{\underline {\vline 1}}\\0&2&\\\end{array}}&&2=1\cdot 2.&&\\\end{array}}$$

Hortik, $1=5-2\cdot 2=5-2\cdot (12-2\cdot 5)=(5)\cdot 5+(-2)\cdot 12.$

Eta, ondorioz, $5$aren alderantzizko modularra $5$ bera da, hots, $5^{-1}\equiv 5{\pmod {12}}$ da.

Egiazta daiteke hori: $5\cdot 5^{-1}=5\cdot 5=25\equiv 1{\pmod {12}}.$

Kalkula dezagun, orain, $7^{-1}{\pmod {12}})$. $\exists x,y\in \mathbb {Z}$ / $7x+12y={\mbox{zkh}}(7,12)=1.$

Euklidesen algoritmoa erabiliko dugu $x=7^{-1}$ kalkulatzeko.

$${\begin{array}{cllll}{\begin{array}{rrll}12&{\underline {\vline 7}}\\5&1&\\\end{array}}&&12=1\cdot 7+5,&&5=12-1\cdot 7;\\\\{\begin{array}{rrll}7&{\underline {\vline 5}}\\2&1&\\\end{array}}&&7=1\cdot 5+2,&&2=7-1\cdot 5;\\\\{\begin{array}{rrll}5&{\underline {\vline 2}}\\1&2&\\\end{array}}&&5=2\cdot 2+1,&&1=5-2\cdot 2;\\\\{\begin{array}{rrll}2&{\underline {\vline 1}}\\0&2&\\\end{array}}&&2=1\cdot 2.&&\\\end{array}}$$

Hortik, $1=5-2\cdot 2=5-2\cdot (7-1\cdot 5)=(3)\cdot 5+(-2)\cdot 7=(3)\cdot (12-1\cdot 7)+(-2)\cdot 7=$

$=(3)\cdot 12+(-5)\cdot 7.$

Ondorioz, $7$aren alderantzizko modularra $-5$ da $\mathbb {Z} _{12}$ multzoan, hots, $7^{-1}\equiv -5{\pmod {12}}$ da. Baina, $5$aren aurkakoa $7$ da $\mathbb {Z} _{12}$ multzoan, $5+7=12\equiv 0{\pmod {12}}$ delako. Hortaz, $7^{-1}\equiv 7{\pmod {12}}$ da.

4.2.2 Berreketa modularra

$\mathbb {Z}$ multzoan, $a^{x}$ berreketa, $a,x\in \mathbb {Z}$ eta $x\geq 0$ izanik, biderketen bidez kalkulatu ohi da, baina $x$ berretzailea handia denean, bi arazo sortzen dira:

• $a^{x}$ zenbaki handiegia izan daiteke, konputagailuak kalkulatu ahal izateko.
• $a$ zenbakia bere buruarekin $x-1$ aldiz biderkatu behar da eta, beraz, biderketa kopuru handia egin behar da, kostu konputazionala handituz.

$\mathbb {Z} _{n}$ multzoan, ordea, $a^{x}{\pmod {n}}$ kalkulatzean,

• Zenbaki handiegien arazoa ekiditen da, kalkuluetan $n$ moduluko kongruentzia erabiltzen delako, eta sortzen diren zenbaki berriak $n$ baino txikiagoak direlako, biderketa modularraren definizioari esker:

$$(a{\pmod {n}})\cdot (b{\pmod {n}})=(a\cdot b){\pmod {n}}.$$

• Bestalde, kostu konputazionala txikitu daiteke berreketa bitarraren metodoa erabiliz.

Berreketa bitarraren metodoa

• Berreketaren honako hiru propietateetan oinarritzen da:

$$a^{1}=a,\quad a^{x+y}=a^{x}a^{y},\quad a^{xy}=(a^{x})^{y}.$$

• $a^{x}$ berreketa kalkulatzeko, adierazpena behin eta berriz deskonposatzen da, berretzaile guztiak $1$ edo $2$ izan arte:

$$a^{x}=\left\{{\begin{array}{ll}a,&\quad x=1{\mbox{ bada,}}\\(a^{\frac {x}{2}})^{2},&\quad x{\mbox{ bikoitia bada,}}\\a\cdot a^{x-1},&\quad x{\mbox{ bakoitia bada.}}\end{array}}\right.$$

4.44 Adibidea. Kalkula ditzagun ondoko berreturak $\mathbb {Z} _{12}$ multzoan: $3^{8}$ eta $7^{9}$.

Aurreko irizpidea erabiliz, honela deskonposatuko ditugu berreturak:

$3^{8}=(3^{4})^{2}=((3^{2})^{2})^{2}\,$ eta $\,7^{9}=7\cdot 7^{8}=7\cdot (7^{4})^{2}=7\cdot ((7^{2})^{2})^{2}$.

Orain, $3^{2}$ eta $7^{2}$ berreturak kalkulatuko ditugu, eta aurreko adierazpenetan ordezkatu:

$81\equiv 9{\pmod {12}}\,$ eta $\,7^{2}=49\equiv 1{\pmod {12}}$ dira. Hortaz,

• $3^{8}=((3^{2})^{2})^{2}=((9)^{2})^{2}=(81)^{2}\equiv (9)^{2}=81\equiv 9{\pmod {12}}.$

• $7^{9}=7\cdot ((7^{2})^{2})^{2}\equiv 7\cdot ((1)^{2})^{2}=7\cdot (1)^{2}=7\cdot 1=7=7{\pmod {12}}.$

Berreketa modularraren kalkuluan hurrengo teoremek lagunduko digute.

4.45 Teorema. Fermat-en teorema txikia

Izan bedi $n\in \mathbb {Z} ^{+}$ zenbaki lehena. $a\in \mathbb {Z} ^{+}$ izanik, $a^{n-1}\equiv 1{\pmod {n}}$ betetzen da.

4.46 Adibidea. Kalkula dezagun $6^{52}$ berretura $\mathbb {Z} _{17}$ multzoan.

Aurreko teoremaren arabera, $17$ zenbaki lehena denez, $6^{17-1}=6^{16}\equiv 1{\pmod {17}}$ beteko da.

Beraz, $6^{52}$ berretura $6^{16}$ berreturaren bidez adieraztea komeniko zaigu. $52=3\cdot 16+4$ denez,

$6^{52}=6^{(3\cdot 16+4)}=6^{3\cdot 16}\cdot 6^{4}=(6^{16})^{3}\cdot 6^{4}\equiv (1)^{3}\cdot 6^{4}=1\cdot 6^{4}=6^{4}=(6^{2})^{2}=(36)^{2}\equiv 2^{2}=4{\pmod {17}},$ $\quad 36\equiv 2{\pmod {17}}$ izanik.

Hortaz, $6^{52}\equiv 4{\pmod {17}}$ da.

Kasu hori, ordea, oso sinplea da $n$ zenbaki lehena delako. Fermaten emaitza Eulerrek orokortu zuen teorema hauekin.

4.47 Definizioa. Euler-en $\phi (n)$ funtzioa $n$ moduluko hondarren multzo murriztuak duen elementu kopurua da, hau da, $\mathbb {Z} _{n}^{*}$ multzoaren kardinala da: $\phi (n)={\mbox{card}}(\mathbb {Z} _{n}^{*}).$

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

1. $n$ zenbakia lehena bada, $\phi (n)=n-1$ da.
2. $n=pq$ bada, $p$ eta $q$ bi zenbaki lehen desberdinak izanik, $\phi (n)=(p-1)(q-1)$ da.
3. $n=p_{1}^{e_{1}}\cdots p_{r}^{e_{r}}$ moduan deskonposa badaiteke, $p_{1},\ldots ,p_{r}$ zenbaki lehen desberdinak izanik, $\phi (n)={\dfrac {n}{p_{1}\cdots p_{r}}}(p_{1}-1)\cdots (p_{r}-1)$ da.

4.49 Teorema. Euler-en teorema

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

4.50 Adibide. Kalkula dezagun $22^{83}$ berretura $\mathbb {Z} _{75}$ multzoan.

Aurreko teoremak aplikatzeko, $75$ zenbakia deskonposatuko dugu: $75=3^{1}\cdot 5^{2}$ da.

Beraz, $\phi (75)={\dfrac {75}{3\cdot 5}}(3-1)(5-1)={\dfrac {75}{15}}(2)(4)=40$ da.

Eulerren teoremak dio $a^{40}\equiv 1{\pmod {75}}$ betetzen dela, ${\mbox{zkh}}(a,75)=1$ bada; gure kasuan, ${\mbox{zkh}}(22,75)=1$ denez, $22^{40}\equiv 1{\pmod {75}}$ da.

Beraz, berreturaren $83$ berretzailea honela deskonposatuko dugu: $83=2\cdot 40+3$.

Hortaz, $22^{83}=22^{(2\cdot 40+3)}=22^{2\cdot 40}\cdot 22^{3}=(22^{40})^{2}\cdot 22^{3}\equiv (1)^{2}\cdot 22^{3}=1\cdot 22^{3}=22^{3}=22\cdot (22^{2})=22\cdot 484\equiv 22\cdot 34=748\equiv 73{\pmod {75}},$ $484\equiv 34{\pmod {75}}$ izanik.

Ondorioz, $22^{83}\equiv 73{\pmod {75}}$ da.

4.51 Korolarioa. $a,n\in \mathbb {Z} ^{+}$ badira, ${\mbox{zkh}}(a,n)=1$ izanik, $a^{-1}\equiv a^{\phi (n)-1}{\pmod {n}}$ betetzen da.

Froga.

Izan ere, $a^{\phi (n)}=a\cdot a^{\phi (n)-1}$ da eta $a^{\phi (n)}\equiv 1{\pmod {n}}$ betetzen da; beraz, $a\cdot a^{\phi (n)-1}\equiv 1{\pmod {n}}$ denez, $a$-ren alderantzizko modularra $a^{\phi (n)-1}$ da. $\square$ $\blacksquare$ $\square$

4.52 Adibidea. Kalkula ditzagun elementu hauen alderantzizkoak $\mathbb {Z} _{12}$ multzoan: $5$ eta $7.$

Aurreko teoremak aplikatzeko, ${\mbox{zkh}}(5,12)=1$ eta ${\mbox{zkh}}(7,12)=1$ betetzen direla egiaztatzen dugu.

Beraz, $5^{-1}\equiv 5^{\phi (12)-1}{\pmod {12}}$ eta $7^{-1}\equiv 7^{\phi (12)-1}{\pmod {12}}$ izango dira.

Orain, $\phi (12)$ kalkulatuko dugu: $12=2^{2}\cdot 3$ denez, $\phi (12)={\dfrac {12}{2\cdot 3}}(2-1)(3-1)={\dfrac {12}{6}}(1)(2)=4$ da. Hortaz,

• $5^{-1}\equiv 5^{4-1}{\pmod {12}}=5^{3}=125\equiv 5{\pmod {12}}.$

• $7^{-1}\equiv 7^{4-1}{\pmod {12}}=7^{3}=7\cdot (7^{2})=7\cdot 49\equiv 7\cdot 1=7\equiv 7{\pmod {12}}.$

Emaitza horiek berak 4.43 Adibidean lortu genituen.

Oharrak.

1. Berreketa modularra Euler-Fermat teoremak erabiliz 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.3 RSA algoritmoa

RSA algoritmoa mezuak zifratzeko (enkriptatzeko) erabiltzen den sistema kriptografiko bat da. Zenbaki teoriaren eta aritmetika modularraren aplikaziotzat har daiteke.

Algoritmoaren izena bere asmatzaileen izenetatik dator. 1977. urtean, Ronald Rivest-ek, Adi Shamir-ek eta Leonard Adleman-ek sortu zuten.

RSA bidez zifratzeko, gako publikoa eta pribatua sortu behar dira. Horretarako, ezkutuan geratzen diren bi zenbaki lehen erabiltzen dira. Mezuak edonork zifra ditzake gako publikoarekin, baina gako pribatua ezagutzen duenak bakarrik deszifra ditzake.

RSA algoritmoaren segurtasuna zenbaki osoen faktorizazioa egiteak praktikan duen zailtasunean oinarritzen da, zenbakiak handiak direnean, ez baita ezagutzen faktorizazioa modu eraginkorrean egiteko gai den algoritmorik.

4.3.1 Oinarri teorikoa

4.53 Teorema. Izan bedi $n=pq$, $p$ eta $q$ zenbaki lehenak izanik, eta izan bitez $e$ eta $d$ zenbaki osoak $d\equiv e^{-1}{\pmod {\phi (n)}}$ betetzen dutenak, non $\phi (n)=(p-1)(q-1)$ Eulerren funtzioa den. Orduan, $a^{ed}\equiv a{\pmod {n}}$ da, $a<\min\{p,q\}$ guztietarako.

Froga. $n=pq$ denez, eta $p$ eta $q$ lehenak direnez, $\phi (n)=(p-1)(q-1)$ da (ikus 4.48 Teorema). Bestalde, $d\equiv e^{-1}{\pmod {\phi (n)}}$ denez, $ed\equiv 1{\pmod {\phi (n)}}$ da (ikus 4.40 Definizioa). Ondorioz, $\exists k\in \mathbb {Z}$, non $ed=1+k\phi (n)$ den; hau da, $a^{ed}=a^{1+k\phi (n)}$ da $k\in \mathbb {Z}$ baterako.

$n$ moduluko kongruentzian zera daukagu:

$a^{ed}\equiv a^{1+k\phi (n)}\equiv a(a^{\phi (n)})^{k}{\pmod {n}}.$

Bestalde, $a<\min\{p,q\}$ denez eta $n=pq$ denez, $a$ eta $n$ zenbaki lehen erlatiboak dira, $n$-ren zatitzaile bakarrak $p$ eta $q$ direlako, biak lehenak izanik. Eulerren teorema aplikatuz (ikus 4.49 Teorema), hau da, $a^{\phi (n)}\equiv 1{\pmod {n}}$ denez, $a^{ed}\equiv a(a^{\phi (n)})^{k}\equiv a(1)^{k}\equiv a{\pmod {n}}.$ $\square$ $\blacksquare$ $\square$

4.54 Adibidea.

Izan bitez $p=7$ eta $q=13$ zenbaki lehenak eta izan bitez $d=29$ eta $e=5$.

$n=pq=7\cdot 13=91$ da, eta $\phi (n)=(7-1)(13-1)=72$ da. Egiazta dezagun $29\equiv 5^{-1}{\pmod {\phi (91)}}$ edo $5\equiv 29^{-1}{\pmod {\phi (91)}}$ dela. Alegia, $5$ eta $29$ elkarren alderantzizkoak direla $\phi (91)=72$ moduluko kongruentzian.

Hona hemen kalkuluak $d=29$ zenbakirako, alderantzizko modularra kalkulatzeko bidea jarraituz (ikus 4.2.1 Atala):

$${\begin{array}{cllll}{\begin{array}{rrll}72&{\underline {\vline 29}}\\14&2&\\\end{array}}&&72=2\cdot 29+14,&&14=72-2\cdot 29;\\\end{array}}$$

$${\begin{array}{cllll}{\begin{array}{rrll}29&{\underline {\vline 14}}\\1&2&\\\end{array}}&&29=2\cdot 14+1,&&1=29-2\cdot 14.\\\end{array}}$$

Beraz, ${\mbox{zkh}}(29,72)=1$ da eta alderantzizko modularraren existentziaren teoremagatik (ikus 4.42 Teorema) $\exists 29^{-1}{\pmod {72}}$ dakigu.

Atzera ordezkatzeak eginez, Bezouten identitatea lortuko dugu:

$1=29-2\cdot 14=29-2\cdot (72-2\cdot 29)=29\cdot (1+4)+(-2)\cdot 72.$

Hortik,

$1=5\cdot 29+(-2)\cdot 72\quad \rightarrow \quad 5\cdot 29=1+2\cdot 72$

Frogatuta geratzen da $d=29$ eta $e=5$ bata bestearen alderantzizkoak direla 72 moduluko kongruentzian. Hau da, $de=1+k\phi (n)$ da, $k=2$ izanik.

Egiazta dezagun $a^{ed}\equiv a{\pmod {n}}$ dela. Eulerren teorematik (ikus 4.49 Teorema) $a^{72}\equiv 1{\pmod {91}}$ denez,

$a^{5\cdot 29}=a^{1+2\cdot 72}=a\cdot a^{2\cdot 72}=a\cdot (a^{72})^{2}\equiv a\cdot 1^{2}\equiv a{\pmod {91}}.$

Ikus dezagun, adibidez, $a=6$ baliorako $(6^{5})^{29}\equiv 6{\pmod {91}}$ dela. Berreketaren kalkulurako berreketa bitarrerako metodoa erabiliko dugu (ikus 4.2.2 Atala). Bi urratsetan egingo dugu:

• Lehenik, $a^{e}{\pmod {n}}=6^{5}{\pmod {91}}$ kalkulatu behar dugu:

$z\equiv 6^{5}=6\cdot (6^{2})^{2}=6\cdot (36)^{2}=6\cdot 1296\equiv 6\cdot 22=132\equiv 41{\pmod {91}}.$

• Orain, $(a^{e})^{d}{\pmod {n}}$ kalkulatuko dugu, hau da, $41^{29}{\pmod {91}}$:

$41^{29}=41\cdot (41^{14})^{2}=41\cdot ((41^{7})^{2})^{2}=41\cdot ((41\cdot (41^{3})^{2})^{2})^{2}=41\cdot ((41\cdot (41\cdot (41)^{2})^{2})^{2})^{2}=41\cdot ((41\cdot (41\cdot 1.681)^{2})^{2})^{2}\equiv$ $\equiv 41\cdot ((41\cdot (41\cdot 43)^{2})^{2})^{2}=41\cdot ((41\cdot (1.763)^{2})^{2})^{2}\equiv 41\cdot ((41\cdot (34)^{2})^{2})^{2}=41\cdot ((41\cdot 1.156)^{2})^{2}\equiv 41\cdot ((41\cdot 64)^{2})^{2}=$ $=41\cdot ((2.624)^{2})^{2}\equiv 41\cdot ((76)^{2})^{2}=41\cdot (5.776)^{2}\equiv 41\cdot (43)^{2}=41\cdot 1.849\equiv 41\cdot 29=1.189\equiv 6{\pmod {91}}.$ Espero zitekeen bezala, $(6^{5})^{29}\equiv 6{\pmod {91}}$ da.

4.3.2 Algoritmoaren urratsak

RSA algoritmoak lau urrats ditu: gakoak sortzea, gako publikoa zabaltzea, mezua zifratzea eta mezua deszifratzea.

Gakoak sortzea

RSA gakoak sortzeko, 4.53 Teoremaren baldintzak betetzen dituzten zenbakiak aukeratu behar dira. Jarraitu beharreko urratsak honakoak dira:

• Bi zenbaki lehen $p$ eta $q$ aukeratu, $p\neq q$ eta handiak (100 digitutik gorakoak).
• Kalkulatu $n=pq$ ($p$ eta $q$ handiak diren heinean $n$-ren faktorizazioa zaila izango da).
• Gako publikoa kalkulatu ($n$ eta $e$ zenbakiak). $\phi (n)=(p-1)(q-1)$ izanik, $\phi (n)$ zenbakiarekin lehen erlatiboa den $e$ zenbaki bat aurkitu behar da, hau da, ${\mbox{zkh}}(\phi (n),e)=1$ beteko duena. $e$ handia aukeratzea gomendatzen da.
• Gako pribatua kalkulatu ($d$ zenbakia). $\phi (n)$ moduluko kongruentzian $e$ gako publikoaren alderantzizkoa den $d$ balioa kalkulatu behar da, hau da, $d=e^{-1}{\pmod {\phi (n)}}$.

Gako publikoa zabaltzea

Argitara eman zifratzeko behar den gako publikoa, alegia, $n$ eta $e$ zenbakiak. Eta, ezkutuan gorde deszifratzeko beharrezkoa den gako pribatua, alegia, $d$ zenbakia.

Mezua zifratzea

$a$ mezua RSA algoritmoaren bidez zifratzea, $(n,e)$ gako publikoa erabiliz honako berreketa modularra kalkulatzea da:

$z\equiv a^{e}{\pmod {n}}.$

Horrela $z$ mezu zifratua lortzen da.

Mezua deszifratzea

$z$ mezu zifratua RSA algoritmoaren bidez deszifratzea honako berreketa modularra kalkulatzea da, $d$ gako pribatua eta publikoa den $n$ erabiliz:

$a\equiv z^{d}{\pmod {n}}.$

Aukeratu ditugun gakoek 4.53 Teoremaren baldintzak betetzen dituztenez, $a\equiv z^{d}\equiv (a^{e})^{d}{\pmod {n}}$

betetzen da, eta ondorioz $z$ mezu zifratua deszifratu eta $a$ mezu originala berreskuratzea lortzen da.

4.55 Adibidea.

Begoñak Asierri "kaixo" mezua bidali nahi dio zifratuta, RSA zifratze-algoritmoa erabiliz. Algoritmoaren segurtasuna bermatzeko zenbaki oso handiak erabili behar diren arren, kalkuluak errazteko zenbaki txikiak erabiliko dituzte.

Gakoak sortzea

Asierrek gakoak sortuko ditu mezu zifratua jaso ahal izateko.

• $p=17$ eta $q=23$ zenbaki lehenak aukeratu ditu.
• $n=pq=17\cdot 23=391$ $\rightarrow$ $n=391.$
• Gako publikoa ($n,e$). $n=391$ zenbakirako $e$ egoki bat aukeratu behar du.
  • $\phi (n)=(p-1)(q-1)=16\cdot 22=352\quad \rightarrow \quad \phi (n)=352.$
  • ${\mbox{zkh}}(\phi (n),e)=1\quad \rightarrow \quad {\mbox{zkh}}(352,e)=1.$ $e$ baliorako aukera bat baino gehiago existitzen da. $\phi (n)$ zenbakiarekin lehen erlatiboa den zenbaki handi bat aukeratzea gomendatzen bada ere, berak txikiena aukeratu du: $e=3.$
• Gako pribatua ($d$). Alderantzizko modularra kalkulatzeko bidea jarraituz, egiazta daiteke $d=235$ dela, hau da, $3\cdot 235\equiv 1{\pmod {352}}$ da.

Oharra. Gako publikoko $n$ zenbakia txikia da, eta faktorizatuz $p$ eta $q$ erraz kalkula daitezke. $n$ faktorizatzea lortzen denean, sistema kriptografikoak porrot egin duela esaten da. Izan ere, $e$ publikoa denez, goiko kalkulu guztiak egin daitezke eta $d$ gako pribatua kalkulatu.

Gako publikoa zabaltzea

Asierrek $n=391$ eta $e=3$ balioak publiko egingo ditu eta $d=235$ gako pribatua ezkutuan gordeko du. Bere gako publikoak eta RSA zifratze-algoritmoa erabiliz zifratutako mezuak jasotzeko prest dago.

Mezua zifratzea ($a_{i}\rightarrow z_{i}$)

Begoñak Asierren gako publikoa erabiliz "kaixo" mezua zifratu behar du. Baina, zifratzeak eskatzen duen berreketa modularra kalkulatu ahal izateko, nahitaezkoa da mezua zifratu aurretik kodetzea, hau da, karakterez osatuta dagoen mezu originala zenbakietara bihurtzea.

Kodeketa erabiliena ASCII kodeketa da. "kaixo" mezuaren karaktereei dagozkien ASCII kodeak honakoak dira: 107, 97, 105, 120, 111. Zifratzeko kalkuluak hauek dira:

• $a_{1}=107\quad \Longrightarrow \quad z_{1}=a_{1}^{e}{\pmod {n}}=107^{3}{\pmod {391}}=40.$
• $a_{2}=97\quad \Longrightarrow \quad z_{2}=a_{2}^{e}{\pmod {n}}=97^{3}{\pmod {391}}=79.$
• $a_{3}=105\quad \Longrightarrow \quad z_{3}=a_{3}^{e}{\pmod {n}}=105^{3}{\pmod {391}}=265.$
• $a_{4}=120\quad \Longrightarrow \quad z_{4}=a_{4}^{e}{\pmod {n}}=120^{3}{\pmod {391}}=171.$
• $a_{5}=111\quad \Longrightarrow \quad z_{5}=a_{5}^{e}{\pmod {n}}=111^{3}{\pmod {391}}=304.$

Begoñak Asierri $(40,79,265,171,304)$ mezu zifratua bidaliko dio.

Mezua deszifratzea ($z_{i}\rightarrow a_{i}$)

Asierrek mezu zifratua deszifratuko du bere $d=235$ gako pribatua erabiliz.

• $z_{1}=40\quad \Longrightarrow \quad a_{1}=z_{1}^{d}{\pmod {n}}=40^{235}{\pmod {391}}=107.$
• $z_{2}=79\quad \Longrightarrow \quad a_{2}=z_{2}^{d}{\pmod {n}}=79^{235}{\pmod {391}}=97.$
• $z_{3}=265\quad \Longrightarrow \quad a_{3}=z_{3}^{d}{\pmod {n}}=265^{235}{\pmod {391}}=105.$
• $z_{4}=171\quad \Longrightarrow \quad a_{4}=z_{4}^{d}{\pmod {n}}=171^{235}{\pmod {391}}=120.$
• $z_{5}=304\quad \Longrightarrow \quad a_{5}=z_{5}^{d}{\pmod {n}}=304^{235}{\pmod {391}}=111.$

Deszifratu ondoren, mezua ASCII kodeetan lortu du $(107,97,105,120,111)$, eta ASCII kodeak karaktere bihurtuz, "kaixo" mezu originala lortu du.

Oharra. Adibide honetan ez da betetzen 4.53 Teoremako $a<\min\{p,q\}$ baldintza, Asierrek $p=17$ eta $q=23$ zenbaki lehenak txikiegiak aukeratu dituelako. Dena den, Eulerren teoremaren baldintza betetzen da, ${\mbox{zkh}}(a_{i},n)=1$ betetzen delako adibideko $a_{i}$ guztietarako.

4.3.3 Mezu ziurtatuetarako erabilera

RSA gakoek beste erabilera bat ere badute: mezu ziurtatua bidaltzeko aukera ematen dute. Alegia, mezua sortu duena nor izan den ziurtatzeko aukera ematen dute. Mezua sinatzearen pareko prozesua da.

Mezua sinatzeko, gako pribatuarekin zifratu behar da. Hori gakoen jabeak baino ezin du egin, berak bakarrik ezagutzen baitu $d$ gakoa. Gakoen jabeak (sinatzaileak) $a$ mezua sinatzeko

$z\equiv a^{d}{\pmod {n}}$

mezu sinatua sortuko du. $z$ mezu ziurtatu hori edonork deszifra dezake sinatzailearen beraren gako publikoak erabiliz:

$a=z^{e}{\pmod {n}}.$

Horrela, mezu hori gakoen jabe den sinatzaileak sortua dela ziurtatzen da.