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 $\mathbb{Z}$ multzoa aztertuko dugu, baita bertan defini daitezkeen eragiketak eta $\le$, “txikiago edo berdin” ordena-erlazioa ere.

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

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

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

• Bestalde, $\le$ ordena-erlazioa da $\mathbb{Z}$ multzoan, [orderl] atalean definitu ditugun propietateak betetzen dituelako:

  • Bihurtze-propietatea: $(\mathrm{\forall }x\in \mathbb{Z})x\le x$.

  • Antisimetria-propietatea: $(\mathrm{\forall }x,y\in \mathbb{Z})x\le y\wedge y\le x\Rightarrow x=y$.

  • Iragate-propietatea: $(\mathrm{\forall }x,y,z\in \mathbb{Z})x\le y\wedge y\le z\Rightarrow x\le z$.

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

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

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

4.1.2 Zatigarritasuna. Zenbaki lehenak

${\mathbb{Z}}^{*}$ multzoa $/$ zatiketarako itxia ez bada ere, badira kasu batzuk non zenbaki oso batek beste bat zehazki zatitzen duen. Esaterako, $4$ak $12$a 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 izanik, $a\ne 0$ izanik, $a$ zenbakiak $b$ zenbakia zatitzen du, eta $a\mid b$ adieraziko dugu, baldin $$\mathrm{\exists }k\in \mathbb{Z},\text{ non }b=ka\text{ den. }$$ Hori gertatzen denean, $a$ zenbakia $b$ zenbakiaren zatitzaile bat dela esango dugu, edo $b$ zenbakia $a$ zenbakiaren multiplo bat dela.

Hitzarmena. $a\mid b$ idazten dugunean, $a\ne 0$ dela pentsatuko dugu.

4.2 Lema. $a,b\in {\mathbb{Z}}^{+}$ bada, $a\mid b⟹a\le b$.

Ondoko teoreman zatigarritasunaren propietate batzuk frogatuko ditugu.

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

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

Froga.

1. $a=1a.$ da; beraz, $1\mid a$ eta $a\mid a$. Bestalde, $0=0a.$ da; beraz, $a\mid 0$.
2. Hasteko, $(a\mid b)\wedge (b\mid a)$ daukagu, hau da, $$\begin{array}{c}a\mid b\\ \wedge \\ b\mid a\end{array}\}⟹\begin{array}{c}b=k_{1}a,k_1\in \mathbb{Z}\text{ izanik}\\ \wedge \\ a=k_{2}b,k_2\in \mathbb{Z}\text{ izanik}\end{array}\}⟹b=k_1(k_{2}b)=(k_1{k}_2)b,$$$$k_1,k_2\in \mathbb{Z}\text{ izanik}⟹k_1{k}_2=1,k_1,k_2\in \mathbb{Z}\text{ izanik}⟹\begin{array}{c}{k}_1=k_2=1\\ \vee \\ k_1=k_2=-1\end{array}\}⟹\begin{array}{c}a=b\\ \vee \\ a=-b.\end{array}$$
3. Kasu honetan $(a\mid b)\wedge (b\mid c)$ daukagu, $$\begin{array}{c}a\mid b\\ \wedge \\ b\mid c\end{array}\}⟹\begin{array}{c}b=k_{1}a,k_1\in \mathbb{Z}\text{ izanik}\\ \wedge \\ c=k_{2}b,k_2\in \mathbb{Z}\text{ izanik}\end{array}\}⟹c=k_2(k_{1}a)=(k_2{k}_1)a,$$ $k_2{k}_1\in \mathbb{Z}\text{ izanik }⟹a\mid c$.
4. Edozein $x\in \mathbb{Z}$ izanik, $$a\mid b⟹b=ka,k\in \mathbb{Z}\text{ izanik}⟹xb=x(ka)=(xk)a,xk\in \mathbb{Z}\text{ izanik}⟹a\mid xb.$$
5. Edozein $x,y\in \mathbb{Z}$ izanik, $$\begin{array}{c}a\mid b\\ \wedge \\ a\mid c\end{array}\}⟹\begin{array}{c}b=k_{1}a,k_1\in \mathbb{Z}\text{ izanik}\\ \wedge \\ c=k_{2}a,k_2\in \mathbb{Z}\text{ izanik}\end{array}\}⟹xb+yc=x(k_{1}a)+y(k_{2}a)=$$ $$=(x{k}_1+y{k}_2)a,x{k}_1+y{k}_2\in \mathbb{Z}\text{ izanik }⟹a\mid xb+yc.$$ $◻$

Oharrak.

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

   $a$ zenbakiak $b$ eta $c$ zenbakiak zatitzen baditu, [propietateak]-5 Teoremaren arabera, $a$ zenbakiak $b$ eta $c$ zenbakien edozein konbinazio lineal zatituko du.

2. Propietate hori honela zabal daiteke: $b_1,\cdots ,b_n\in \mathbb{Z}$ izanik, $$x_1{b}_1+\cdots +x_n{b}_n,x_1,\dots ,x_n\in \mathbb{Z}\text{ izanik},$$ adierazpenari $b_1,\dots ,b_n$ zenbakien konbinazio lineal deituko diogu.

   $a$ zenbakiak $b_1,\dots ,b_n$ zenbakiak zatitzen baditu, $a$ zenbakiak $b_1,\dots ,b_n$ zenbakien edozein konbinazio lineal zatituko du: $$a\mid b_i,i=1,\cdots ,n⟹(\mathrm{\forall }{x}_1,\cdots ,x_n\in \mathbb{Z})a\mid x_1{b}_1+\cdots +x_n{b}_n.$$

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

Demagun $x,y,z$ zenbaki oso horiek existitzen direla. $5\mid 5$, $5\mid 10$ eta $5\mid 20$ betetzen direnez, $5\mid 1003$ ere beteko litzateke; baina hori ez da gertatzen. Hortaz, ez daude ekuazioa betetzen duten $x,y,z$ zenbaki osoak.

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

$n$ zenbaki lehena dela esango dugu bere zatitzaile positibo bakarrak $n$ eta $1$ badira: $$m\mid n,m\in {\mathbb{Z}}^{+}⟹m=1\vee m=n.$$ Eta $n$ zenbaki konposatua dela esango dugu ez bada lehena: $$\mathrm{\exists }{m}_1,m_2\in {\mathbb{Z}}^{+}\text{ non }n=m_1{m}_2,1<m_1<n,1<m_2<n.$$

4.6 Adibidea. $12$ zenbaki konposatua da, $12>1$ delako eta $1$, $2$, $3$, $4$, $6$ eta $12$ zatitzaileak dituelako.

$11$ zenbaki lehena da, $11>1$ delako eta bere zatitzaile positibo bakarrak $1$ eta $11$ direlako.

Hurrengo teoreman zenbaki lehenen eta konposatuen arteko erlazio bat frogatuko dugu.

4.7 Teorema. [lekon] Zenbaki konposatu orok zatitzaile lehenen bat dauka. Hau da, $n\in {\mathbb{Z}}^{+}$, $n>1$ izanik, $$n\text{ konposatua }⟹\mathrm{\exists }p\in {\mathbb{Z}}^{+},p\text{ lehena eta }p\mid n.$$

Froga.

Izan bedi $S$ zatitzaile lehenik ez duten zenbaki oso konposatu guztien multzoa: $$S=\{x\in {\mathbb{Z}}^{+}/x\text{ konposatua da eta ez du zatitzaile lehenik}\}.$$ Absurdora eramanez, $S=\mathrm{\varnothing }$ dela frogatuko dugu.

Demagun $S\ne \mathrm{\varnothing }$ dela. $S$ multzoa ${\mathbb{Z}}^{+}$ multzoaren azpimultzo ez-hutsa denez, ordena onaren printzipioaren arabera, $S$ multzoak elementu minimoa izango du, $m$.

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

$m$ da $S$ multzoaren minimoa eta $m_1<m$ da; beraz, $m_1\in ̸S$ beteko da. Hortaz, $m_1$ lehena da edo zatitzaile lehenen bat dauka.

$m_1$ lehena bada, $m_1$ lehena da eta $m_1\mid m$ betetzen da.

$m_1$ zenbakiak $p$ zatitzaile lehen bat badauka, $p$ lehena da eta $p\mid m_1$ eta $m_1\mid m$; hortaz, $p\mid m$.

Bi kasuetan kontraesan bat aurkitu dugu, $m$ zenbakiak ez baitauka zatitzaile lehenik. Hortaz, $S=\mathrm{\varnothing }$ da; eta, ondorioz, zenbaki konposatu orok zatitzaile lehenen bat badauka. $◻$

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

Infinitu zenbaki lehen daude.

Froga.

Absurdora eramanez frogatuko dugu.

Jo dezagun zenbaki lehenen kopurua finitua dela: $p_1,\dots ,p_k$.

Izan bitez $a=p_1\dots p_k$ eta $A=a+1$.

Orduan, $p_i\mid a$, $i=1,\dots ,k$ dugu eta, beraz, $a\ge p_i$, $i=1,\dots ,k$; hortik $A\ne p_i$, $i=1,\dots ,k$ aterako dugu. Beraz, $A$ konposatua da. [lekon] Teoremaren arabera, badago $p_j\in \{p_1,\dots ,p_k\}$ zenbaki lehenen bat, non $p_j\mid A$ betetzen den.

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

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

4.1.3 Zatiketa euklidearra

[zateuk]

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

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

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

Zergatik ez da $4$ zatidura? $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, $38-x\cdot 7$ ahalik eta txikiena, baina positiboa, egiten duen $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}{ccc}-38& \underset{\_}{\mathrm{\backslash vline}7}& \\ 4& -6& \end{array}$$ $-38-x\cdot 7>0$ izan dadin $x<-5$ bete behar da. $$\begin{array}{cc}x& -38-x\cdot 7\\ -4& -10\\ -5& -3\\ -6& 4\\ -7& 11\\ -8& 18\\ ⋮& ⋮\end{array}$$

“Hondar” positibo txikiena $4$ da eta, beraz, zatidura $-6$ da.

Euklidesek ideia hori teorema honetan zehaztu zuen:

4.9 Teorema. Euklidesen teorema [zateukteo]

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

$q$ zatidura, $r$ hondarra, $a$ zatikizuna eta $b$ zatitzailea dira.

Froga.

$q$ eta $r$ existitzen dira.

Bi kasu bereiziko ditugu: $b\mid a$ eta $b|a$.

1. $b\mid a$.

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

2. $b|a$.

   Izan bedi $S=\{a-xb/x\in \mathbb{Z}\text{ eta }a-xb>0\}$ multzoa. Lehendabizi, $S\ne \mathrm{\varnothing }$ dela frogatuko dugu:

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

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

   Hortaz, $S\ne \mathrm{\varnothing }$ da, eta ordena onaren printzipioaren arabera, $S$ multzoak elementu minimoa du; izan bedi $r:=\min S$. $$r\in S⟹r=a-qb>0,q\in \mathbb{Z}\text{ izanik}⟹a=qb+r,q,r\in \mathbb{Z}\text{ eta }r>0\text{ izanik}.$$

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

   1. $r=b$ bada, $a=qb+b=(q+1)b$ da eta, hortaz, $b\mid a$ beteko da, hartu dugun $b|a$ baldintzaren kontrakoa dena.

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

$q$ eta $r$ bakarrak dira.

Demagun $$\mathrm{\exists }{q}_1,q_2,r_1,r_2\in \mathbb{Z},\text{ non }a=q_{1}b+r_1=q_{2}b+r_2\text{ den},$$ $0\le r_1<b$ eta $0\le r_2<b$ izanik. Orduan, $$(q_1-q_2)b=r_2-r_1$$ beteko da.

Lehendabizi, $r_1=r_2$ dela frogatuko dugu.

$r_1\ne r_2$ dela pentsatuko dugu eta kontraesan bat aurkituko dugu.

1. $r_2>r_1$ bada, $0<(q_1-q_2)b\le r_2<b$ izango dugu. $b>0$ denez, $0<q_1-q_2<1$ aterako dugu; eta hori ezinezkoa da $q_1-q_2\in \mathbb{Z}$ delako.
2. $r_2<r_1$ bada, arrazoibide bera da, kontuan izanik $(q_2-q_1)b=r_1-r_2$ dela.

Hortaz, $r_1=r_2$ dugu; hortik $q_{1}b=q_{2}b$ aterako dugu. $b\ne 0$ denez, $q_1=q_2$ lortuko dugu. $◻$

4.10 Adibidea. $$\begin{array}{ccc}27& \underset{\_}{\mathrm{\backslash vline}6}& \\ 3& 4& \end{array}\begin{array}{ccc}-27& \underset{\_}{\mathrm{\backslash vline}6}& \\ 3& -5& \end{array}\begin{array}{ccc}6& \underset{\_}{\mathrm{\backslash vline}27}& \\ 6& 0& \end{array}\begin{array}{ccc}-6& \underset{\_}{\mathrm{\backslash vline}27}& \\ 21& -1& \end{array}$$

4.1.4 Zatitzaile komun handiena

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

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

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

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

4.14 Adibidea. [zatikomu] Adibidean ikus dezakegu $-24$ eta $32$ zenbakien zatitzaile komun handiena $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.

4.15 Teorema. (Zatitzaile komun handienaren bakartasuna)

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

Froga.

Demagun $a$ eta $b$ zenbakien bi zatitzaile komun handien daudela, $d_1$ eta $d_2$. $d_1=d_2$ dela frogatuko dugu.

$d_1$ $a$ eta $b$ zenbakien zatitzaile komuna da; beraz, $d_1\mid a$ eta $d_1\mid b$; hortaz, $d_1\mid d_2$, $d_2$ delako $a$ eta $b$ zenbakien zatitzaile komun handienetako bat.

Antzeko eran frogatuko genuke $d_2\mid d_1$ ere betetzen dela. Orduan, $$\begin{array}{c}{d}_1\mid d_2\\ d_2\mid d_1\end{array}\}⟹d_1=d_2\text{ edo }{d}_1=-d_2.$$ $d_1,d_2\in {\mathbb{Z}}^{+}$ denez, aukera bakarra $d_1=d_2$ izatea da. $◻$

Oharrak.

1. $a,b\in \mathbb{Z}$ izanik, $a$ eta $b$ zenbakien zatitzaile komun handiena badago, $\text{zkh}(a,b)$ adieraziko dugu.
2. $\text{zkh}(a,b)$ badago, $\text{zkh}(b,a)=\text{zkh}(a,b)$ beteko da.
3. $\text{zkh}(0,0)$ ez dago definiturik.
4. $a\in {\mathbb{Z}}^{*}$ bada, erraz froga daiteke $\text{zkh}(a,0)$ badagoela, eta $\text{zkh}(a,0)=\mid a\mid$ betetzen dela.
   • $\mid a\mid$ zenbakia $a$ eta $0$ zenbakien zatitzaile komuna da: $$a=\mid a\mid \text{ edo }a=(-1)\cdot \mid a\mid ⟹\mid a\mid |a$$
   $$\mid a\mid |0\text{ (edozein zenbaki oso da 0 zenbakiaren zatitzailea).}$$
   • $\mid a\mid$ zenbakia $a$ eta $0$ zenbakien zatitzaile komun handiena da: $c\in {\mathbb{Z}}^{+}$ izanik,
   $$\begin{array}{c}c\mid a\\ c\mid 0\end{array}\}⟹c\mid a⟹c|\mid a\mid \text{ (}\mid a\mid =a\text{ edo }\mid a\mid =-a\text{ delako).}$$

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

4.16 Teorema. (Zatitzaile komun handienaren existentzia) [zkhex]

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

Froga.

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

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

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

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

1. $d$ zenbakia $a$ eta $b$ zenbakien zatitzaile komun bat da:

   • Demagun $d|a$ dela, eta kontraesan bat aurkituko dugu:

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

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

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

$◻$

Oharrak.

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

   1. $\text{zkh}(\mid a\mid ,\mid b\mid )$ existitzen dela jadanik frogatu dugu. Eta erraz froga dezakegu $\text{zkh}(a,b)=\text{zkh}(\mid a\mid ,\mid b\mid )$ betetzen dela.

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

      • $d$ zenbakia $a$ eta $b$ zenbakien zatitzaile komun bat da: $$d=\text{zkh}(\mid a\mid ,\mid b\mid )⟹\{\begin{array}{c}d|\mid a\mid ⟹d\mid a\\ \\ d|\mid b\mid ⟹d\mid b\end{array}$$

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

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

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

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

4.17 Adibidea. $$\text{zkh}(24,32)=\text{zkh}(-24,32)=8.$$ $$\begin{array}{cc}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}$$

Oharra. $a,b\in \mathbb{Z}$ eta $d\in {\mathbb{Z}}^{+}$ izanik, $$d=\text{zkh}(a,b)⟹d=xa+yb,x,y\in \mathbb{Z}\text{ izanik}.$$ Baina elkarrekikoa ez da orokorrean betetzen, $d=1$ denean izan ezik. $$d=xa+yb,x,y\in \mathbb{Z}\text{ izanik}⟹d\ge \text{zkh}(a,b).$$

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

4.19 Ondorioa. $a,b\in \mathbb{Z}$ emanik, $$a,b\text{ lehen erlatiboak dira}⟺\mathrm{\exists }x,y\in \mathbb{Z},\text{ non }xa+yb=1\text{den}.$$

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

4.1.5 Euklidesen algoritmoa

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

Euklidesen algoritmoa. Ondoko zatiketak egingo ditugu:

$$\begin{array}{ccccc}\begin{array}{cc}a& \underset{\_}{\mathrm{\backslash vline}b}\\ r_1& q_1& \end{array}& & a=q_{1}b+r_1,& & 0<r_1<b;\\ \\ \begin{array}{cc}b& \underset{\_}{\mathrm{\backslash vline}{r}_1}\\ r_2& q_2& \end{array}& & b=q_2{r}_1+r_2,& & 0<r_2<r_1;\\ \\ \begin{array}{cc}{r}_1& \underset{\_}{\mathrm{\backslash vline}{r}_2}\\ r_3& q_3& \end{array}& & r_1=q_3{r}_2+r_3,& & 0<r_3<r_2;\\ \\ ⋮& & ⋮& & ⋮\\ \\ \begin{array}{cc}{r}_i& \underset{\_}{\mathrm{\backslash 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};\\ \\ ⋮& & ⋮& & ⋮\\ \end{array}$$

Gero eta hondar txikiagoak lortzen ditugunez, noizbait 0 hondarra lortuko dugu:

$$\begin{array}{ccccc}\begin{array}{cc}{r}_{k-1}& \underset{\_}{\mathrm{\backslash vline}{r}_k}\\ 0& q_{k+1}& \end{array}& & r_{k-1}=q_{k+1}{r}_k+0.& & \end{array}$$

$$b>r_1>r_2>\cdots >r_{k-1}>r_k>0(=r_{k+1}).$$

Orduan, $r_k$, $0$ ez den azkeneko hondarra, $\text{zkh}(a,b)$ da:

$$\text{zkh}(a,b)=r_k.$$

Froga.

Berdintza hauek dauzkagu:\label{hiru}

$$\begin{array}{c}a=q_{1}b+r_1,\\ b=q_2{r}_1+r_2,\\ r_i=q_{i+2}{r}_{i+1}+r_{i+2},i=1,\dots ,k-2.\end{array}\}\text{ (hiru) }$$

$r_0=b$ eta $r_{-1}=a$ izendatzen baditugu, ([hiru]) honela idatz ditzakegu:

$$r_i=q_{i+2}{r}_{i+1}+r_{i+2},i=-1,\dots ,k-2.\text{ (ri) }$$

Eta horrez gain, beste hau ere badugu:

$$r_{k-1}=q_{k+1}{r}_k.\text{ (rk) }$$

$\text{zkh}(a,b)=r_k$ dela frogatzeko, ondokoa frogatu beharko dugu:

1. $r_k$ hondarra $a$ eta $b$ zenbakien zatitzaile komun bat da; hau da, $r_k\mid a$ eta $r_k\mid b$ betetzen dira.

   Horretarako, ondoz ondo frogatuko dugu $r_k$ hondarrak $r_k$, $r_{k-1}$, $r_{k-2}$, $r_{k-3}$, etab. zatitzen dituela, $r_0=b$ eta $r_{-1}=a$ ere zatitzen dituela frogatu arte.

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

   • Argi dago $r_k\mid r_k$ betetzen dela.

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

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

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

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

2. $r_k$ hondarra $a$ eta $b$ zenbakien zatitzaile komun handiena da; hau da, $a$ eta $b$ zenbakien edozein zatitzaile komun $r_k$ hondarraren zatitzailea da.

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

   ([ri]) berdintzetatik $r_{i+2}$ bakanduz gero, ekuazio hauek lortuko ditugu: $$r_{i+2}=r_i-q_{i+2}{r}_{i+1}i=-1,\dots ,k-2.\text{ (alder) }$$

   Ohar gaitezen, orduan, $i=-1,\dots ,k-2$ balioetarako $r_{i+2}$ hondarra $r_i$ eta $r_{i+1}$ hondarren konbinazio lineala dela; propietate hori erabiliko dugu.

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

   • $c\mid b=r_0$.

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

   • $c\mid r_2$ frogatzeko, arrazoibidea antzekoa da: ([alder]) ekuazioetako $i=0$ kasuan, $r_2=r_0-q_2{r}_1$ dugu; hau da, $r_2$ hondarra $r_0$ eta $r_1$ hondarren konbinazio lineala da. $c\mid r_0$ eta $c\mid r_1$ betetzen direla frogatu dugunez, $c\mid r_2$ ere beteko da.

   • Antzeko eran frogatuko dugu $c\mid r_3$, $c\mid r_4$, etab. betetzen direla $c\mid r_k$ betetzen dela frogatu arte.

$◻$

4.21 Adibidea. [zkh] $\text{zkh}(250,12)$ kalkulatzeko: $$\begin{array}{cc}250& \underset{\_}{\mathrm{\backslash vline}12}\\ 10& 20& \end{array}\begin{array}{cc}12& \underset{\_}{\mathrm{\backslash vline}10}\\ 2& 1& \end{array}\begin{array}{cc}10& \underset{\_}{\mathrm{\backslash vline}2}\\ 0& 5& \end{array}.$$ Hortaz, $$\text{zkh}(250,12)=\text{zkh}(-250,12)=\text{zkh}(250,-12)=\text{zkh}(-250,-12)=2.$$

Oharrak.

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

4.22 Adibideak.

1. [zkh] adibidean, $\text{zkh}(250,12)=2$ kalkulatu dugu. $2$ emaitza $250$ eta $12$ zenbakien konbinazio lineal bezala adierazteko, $2$ azkeneko hondar ez-nulua $10$ eta $12$ zenbakien konbinazio lineal bezala adierazten hasiko gara: $$\begin{array}{ccccc}\begin{array}{cc}12& \underset{\_}{\mathrm{\backslash vline}10}\\ 2& 1& \end{array}& & 12=1\cdot 10+2,& & 2=12-1\cdot 10.\end{array}$$ Orain, kontuan izanik $10$ dela aurreko hondarra, $10$ hori $250$ eta $12$ zenbakien konbinazio lineal bezala adieraz dezakegu: $$\begin{array}{ccccc}\begin{array}{cc}250& \underset{\_}{\mathrm{\backslash 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 \mathrm{𝟏}\mathrm{𝟎}=12-1\cdot (250-20\cdot 12)=(-1)\cdot 250+21\cdot 12.$$

2. $\text{zkh}(-250,12)=2=1\cdot (-250)+21\cdot 12.$ $\text{zkh}(250,-12)=2=(-1)\cdot 250+(-21)\cdot (-12).$ $\text{zkh}(-250,-12)=2=1\cdot (-250)+(-21)\cdot (-12).$

3. Euklidesen algoritmoa erabiliko dugu $\text{zkh}(250,111)$ kalkulatzeko eta $250$ eta $111$ zenbakien konbinazio lineal bezala adierazteko:

   $$\begin{array}{ccccc}\begin{array}{cc}250& \underset{\_}{\mathrm{\backslash vline}111}\\ 28& 2& \end{array}& & 250=2\cdot 111+28,& & 28=250-2\cdot 111;\\ \\ \begin{array}{cc}111& \underset{\_}{\mathrm{\backslash vline}28}\\ 27& 3& \end{array}& & 111=3\cdot 28+27,& & 27=111-3\cdot 28;\\ \\ \begin{array}{cc}28& \underset{\_}{\mathrm{\backslash vline}27}\\ 1& 1& \end{array}& & 28=1\cdot 27+1,& & 1=28-1\cdot 27;\\ \\ \begin{array}{cc}27& \underset{\_}{\mathrm{\backslash vline}1}\\ 0& 27& \end{array}& & 27=1\cdot 27.& & \end{array}$$

   $\text{zkh}(250,111)=1$; beraz, $250$ eta $111$ zenbaki lehen erlatiboak dira. $$\begin{array}{cc}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.23 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.24 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.25 Definizioa. [mktdef] Izan bitez $a,b,m\in {\mathbb{Z}}^{+}$, $m$ zenbakia $a$ eta $b$ zenbakien multiplo komun txikiena dela esango dugu ($m=\text{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\text{ eta }b\mid m.$

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

$(\mathrm{\forall }c\in {\mathbb{Z}}^{+})a\mid c,b\mid c⟹m\le c.$

4.26 Adibideak.

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

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

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

Froga.

Demagun $m=\text{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|c$ betetzen dela; kontraesan bat bilatuko dugu.

$m|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=\text{mkt}(a,b)⟹a\mid m$ ditugu; hortaz, $a\mid r$ ere beteko da.

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

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

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

4.28 Adibidea. $\text{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.29 Teorema. $a,b\in {\mathbb{Z}}^{+}$ izanik, $ab=\text{mkt}(a,b)\text{zkh}(a,b)$ betetzen da.

Froga.

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

$d=\text{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=\text{mkt}(a,b)$ denez, $m=k{\text{'}}_{1}a$ eta $m=k{\text{'}}_{2}b$ ditugu, $k{\text{'}}_1,k{\text{'}}_2\in \mathbb{Z}$ izanik.

1. $md\mid ab$:

   $ab=a{k}_{2}d=b{k}_{1}d⟹\frac{ab}{d}=a{k}_2=b{k}_1⟹\left\{\begin{array}{c}a\mid \frac{ab}{d}\\ \\ b\mid \frac{ab}{d}\end{array}\right\}⟹m\mid \frac{ab}{d}$

   (mkt Teoremaren arabera) $⟹md\mid ab.$

2. $ab\mid md$:

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

$\begin{array}{c}md\mid ab\\ ab\mid md\end{array}\}⟹ab=md\text{ edo }ab=-md⟹ab=md(ab,md\in {\mathbb{Z}}^{+}\text{ direlako)}.$ $◻$

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

4.30 Adibideak.

1. $\text{zkh}(250,12)=2$; hortaz, $\text{mkt}(250,12)=\frac{250\cdot 12}{2}=1500$ da.

2. $\text{zkh}(250,111)=1$; hortaz, $\text{mkt}(250,111)=250\cdot 111$ da.

3. $\text{zkh}(12,18)=6$; hortaz, $\text{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$, 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.31 Lema. [pab] $a,b,p\in {\mathbb{Z}}^{+}$ izanik, $p$ lehena izanik,

$p\mid ab⟹(p\mid a)\text{ edo }(p\mid b).$

Froga.

Demagun $p\mid ab$ betetzen dela; hau da, $ab=kp,k\in \mathbb{Z}\text{ izanik}.$

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

Horretarako, $p|a$ betetzen dela pentsatuko dugu eta, orduan, $p\mid b$ betetzen dela ikusiko dugu.

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

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

Orduan, hau lortuko dugu:

$\text{zkh}(a,p)=1⟹1=xa+yp,x,y\in \mathbb{Z}\text{ izanik }⟹$

$⟹b=xab+ypb=xkp+ypb=(xk+yb)p,xk+yb\in \mathbb{Z}\text{ izanik }⟹p\mid b.$ $◻$

4.32 Lema. [pab2] $a_1,\dots ,a_n,p\in {\mathbb{Z}}^{+}$ izanik, $p$ lehena izanik,

$p\mid a_1\cdots a_n⟹p\mid a_j,j\in \{1,\cdots ,n\}\text{ 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}.$

[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\text{ beteko da, }j\in \{1,\cdots ,k\}\subset \{1,\cdots ,k+1\}=\{1,\cdots ,n\}\text{ 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. $◻$

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

Irrazionala ez dela pentsatuko dugu. Orduan, ondoko hau idatzi ahal izango dugu:

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

Hortik,

$\sqrt{2}=\frac{a}{b}⟹2=\frac{a^2}{b^2}⟹2b^2=a^2⟹2\mid a^2=a\cdot a$

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

$2\mid a⟹a=2k,k\in \mathbb{Z}\text{ izanik }⟹4k^2=a^2=2b^2,k\in \mathbb{Z}\text{ izanik }⟹b^2=2k^2,k^2\in \mathbb{Z}\text{ izanik }⟹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 \text{zkh}(a,b)=1$ ere beteko da; baina hori ezinezkoa da.

4.34 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\text{ ezin da adierazi zenbaki lehenen biderketa bezala}\}.$

Absurdora eramanez, $S=\mathrm{\varnothing }$ dela frogatuko dugu. Horretarako, $S\ne \mathrm{\varnothing }$ 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\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=\mathrm{\varnothing }$ 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,\dots ,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,\dots ,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,\dots ,u$, izanik.

  Frogatu beharko dugu $r=u$ eta $p_i=q_i$, $s_i=t_i$ direla, $i=1,\dots ,r$ kasuetan.

  $p_1\mid k+1=q_1^{t_1}\cdots q_u^{t_u}$ betetzen denez eta $p_1$ zenbaki lehena denez, [pab2] Lemaren arabera, $p_1\mid q_j$ beteko da $j\in \{1,\dots ,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\ne 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, [pab2] Lemaren arabera, $q_1\mid p_i$ beteko da $i\in \{1,\dots ,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\le 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: $\{\begin{array}{c}{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}$

  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,\dots ,r$ guztietarako, eta $s_1-1=t_1-1$ (hots, $s_1=t_1$) eta $s_i=t_i$, $i=2,\dots ,r$ guztietarako.

$◻$

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

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

$\begin{array}{cc}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 euklidearra egitean lortuko den hondarrarekin erlazionatuko ditugu, eta hondar bereko elementuen multzoak hartuko ditugu kontuan. Horrez gain, multzo horietako elementuen arteko eragiketa aritmetikoak aztertuko ditugu.

4.2.1 n moduluko kongruentzia

[nmodkan] Atalean, $n$ moduluko kongruentziaren definizioa eman genuen:

$a\equiv b(\mathrm{mod}n)⟺n\mid a-b⟺\mathrm{\exists }k\in \mathbb{Z}/a=b+kn.$

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

Bestalde, [zateuk] Atalean, zatiketa euklidearraren [zateukteo] Teorema eman genuen:

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

$\begin{array}{cc}a& \underset{\_}{\mathrm{\backslash vline}b}\\ r& q\end{array}a=qb+r,0\le r<b.$

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

Oharrak.

1. Euklidesen teorema eta kongruentziaren definizioa kontutan izanik, $a\equiv b(\mathrm{mod}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}{cc}b& \underset{\_}{\mathrm{\backslash vline}n}\\ r& q\end{array}b=qn+r,0\le r<n.\begin{array}{cc}a& \underset{\_}{\mathrm{\backslash vline}n}\\ r& q+k\end{array}a=(q+k)n+r,0\le 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 ([nmodbalerl] Teorema: $n$ moduluko kongruentzia baliokidetasun-erlazioa da). Hau da, $\mathbb{Z}$ multzoari $n$ klase dituen partiketa eragiten dio erlazio honek.

4.2.2 Eragiketa modularrak

4.36 Definizioa. ${\mathbb{Z}}_n$ multzoan, batuketa eta biderketa modularra honela definitzen dira:

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

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

Zatiketa ez dago ${\mathbb{Z}}_n$ multzoko elementu guztietarako definituta, eta egin daitekeenean alderantzizko modularraz biderkatuz kalkulatu ohi da.

4.37 Definizioa. ${\mathbb{Z}}_n$ multzoan, $a$ elementua alderantzikagarria da $\mathrm{\exists }b\in {\mathbb{Z}}_n$, non $a\cdot b=1$ den. $b$ elementuari alderantzizko modularra deituko diogu eta $a^{-1}$ idatziko dugu.

Oharra. $\mathbb{Z}$ multzoko elementu guztiek ez dute alderantzizkorik, ez eta ${\mathbb{Z}}_n$ multzoko guztiek alderantzizko modularrik ere.

4.38 Teorema (Alderantzizko modularraren existentzia)

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

${\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/\text{zkh}(a,n)=1\}$.

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

Alderantzizko modularraren kalkulua Euklidesen algoritmoa erabiliz

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

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

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

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

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

4.2.4 Euler-en eta Fermat-en teoremak

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

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

1. $n$ zenbakia lehena bada, $\varphi (n)=n-1$ da.
2. $n=pq$ bada, $p$ eta $q$ bi zenbaki lehen desberdinak izanik, $\varphi (n)=(p-1)(q-1)$ da.
3. $n=p_1^{e_1}\cdots p_r^{e_r}$ moduan deskonposa daiteke, $p_1,\dots ,p_r$ lehen desberdinak izanik, $\varphi (n)=\frac{n}{p_1\dots p_r}(p_1-1)\dots (p_r-1)$ da.

4.41 Teorema. Euler-en teorema

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

4.42 Teorema. Fermat-en teorema txikia

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

4.43 Korolarioa. $a,n\in {\mathbb{Z}}^{+}$ badira, zkh$(a,n)=1$ izanik, $a^{-1}\equiv a^{\varphi (n)-1}(\mathrm{mod}n)$ betetzen da.

Froga.

Izan ere, $a^{\varphi (n)}=a\cdot a^{\varphi (n)-1}$ da eta $a^{\varphi (n)}\equiv 1(\mathrm{mod}n)$ betetzen da; beraz, $a\cdot a^{\varphi (n)-1}\equiv 1(\mathrm{mod}n)$ denez, $a$-ren alderantzizko modularra $a^{\varphi (n)-1}$ da.

Oharrak:

1. Berreketa modularra Euler-Fermat teoremak erabiliz kalkulatzea posible bada ere, gehienetan ez da praktikoa.
   • $\varphi (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\ge 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\text{ mod }n$ kalkulatzean:

• Zenbaki handiegien arazoa ekiditen da, ez dago $a^x$ kalkulatu beharrik, horrela eragiten delako. $((a\text{ mod }n)\cdot (b\text{ mod }n))\text{ mod }n=(a\cdot b)\text{ 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=\{\begin{array}{cc}a& x=1\text{ bada}\\ (a^{\frac{x}{2}}{)}^2& x\text{ bikoitia bada}\\ a{a}^{x-1}& x\text{ bakoitia bada}\end{array}$$

Berreketaren honako hiru propietateetan oinarritzen da:

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

4.3 RSA algoritmoa

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

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

4.3.1 RSA algoritmoaren jatorria

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

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

4.3.2 RSA algoritmoaren oinarri teorikoak

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

Teorema. Izan bedi $n=pq,$ non $p$ eta $q$ zenbaki lehenak diren, eta izan bitez $r\equiv s^{-1}(\mathrm{mod}\varphi (n))$ eta $a<\min \{p,q\}$, non $\varphi (n)=(p-1)(q-1)$ Eulerren funtzioa den. Orduan, $a\equiv a^{rs}(\mathrm{mod}n)$ beteko da.

Froga.

Teoreman zehaztu da $n$ zenbakia $p$ eta $q$ bi zenbaki lehenen biderketa dela; beraz, badakigu $\varphi (n)=(p-1)(q-1)$ dela. Bestalde, $r=s^{-1}(\mathrm{mod}\varphi (n))$ denez, alderantzizko modularraren definizioaren arabera, $rs(\mathrm{mod}\varphi (n))=1$ izango da eta, ondorioz, badakigu $k\in \mathbb{Z}$ badagoela, non $rs=1+k\varphi (n)$ beteko den; hortaz, $a^{rs}=a^{1+k\varphi (n)}$ beteko da.

Berdintza horretako bi aldeeetan $n$ modulua kalkulatzen badugu: $$a^{rs}(\mathrm{mod}n)=a^{1+k\varphi (n)}(\mathrm{mod}n)=a(a^{\varphi (n)}{)}^k(\mathrm{mod}n).$$ Badakigu, bestalde, Euler-Fermaten teoremaren arabera, $a$ eta $n$ zenbaki elkarrekiko lehenak edo zenbaki lehen erlatiboak badira, $a^{\varphi (n)}\text{mod }n\equiv 1$ dena. Kontuan izan behar da, $a<\min (p,q)$ dela eta $n$ zenbakiaren zatitzaile bakarrak $p$ eta $q$ direla. Hortaz, esan dezakegu $a$ eta $n$ zenbakiek ez dutela zatitzaile komunik, hau da, elkarrekiko lehenak direla. Ondorioz, Euler-Fermaten teorema aplikatuz, $$a^{rs}(\mathrm{mod}n)=a(a^{\varphi (n)}{)}^k(\mathrm{mod}n)=a(1{)}^k(\mathrm{mod}n)=a(\mathrm{mod}n).$$ berdintza lortuko dugu.

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

4.3.3 Gako publikoa eta gako pribatua

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

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

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

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

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

4.3.4 Gako publikoak eta pribatuak sortzeko prozedura

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

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

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

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

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

Laburbilduz, prozedurak urrats hauek ditu:

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

4.3.5 Mezu zifratua bidaltzeko prozedura

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

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

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

4.3.6 Mezu ziurtatua bidaltzeko prozedura

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

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