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 $\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 }\{0\}\dot{\cup }{\mathbb{Z}}^{+}.$$

• $\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, Erlazioen 3.3.2 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⟹x=y$.

  • Iragate-propietatea: $(\mathrm{\forall }x,y,z\in \mathbb{Z})x\le y\wedge y\le z⟹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}}^{\ast }$ multzoa $/$ 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, $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. $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, 4.3-5 Teoremaren arabera, $a$ zenbakiak $b$ eta $c$ zenbakien edozein konbinazio lineal zatituko du.

2. Propietate hori honela zabal daiteke: $b_1,\dots ,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,\dots ,n⟹(\mathrm{\forall }{x}_1,\dots ,x_n\in \mathbb{Z})a\mid x_1{b}_1+\cdots +x_n{b}_n.$$

4.4 Adibidea. 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\text{ den, }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. 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. Beraz, $S=\mathrm{\varnothing }$ da; eta, ondorioz, zenbaki konposatu orok zatitzaile lehenen bat dauka. $◻$ $◼$ $◻$

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\cdots p_k$, zenbaki lehenen biderkadura, eta $b=a+1$.

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

Orduan, $p_j\mid b$ eta $p_j\mid a$ betetzen dira; beraz, $p_j\mid 1b+(-1)a$ ere beteko da. Baina $1b+(-1)a=b-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

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. Zatiketa euklidearra

$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\}$ hondar positiboen 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:=minS$. $$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⟹c=a-(q+1)b>0⟹c\in S.$$ $r=minS$ denez, $c\ge r$ da; $c=r-b$ denez, $r-b\ge r⟹b\le 0$ lortuko dugu; eta hori ezinezkoa da $b>0$ delako.

$q$ eta $r$ bakarrak dira.

Demagun ez direla bakarrak, hau da, $$\mathrm{\exists }{q}_1,q_2,r_1,r_2\in \mathbb{Z},\text{ non }a=q_{1}b+r_1\text{ eta }a=q_{2}b+r_2\text{ den},$$ $0\le r_1<b$ eta $0\le r_2<b$ izanik. Orduan, $$q_{1}b+r_1=q_{2}b+r_2⟹(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. Adibide hauetan ematen diren zatidurak eta hondarrak existitzen dira eta bakarrak dira.

$$\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. $-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. Bien 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⟹c\mid d.$$

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

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

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

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

4.16 Propietateak.

1. $\text{zkh}(a,b)$ badago, $\text{zkh}(b,a)=\text{zkh}(a,b)$ beteko da.
2. $a\in {\mathbb{Z}}^{\ast }$ bada, $\text{zkh}(a,0)$ badagoela eta $\text{zkh}(a,0)=\mid a\mid$ betetzen dela froga daiteke.
   • $\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.17 Teorema. Zatitzaile komun handienaren existentzia

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

$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=minS$ 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}}^{+}$ beste zatitzaile komun bat izanik, $$\begin{array}{c}c\mid a\\ c\mid b\end{array}\}⟹c\mid xa+yb=d⟹c\le d,$$ zenbaki oso batek bi zenbaki zatitzen baditu, horien edozein konbinazio lineal zatituko duelako. $◻$ $◼$ $◻$

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

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

Horretarako, izan bedi $d=\text{zkh}(\mid a\mid ,\mid b\mid )$ (badakigu existitzen dela); 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}}^{+}$ beste zatitzaile komun bat 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⟹c\le d,$$ $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\ne 0$ edo $b\ne 0$ izanik, $\mathrm{\exists }x,y\in \mathbb{Z}$, non $\text{zkh}(a,b)=xa+yb$ baita. Horrez gain, $\text{zkh}(a,b)$ da $a$ eta $b$ zenbakien konbinazio lineal moduan adieraz daitekeen zenbaki oso positiborik txikiena.

$$\text{zkh}(a,b)=min\{xa+yb/x,y\in \mathbb{Z}\text{ 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 $\text{zkh}(a,b)=\text{zkh}(\mid a\mid ,\mid b\mid )$ dela kontuan hartzea konbinazio lineal positiboen $S$ eta $S^{\prime }$ multzoak berdinak direla frogatzea, hots, berdintza hau betetzen dela:

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

$\supseteq$ )

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 partekotasun hau aterako dugu: $$S^{\prime }=\{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\}=S.$$

$\subseteq$ )

$S\subseteq S^{\prime }$ beste partekotasuna antzeko eran frogatuko genuke. $◻$ $◼$ $◻$

Bézouten leman agertzen diren $x$ eta $y$ koefizienteak ez dira bakarrak; esate baterako, $\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.19 Adibidea. 4.12 Adibidean ikusi dugu $\text{zkh}(24,32)=8$ dela eta 4.17 Teoremaren oharrean $\text{zkh}(-24,32)=\text{zkh}(24,32)$ dela frogatu dugu; hortaz, $$\text{zkh}(24,32)=\text{zkh}(-24,32)=8.$$

Bestalde, Bezouten lemari esker badakigu $\mathrm{\exists }x,y\in \mathbb{Z}$, non $\text{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=\text{zkh}(a,b)$ bada, $d$ zenbakia $a$ eta $b$ zenbakien konbinazio lineala dela, hau da, $$d=\text{zkh}(a,b)⟹d=xa+yb,x,y\in \mathbb{Z}\text{ izanik}.$$

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

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

Kasu horrek hurrengo definiziora garamatza:

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

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

4.22 Adibidea.

1. $x=-2$ eta $y=2$ hartuz, $16=(-2)24+2\cdot 32.\text{ Hortaz,}\text{zkh}(24,32)\le 16\text{ da}.$
2. Orain, $a=3$ eta $b=4$ zenbakiak hartuz, $1=(-1)3+1\cdot 4$ dugu. Hortaz, $\text{zkh}(3,4)=1$ eta $3$ eta $4$ 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}).$$

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

Froga.

Berdintza hauek dauzkagu:

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

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

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

Eta horrez gain, beste hau ere badugu:

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

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

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

   • Badakigu $r_k\mid r_k$ betetzen dela, $r_k\ne 0$ izanik.

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

   • $r_k\mid r_{k-2}$ frogatzeko, (4.2) 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: (4.2) 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.

   (4.2) 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{ (4.4) }$$

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

4.25 Adibideak.

1. 4.24 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{𝟏𝟎}=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.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=\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.$$
2. $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.29 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.30 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⟹m\mid c.$

Froga.

Demagun $m=\text{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|̸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.31 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.32 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}$

   (4.30 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.33 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

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⟹(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.35 Lema. $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}.$

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

4.34 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.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\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=minS$. $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=minS$ eta $m_2<m=minS$ 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, 4.35 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, 4.35 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.38 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 (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(\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, 4.1.3 Atalean, zatiketa euklidearraren 4.9 Teorema eman genuen:

$a,b\in \mathbb{Z}$ izanik, $b>0$, $\mathrm{\exists }!q\in \mathbb{Z}\mathrm{\exists }!r\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. Zatiketa euklidearra 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,\mathrm{...},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(\mathrm{mod}n))+(b(\mathrm{mod}n))=(a+b)(\mathrm{mod}n).$

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

Definizioak esaten digu ${\mathbb{Z}}_n$ multzoko $a(\mathrm{mod}n)$ eta $b(\mathrm{mod}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(\mathrm{mod}n)$ den, $b$ elementuari $a$ elementuaren aurkako modularra deituko diogu eta $-a$ idatziko dugu.
2. ${\mathbb{Z}}_n$ multzoan, $a$ elementua alderantzikagarria da $\mathrm{\exists }b\in {\mathbb{Z}}_n$, non $a\cdot b\equiv 1(\mathrm{mod}n)$ den. $b$ elementuari $a$ elementuaren alderantzizko modularra deituko diogu eta $a^{-1}$ idatziko dugu.

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

$(a(\mathrm{mod}n))-(b(\mathrm{mod}n))=(a+(-b))(\mathrm{mod}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(\mathrm{mod}n))÷(b(\mathrm{mod}n))=(a\cdot (b^{-1}))(\mathrm{mod}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\text{ eta }10/3.$$

Formalki honela egingo genuke:

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

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

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

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

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

Idazkera sinplifikatuz, honela egingo dugu: $5+7=12\equiv 0(\mathrm{mod}12).$

Eta horrela egingo dugu kasu praktikoetan.

4.42 Teorema. Alderantzizko modularraren existentzia

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

Froga.

$⟹:$

$\mathrm{\exists }x=a^{-1}(\mathrm{mod}n)⟹xa\equiv 1(\mathrm{mod}n)⟹n\mid xa-1⟹\mathrm{\exists }y\in \mathbb{Z}/xa-1=yn⟹xa-yn=1⟹\text{zkh}(a,n)=1.$

$⟸$ :

$\text{zkh}(a,n)=1⟹\mathrm{\exists }x,y\in \mathbb{Z},\text{ non }xa+yn=1\text{den}$. Hortik, $xa-1=yn⟹n\mid xa-1⟹xa\equiv 1(\mathrm{mod}n)⟹\mathrm{\exists }x=a^{-1}(\mathrm{mod}n)$. $◻$ $◼$ $◻$

${\mathbb{Z}}_n$ multzoan alderantzikagarri diren elementuen multzoari hondarren multzo murriztu deitzen zaio eta ${\mathbb{Z}}_n^{\ast }$ idatziko dugu: ${\mathbb{Z}}_n^{\ast }=\{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 modularra kalkulatzeko bidea:

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

4.18 Bézouten lematik 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}=x(\mathrm{mod}n).$

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

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

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

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

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

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

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

$$\begin{array}{ccccc}\begin{array}{cc}12& \underset{\_}{\mathrm{\backslash vline}5}\\ 2& 2& \end{array}& & 12=2\cdot 5+2,& & 2=12-2\cdot 5;\\ \\ \begin{array}{cc}5& \underset{\_}{\mathrm{\backslash vline}2}\\ 1& 2& \end{array}& & 5=2\cdot 2+1,& & 1=5-2\cdot 2;\\ \\ \begin{array}{cc}2& \underset{\_}{\mathrm{\backslash 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(\mathrm{mod}12)$ da.

Egiazta daiteke hori: $5\cdot 5^{-1}=5\cdot 5=25\equiv 1(\mathrm{mod}12).$

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

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

$$\begin{array}{ccccc}\begin{array}{cc}12& \underset{\_}{\mathrm{\backslash vline}7}\\ 5& 1& \end{array}& & 12=1\cdot 7+5,& & 5=12-1\cdot 7;\\ \\ \begin{array}{cc}7& \underset{\_}{\mathrm{\backslash vline}5}\\ 2& 1& \end{array}& & 7=1\cdot 5+2,& & 2=7-1\cdot 5;\\ \\ \begin{array}{cc}5& \underset{\_}{\mathrm{\backslash vline}2}\\ 1& 2& \end{array}& & 5=2\cdot 2+1,& & 1=5-2\cdot 2;\\ \\ \begin{array}{cc}2& \underset{\_}{\mathrm{\backslash 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(\mathrm{mod}12)$ da. Baina, $5$aren aurkakoa $7$ da ${\mathbb{Z}}_{12}$ multzoan, $5+7=12\equiv 0(\mathrm{mod}12)$ delako. Hortaz, $7^{-1}\equiv 7(\mathrm{mod}12)$ da.

4.2.2 Berreketa modularra

$\mathbb{Z}$ multzoan, $a^x$ berreketa, $a,x\in \mathbb{Z}$ eta $x\ge 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(\mathrm{mod}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(\mathrm{mod}n))\cdot (b(\mathrm{mod}n))=(a\cdot b)(\mathrm{mod}n).$$

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

Berreketa bitarraren metodoa

• Berreketaren honako hiru propietateetan oinarritzen da:

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

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

$$a^x=\{\begin{array}{cc}a,& x=1\text{ bada,}\\ (a^{\frac{x}{2}}{)}^2,& x\text{ bikoitia bada,}\\ a\cdot a^{x-1},& x\text{ bakoitia bada.}\end{array}$$

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(\mathrm{mod}12)$ eta $7^2=49\equiv 1(\mathrm{mod}12)$ dira. Hortaz,

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

• $7^9=7\cdot ((7^2{)}^2{)}^2\equiv 7\cdot ((1{)}^2{)}^2=7\cdot (1{)}^2=7\cdot 1=7=7(\mathrm{mod}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(\mathrm{mod}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(\mathrm{mod}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(\mathrm{mod}17),$ $36\equiv 2(\mathrm{mod}17)$ izanik.

Hortaz, $6^{52}\equiv 4(\mathrm{mod}17)$ da.

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

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

4.48 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 badaiteke, $p_1,\dots ,p_r$ zenbaki lehen desberdinak izanik, $\varphi (n)=\frac{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, $\text{zkh}(a,n)=1$. Kasu horretan $a^{\varphi (n)}\equiv 1(\mathrm{mod}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, $\varphi (75)=\frac{75}{3\cdot 5}(3-1)(5-1)=\frac{75}{15}(2)(4)=40$ da.

Eulerren teoremak dio $a^{40}\equiv 1(\mathrm{mod}75)$ betetzen dela, $\text{zkh}(a,75)=1$ bada; gure kasuan, $\text{zkh}(22,75)=1$ denez, $22^{40}\equiv 1(\mathrm{mod}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(\mathrm{mod}75),$ $484\equiv 34(\mathrm{mod}75)$ izanik.

Ondorioz, $22^{83}\equiv 73(\mathrm{mod}75)$ da.

4.51 Korolarioa. $a,n\in {\mathbb{Z}}^{+}$ badira, $\text{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. $◻$ $◼$ $◻$

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

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

Beraz, $5^{-1}\equiv 5^{\varphi (12)-1}(\mathrm{mod}12)$ eta $7^{-1}\equiv 7^{\varphi (12)-1}(\mathrm{mod}12)$ izango dira.

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

• $5^{-1}\equiv 5^{4-1}(\mathrm{mod}12)=5^3=125\equiv 5(\mathrm{mod}12).$

• $7^{-1}\equiv 7^{4-1}(\mathrm{mod}12)=7^3=7\cdot (7^2)=7\cdot 49\equiv 7\cdot 1=7\equiv 7(\mathrm{mod}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.
   • $\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.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}(\mathrm{mod}\varphi (n))$ betetzen dutenak, non $\varphi (n)=(p-1)(q-1)$ Eulerren funtzioa den. Orduan, $a^{ed}\equiv a(\mathrm{mod}n)$ da, $a<min\{p,q\}$ guztietarako.

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

$n$ moduluko kongruentzian zera daukagu:

$a^{ed}\equiv a^{1+k\varphi (n)}\equiv a(a^{\varphi (n)}{)}^k(\mathrm{mod}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^{\varphi (n)}\equiv 1(\mathrm{mod}n)$ denez, $a^{ed}\equiv a(a^{\varphi (n)}{)}^k\equiv a(1{)}^k\equiv a(\mathrm{mod}n).$ $◻$ $◼$ $◻$

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 $\varphi (n)=(7-1)(13-1)=72$ da. Egiazta dezagun $29\equiv 5^{-1}(\mathrm{mod}\varphi (91))$ edo $5\equiv 29^{-1}(\mathrm{mod}\varphi (91))$ dela. Alegia, $5$ eta $29$ elkarren alderantzizkoak direla $\varphi (91)=72$ moduluko kongruentzian.

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

$$\begin{array}{ccccc}\begin{array}{cc}72& \underset{\_}{\mathrm{\backslash vline}29}\\ 14& 2& \end{array}& & 72=2\cdot 29+14,& & 14=72-2\cdot 29;\end{array}$$

$$\begin{array}{ccccc}\begin{array}{cc}29& \underset{\_}{\mathrm{\backslash vline}14}\\ 1& 2& \end{array}& & 29=2\cdot 14+1,& & 1=29-2\cdot 14.\end{array}$$

Beraz, $\text{zkh}(29,72)=1$ da eta alderantzizko modularraren existentziaren teoremagatik (ikus 4.42 Teorema) $\mathrm{\exists }29^{-1}(\mathrm{mod}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\to 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\varphi (n)$ da, $k=2$ izanik.

Egiazta dezagun $a^{ed}\equiv a(\mathrm{mod}n)$ dela. Eulerren teorematik (ikus 4.49 Teorema) $a^{72}\equiv 1(\mathrm{mod}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(\mathrm{mod}91).$

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

• Lehenik, $a^e(\mathrm{mod}n)=6^5(\mathrm{mod}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(\mathrm{mod}91).$

• Orain, $(a^e{)}^d(\mathrm{mod}n)$ kalkulatuko dugu, hau da, $41^{29}(\mathrm{mod}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(\mathrm{mod}91).$ Espero zitekeen bezala, $(6^5{)}^{29}\equiv 6(\mathrm{mod}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\ne 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). $\varphi (n)=(p-1)(q-1)$ izanik, $\varphi (n)$ zenbakiarekin lehen erlatiboa den $e$ zenbaki bat aurkitu behar da, hau da, $\text{zkh}(\varphi (n),e)=1$ beteko duena. $e$ handia aukeratzea gomendatzen da.
• Gako pribatua kalkulatu ($d$ zenbakia). $\varphi (n)$ moduluko kongruentzian $e$ gako publikoaren alderantzizkoa den $d$ balioa kalkulatu behar da, hau da, $d=e^{-1}(\mathrm{mod}\varphi (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(\mathrm{mod}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(\mathrm{mod}n).$

Aukeratu ditugun gakoek 4.53 Teoremaren baldintzak betetzen dituztenez, $a\equiv z^d\equiv (a^e{)}^d(\mathrm{mod}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$ $\to$ $n=391.$
• Gako publikoa ($n,e$). $n=391$ zenbakirako $e$ egoki bat aukeratu behar du.
  • $\varphi (n)=(p-1)(q-1)=16\cdot 22=352\to \varphi (n)=352.$
  • $\text{zkh}(\varphi (n),e)=1\to \text{zkh}(352,e)=1.$ $e$ baliorako aukera bat baino gehiago existitzen da. $\varphi (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(\mathrm{mod}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\to 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⟹z_1=a_1^e(\mathrm{mod}n)=107^3(\mathrm{mod}391)=40.$
• $a_2=97⟹z_2=a_2^e(\mathrm{mod}n)=97^3(\mathrm{mod}391)=79.$
• $a_3=105⟹z_3=a_3^e(\mathrm{mod}n)=105^3(\mathrm{mod}391)=265.$
• $a_4=120⟹z_4=a_4^e(\mathrm{mod}n)=120^3(\mathrm{mod}391)=171.$
• $a_5=111⟹z_5=a_5^e(\mathrm{mod}n)=111^3(\mathrm{mod}391)=304.$

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

Mezua deszifratzea ($z_i\to a_i$)

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

• $z_1=40⟹a_1=z_1^d(\mathrm{mod}n)=40^{235}(\mathrm{mod}391)=107.$
• $z_2=79⟹a_2=z_2^d(\mathrm{mod}n)=79^{235}(\mathrm{mod}391)=97.$
• $z_3=265⟹a_3=z_3^d(\mathrm{mod}n)=265^{235}(\mathrm{mod}391)=105.$
• $z_4=171⟹a_4=z_4^d(\mathrm{mod}n)=171^{235}(\mathrm{mod}391)=120.$
• $z_5=304⟹a_5=z_5^d(\mathrm{mod}n)=304^{235}(\mathrm{mod}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, $\text{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(\mathrm{mod}n)$

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

$a=z^e(\mathrm{mod}n).$

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