MD-liburua/Zenbaki-teoria-en iturria ikusi

= 4. Gaia: Zenbaki-teoria =


== 4.1 Zenbaki osoak ==

=== 4.1.1 Eragiketak zenbaki osoen artean. Ordena onaren printzipioa ===

Atal honetan, [[#multzo|[multzo]]] atalean aipatu genuen zenbaki osoen <math display="inline">\Z</math> multzoa aztertuko dugu, baita bertan defini daitezkeen eragiketak eta <math display="inline">\leq</math>, “txikiago edo berdin” ordena-erlazioa ere.

<ul>
<li><p>
Gogora dezagun <math display="inline">\Z</math> multzoa azpimultzo disjuntutan deskonposa daitekeela, honela: <math display="block">\Z = \Z^+ \, \dot{\cup}\, \Z^- \, \dot{\cup} \, \{0\}.</math>
</p></li>
<li><p>
<math display="inline">\Z</math> multzoa itxia da <math display="inline">(+)</math> batuketarako, <math display="inline">(\cdot)</math> biderketarako eta <math display="inline">(-)</math> kenketarako: <math display="block">x, y \in \Z \, \Longrightarrow \, x + y, \, x \cdot y, \, x - y \, \in \Z;</math> baina ez da itxia <math display="inline">(/)</math> zatiketarako; adibidez: <math display="inline">2,3 \in \Z</math>, baina <math display="inline">\dfrac{2}{3}\not \in \Z</math>.
</p>
<p>
Hala ere, zatiketa murriztua, zatiketa euklidearra, definituko dugu <math display="inline">\Z</math> multzoan, eta <math display="inline">\Z^+</math> multzoaren elementu berezi batzuetan, ''zenbaki lehenak'', jarriko dugu arreta.
</p></li>
<li><p>
Bestalde, <math display="inline">\leq</math> ordena-erlazioa da <math display="inline">\Z</math> multzoan, [orderl] atalean definitu ditugun propietateak betetzen dituelako:</p>
<ul>
<li><p>Bihurtze-propietatea: <math display="inline">(\forall x \in \Z) \quad x \leq x</math>.</p></li>
<li><p>Antisimetria-propietatea: <math display="inline">(\forall x,y \in \Z) \quad x \leq y \; \wedge \; y \leq x \; \Rightarrow \; x = y</math>.</p></li>
<li><p>Iragate-propietatea: <math display="inline">(\forall x, y, z \in \Z) \quad x \leq y \; \wedge \; y \leq z \; \Rightarrow \; x \leq z</math>.</p></li></ul>
<p>
Are gehiago, ordena osoko erlazioa da; hau da, <math display="inline">\leq</math> ordena-erlazioak osoki ordenatzen du <math display="inline">\Z</math> multzoa; horrek esan nahi du, <math display="inline">x</math> eta <math display="inline">y</math> zeinahi zenbaki osoak izanik, beti ordenatu ahal izango ditugula: 
<math display="block">(\forall x, y \in \Z) \quad x \leq y \, \vee \, y \leq x.</math></p>
<p><math display="inline">\leq</math> ordena-erlazioaren propietate horiek <math display="inline">\Q</math> eta <math display="inline">\R</math> multzoetan ere betetzen dira. <math display="inline">\N</math> edo <math display="inline">\Z^{+}</math> multzoa <math display="inline">\Q^+</math> eta <math display="inline">\R^+</math> multzoetatik bereizten duena da lehena multzo <span>'''ongi ordenatua'''</span> dela, bestela esanda, <span>'''ordena onaren printzipioa'''</span> betetzen dela: <math display="inline">\N</math> edo <math display="inline">\Z^+</math> multzoaren edozein azpimultzo ez-hutsek elementu minimo bat dauka.</p>
<p>Printzipio hori ez da <math display="inline">\Q^+</math> multzoan betetzen, ezta <math display="inline">\R^+</math> multzoan ere. Esate baterako, <math display="block">(0,8) = \{ x \in \R \; / \; 0 < x < 8 \}</math> tarte irekia <math display="inline">\R^+</math> multzoaren azpimultzo ez-hutsa da, baina ez du elementu minimorik. Hori frogatzeko, demagun tarteak <math display="inline">m</math> elementu minimoa duela. Orduan, <math display="inline">0 < m < 8</math>; hortik, <math display="inline">0 < \dfrac{m}{2} < 4 < 8</math> dugu, <math display="inline">\dfrac{m}{2} \in (0,8)</math> izanik. Baina <math display="inline">\dfrac{m}{2} < m</math> betetzen da; beraz, kontraesan batera heldu gara, <math display="inline">m</math> baita <math display="inline">(0,8)</math> tartearen minimoa.</p></li></ul>

=== 4.1.2 Zatigarritasuna. Zenbaki lehenak ===

<br />
<math display="inline">\Z^*</math> multzoa <math display="inline">/</math> zatiketarako itxia ez bada ere, badira kasu batzuk non zenbaki oso batek beste bat zehazki zatitzen duen. Esaterako, <math display="inline">4</math>ak <math display="inline">12</math>a zehazki zatitzen du (<math display="inline">12 = 3 \cdot 4</math>). Hau da, <math display="inline">12</math> zati 4 egitean, zatidura gisa <math display="inline">3</math> eta hondar gisa <math display="inline">0</math> zenbaki osoak lortuko ditugu.

<br />
<span>'''4.1 Definizioa.''' </span> <span id="etikzatigarri" label="etikzatigarri"></span>
<math display="inline">a, b \in \Z</math> zenbakiak izanik, <math display="inline">a \neq 0</math> izanik, <math display="inline">a</math> zenbakiak <math display="inline">b</math> zenbakia '''zatitzen du''', eta <math display="inline">a \mid b</math> adieraziko dugu, baldin <math display="block">\exists k \in \Z, \; \mbox{ non } \; b = ka \mbox{ den. }</math> Hori gertatzen denean, <math display="inline">a</math> zenbakia <math display="inline">b</math> zenbakiaren <span>'''zatitzaile'''</span> bat dela esango dugu, edo <math display="inline">b</math> zenbakia <math display="inline">a</math> zenbakiaren <span>'''multiplo'''</span> bat dela.
<br />

'''Hitzarmena.''' <math display="inline">a \mid b</math> idazten dugunean, <math display="inline">a \neq 0</math> dela pentsatuko dugu.

'''4.2 Lema.''' <math display="inline">a,b \in \Z^{+}</math> bada, <math>a \mid b \implies a \leq b</math>.

Ondoko teoreman zatigarritasunaren propietate batzuk frogatuko ditugu.

<span>'''4.3 Teorema.''' </span> <span id="propietateak" label="propietateak">[propietateak]</span> <math display="inline">a,b,c \in \Z</math> izanik,
<ol>
<li>
<math display="inline">1 \mid a</math>; <math display="inline">a \mid a</math>; <math display="inline">a \mid 0</math>. (<math display="inline">a \neq 0</math>)
</li>
<li>
<math display="inline">(a \mid b) \; \wedge \;  (b \mid a) \implies a =b \; \vee \;a =-b</math>. (<math display="inline">a\neq 0, b\neq 0</math>)
</li>
<li>
<math display="inline">(a \mid b) \; \wedge \;  (b \mid c) \implies a \mid c</math>. (<math display="inline">a\neq 0, b\neq 0</math>)
</li>
<li>
<math display="inline">a \mid b \implies (\forall x \in \Z) \; \; a \mid xb</math>. (<math display="inline">a\neq 0</math>)
</li>
<li>
<math display="inline">(a \mid b) \wedge  (a \mid c) \implies (\forall x,y  \in \Z ) \; \;  a \mid xb+yc</math>. (<math display="inline">a\neq 0</math>)
</li>
</ol>

<span>'''Froga.''' </span>

<ol>
<li>
<math display="inline">a = 1a.</math> da; beraz, <math display="inline">1 \mid a</math> eta <math display="inline">a \mid a</math>. Bestalde, <math display="inline">0 = 0a.</math> da; beraz, <math display="inline">a \mid 0</math>.
</li>
<li>
Hasteko, <math display="inline">(a \mid b) \; \wedge \;  (b \mid a) </math> daukagu, hau da, 
<math display="block">\left. 
\begin{array}{c}
      a \mid b \\
      \wedge \\
      b \mid a
\end{array} \right\} \implies 
\left. \begin{array}{c}
             b = k_1a, \; k_1 \in \Z \mbox{ izanik} \\
             \wedge \\
             a = k_2b, \; k_2 \in \Z \mbox{ izanik}
\end{array} \right\} \implies 
b = k_1(k_2b) = (k_1k_2)b,</math><math display="block">k_1, k_2 \in \Z \mbox{ izanik} \implies k_1k_2 = 1, \; k_1, k_2 \in \Z \mbox{ izanik} \implies 
\left. \begin{array}{c}
             k_1 = k_2 = 1 \\
             \vee \\
             k_1 = k_2 = -1
       \end{array} \right\} \implies 
\left. \begin{array}{c}
             a = b \\
             \vee \\
             a = -b.
\end{array} \right.</math>
</li>
<li>
Kasu honetan <math display="inline">(a \mid b) \; \wedge \;  (b \mid c) </math> daukagu, 
<math display="block">\left. 
\begin{array}{c}
      a \mid b \\
      \wedge \\
      b \mid c
\end{array} \right\} \implies 
\left. \begin{array}{c}
             b = k_1a, \; k_1 \in \Z \mbox{ izanik} \\
             \wedge \\
             c = k_2b, \; k_2 \in \Z \mbox{ izanik}
\end{array} \right\} \implies 
c = k_2(k_1a) = (k_2k_1)a,</math> <math display="inline">k_2k_1 \in \Z \mbox{ izanik } \implies a \mid c</math>.
</li>
<li>
Edozein <math display="inline">x \in \Z</math> izanik, <math display="block">a \mid b \implies b = ka, \; k \in \Z \mbox{ izanik} \implies xb = x(ka) = (xk)a, \; xk \in \Z \mbox{ izanik} \implies a \mid xb.</math>
</li>
<li>
Edozein <math display="inline">x,y \in \Z</math> izanik, 
<math display="block">\left. 
\begin{array}{c}
      a \mid b \\
      \wedge \\
      a \mid c
\end{array} \right\} \implies 
\left. \begin{array}{c}
             b = k_1a, \; k_1 \in \Z \mbox{ izanik} \\
             \wedge \\
             c = k_2a, \; k_2 \in \Z \mbox{ izanik}
\end{array} \right\} \implies 
xb + yc = x(k_1a) + y(k_2a) =</math> <math display="block">
= (xk_1 + yk_2)a, \; xk_1 + yk_2 \in \Z \mbox{ izanik } \implies a \mid xb + yc.</math> <math display="inline">\Box</math>
</li>
</ol>

<span>'''Oharrak.''' </span>
<ol>
<li><p>
<math display="inline">b, c \in \Z</math> emanik, <math display="block">xb + yc, \quad x,y \in \Z \mbox{ izanik},</math> adierazpenari <math display="inline">b, c \in \Z</math> zenbakien '''konbinazio lineal''' deituko diogu.</p>
<p><math display="inline">a</math> zenbakiak <math display="inline">b</math> eta <math display="inline">c</math> zenbakiak zatitzen baditu, [[#propietateak|[propietateak]]]-5 Teoremaren arabera, <math display="inline">a</math> zenbakiak <math display="inline">b</math> eta <math display="inline">c</math> zenbakien edozein konbinazio lineal zatituko du.
</p></li>
<li><p>
Propietate hori honela zabal daiteke: <math display="inline">b_1, \cdots, b_n \in \Z</math> izanik, <math display="block">x_1b_1 + \cdots + x_nb_n, \quad x_1, \ldots, x_n \in \Z \mbox{ izanik},</math> adierazpenari <math display="inline">b_1, \ldots, b_n</math> zenbakien '''konbinazio lineal''' deituko diogu.</p>
<p><math display="inline">a</math> zenbakiak <math display="inline">b_1, \ldots, b_n</math> zenbakiak zatitzen baditu, <math display="inline">a</math> zenbakiak <math display="inline">b_1, \ldots, b_n</math> zenbakien edozein konbinazio lineal zatituko du: <math display="block">a \mid b_i, \; i = 1, \cdots, n \implies (\forall x_1, \cdots, x_n  \in \Z )\quad  a \mid x_1b_1 + \cdots + x_nb_n.</math></p></li></ol>

<span>'''4.4 Adibidea.''' </span><span id="Grimaldi4.20" label="Grimaldi4.20">[Grimaldi4.20]</span> Ba al daude <math display="inline">5x + 10y + 20z = 1003</math> ekuazioa betetzen duten zenbaki osoak?

Demagun <math display="inline">x, y, z</math> zenbaki oso horiek existitzen direla. <math display="inline">5 \mid 5</math>, <math display="inline">5 \mid 10</math> eta <math display="inline">5 \mid 20</math> betetzen direnez, <math display="inline">5 \mid 1003</math> ere beteko litzateke; baina hori ez da gertatzen. Hortaz, ez daude ekuazioa betetzen duten <math display="inline">x, y, z</math> zenbaki osoak.

<span>'''4.5 Definizioa.''' </span> Izan bedi <math display="inline">n \in \Z^{+}</math>, <math display="inline">n > 1</math>.

<math display="inline">n</math> <span>'''zenbaki lehena'''</span> dela esango dugu  bere zatitzaile positibo bakarrak <math display="inline">n</math> eta <math display="inline">1</math> badira: <math display="block">m \mid n, \quad m \in \Z^{+} \, \Longrightarrow \, m = 1 \, \vee \, m = n.</math>
Eta <math display="inline">n</math> <span>'''zenbaki konposatua'''</span> dela esango dugu ez bada lehena: <math display="block">\exists m_1, m_2 \in \Z^{+} \; \mbox{ non }\;   n = m_1m_2, \, \quad 1 < m_1 < n, \; 1 < m_2 < n.</math>

<span>'''4.6 Adibidea.''' </span> <math display="inline">12</math> zenbaki konposatua da, <math display="inline">12 > 1</math> delako eta <math display="inline">1</math>, <math display="inline">2</math>, <math display="inline">3</math>, <math display="inline">4</math>, <math display="inline">6</math> eta <math display="inline">12</math> zatitzaileak dituelako.

<math display="inline">11</math> zenbaki lehena da, <math display="inline">11 > 1</math> delako eta bere zatitzaile positibo bakarrak <math display="inline">1</math> eta <math display="inline">11</math> direlako.


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

<span>'''4.7 Teorema.''' </span> <span id="lekon" label="lekon">[lekon]</span> Zenbaki konposatu orok zatitzaile lehenen bat dauka. Hau da, <math display="inline">n \in \Z^{+}</math>, <math display="inline">n > 1</math> izanik, <math display="block">n \, \mbox { konposatua } \, \Longrightarrow \exists p \in \Z^{+}, \, p  \, \mbox { lehena eta } \, p \mid n.</math>

<span>'''Froga.'''</span>

Izan bedi <math display="inline">S</math> zatitzaile lehenik ez duten zenbaki oso konposatu guztien multzoa: <math display="block">S = \{ x \in \Z^{+} \; / \; x \; \mbox{ konposatua da eta ez du zatitzaile lehenik} \}.</math> Absurdora eramanez, <math display="inline">S = \emptyset</math> dela frogatuko dugu.

Demagun <math display="inline">S \neq \emptyset</math> dela. <math display="inline">S</math> multzoa <math display="inline">\Z^{+}</math> multzoaren azpimultzo ez-hutsa denez, ordena onaren printzipioaren arabera, <math display="inline">S</math> multzoak elementu minimoa izango du, <math display="inline">m</math>.

<math display="inline">m \in S</math> denez, <math display="inline">m</math> konposatua da; beraz, <math display="inline">m_1, m_2 \in \Z^{+}</math> badaude, non <math display="inline">m = m_1m_2</math> den, <math display="inline">1 < m_1 < m, \; 1 < m_2 < m</math> izanik.

<math display="inline">m</math> da <math display="inline">S</math> multzoaren minimoa eta <math display="inline">m_1 < m</math> da; beraz, <math display="inline">m_1 \not \in S</math> beteko da. Hortaz, <math display="inline">m_1</math> lehena da edo zatitzaile lehenen bat dauka.

<math display="inline">m_1</math> lehena bada, <math display="inline">m_1</math> lehena da eta <math display="inline">m_1 \mid m</math> betetzen da.

<math display="inline">m_1</math> zenbakiak <math display="inline">p</math> zatitzaile lehen bat badauka, <math display="inline">p</math> lehena da eta <math display="inline">p \mid m_1</math> eta <math display="inline">m_1 \mid m</math>; hortaz, <math display="inline">p \mid m</math>.

Bi kasuetan kontraesan bat aurkitu dugu, <math display="inline">m</math> zenbakiak ez baitauka zatitzaile lehenik. Hortaz, <math display="inline">S = \emptyset</math> da; eta, ondorioz, zenbaki konposatu orok zatitzaile lehenen bat badauka. <math display="inline">\Box</math>

<span>'''4.8 Teorema.''' </span> (Euklides, Elementuak, IX, 20)

Infinitu zenbaki lehen daude.

<span>'''Froga.''' </span>

Absurdora eramanez frogatuko dugu.

Jo dezagun zenbaki lehenen kopurua finitua dela: <math display="inline">p_1, \ldots, p_k</math>.

Izan bitez <math display="inline">a = p_1 \ldots p_k</math> eta <math display="inline">A = a + 1</math>.

Orduan, <math display="inline">p_i \mid a</math>, <math display="inline">i = 1, \ldots, k</math> dugu eta, beraz, <math display="inline">a \geq p_i</math>, <math display="inline">i = 1, \ldots, k</math>; hortik <math display="inline">A \neq p_i</math>, <math display="inline">i = 1, \ldots, k</math> aterako dugu. Beraz, <math display="inline">A</math> konposatua da. [[#lekon|[lekon]]] Teoremaren arabera, badago <math display="inline">p_j \in \{p_1, \ldots, p_k\}</math> zenbaki lehenen bat, non <math display="inline">p_j \mid A</math> betetzen den.

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

Hortaz, zenbaki lehenen kopuruak ezin du kopuru finitua izan. Hau da, infinitu zenbaki lehen daude. <math display="inline">\Box</math>

=== 4.1.3 </span><span id="zatiketa_euklidearra" label="zatiketa_euklidearra">Zatiketa euklidearra</span> ===

[zateuk]

Hurrengo emaitzak aukera emango digu <math display="inline">0</math> ez diren zenbaki osoen arteko zatiketarekin lan egiteko, zatiketa zehatza ez denean.

Adibidez, <math display="inline">38</math> zati <math display="inline">7</math> egiten badugu, zatidura <math display="inline">5</math> eta hondarra <math display="inline">3</math> aterako ditugu. Euklidesek (K. a. 300) frogatu zuen,   <math display="inline">a</math> eta <math display="inline">b</math> bi zenbaki oso izanik, <math display="inline">b \neq 0</math> izanik, zatidura bakar bat, <math display="inline">q</math>, eta hondar bakar bat, <math display="inline">r</math>, <math display="inline">0 \leq r < b</math>, lortzen ditugula beti.

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

Zergatik ez da <math display="inline">4</math> zatidura? <math display="inline">38 - 4 \cdot 7 = 10 > 38 - 5 \cdot 7</math> delako. Izan ere, “hondar” positiboa sortzen duten zenbaki oso guztien artean, ahalik eta hondar txikiena uzten duena bilatzen dugu. Hau da, <math display="inline">38 - x \cdot 7</math> ahalik eta txikiena, baina positiboa, egiten duen <math display="inline">x</math> zenbakia izango da zatidura. 
Bestela esanda,
<math>\{ x \in \Z \; / \; 38 - x \cdot 7  > 0 \} </math> multzoaren minimoa bilatzen dugu.

Ikus dezagun beste adibide bat: 
<math display="block">\begin{array}{rrll}
                            -38 & \underline{\vline  7} & \\ 
                              4 & -6 & \\
\end{array}</math> 
<math display="inline">-38 - x \cdot 7 > 0</math> izan dadin <math display="inline">x < -5</math> bete behar da. 
<math display="block">\begin{array}{cc}
                             x  & -38 - x \cdot 7 \\ \hline
                            -4 & -10 \\
                            -5 & -3 \\
                            -6 & 4 \\
                            -7 & 11 \\
                            -8 & 18 \\
                            \vdots & \vdots \\
\end{array}</math>

“Hondar” positibo txikiena <math display="inline">4</math> da eta, beraz, zatidura <math display="inline">-6</math> da.

Euklidesek ideia hori teorema honetan zehaztu zuen: 

<span>'''4.9 Teorema.''' </span><span id="euklidesen_teorema" label="euklidesen_teorema">Euklidesen teorema</span> 
[zateukteo]

<math display="inline">a,b \in \Z</math> izanik, <math display="inline">b >0</math> izanik, <math display="block">\exists ! q \in \Z \; \; \exists ! r \in \Z \; \mbox{ non } \; a = qb + r \mbox{ den}, \; 0 \leq r < b \mbox{ izanik};</math>

<math display="inline">q</math> <span>'''zatidura'''</span>, <math display="inline">r</math> <span>'''hondarra'''</span>, <math display="inline">a</math> <span>'''zatikizuna'''</span> eta <math display="inline">b</math> <span>'''zatitzailea'''</span> dira.

<span>'''Froga.''' </span>

<u><math display="inline">q</math> eta <math display="inline">r</math> existitzen dira.</u>

Bi kasu bereiziko ditugu: <math display="inline">b \mid a</math> eta <math display="inline">b \not | \; a</math>.

<ol>
<li><p>
<math display="inline">b \mid a</math>.</p>
<p>Orduan, <math display="inline">\exists k \in \Z</math>, non <math display="inline">a = kb</math> den. Hortaz, nahikoa da <math display="inline">q = k</math> eta <math display="inline">r = 0</math> hartzea, eta <math display="inline">a = qb + r</math> beteko da, <math display="inline">0 \leq r < b</math> izanik.
</p></li>

<li><p>
<math display="inline">b \not | \; a</math>.
</p>
<p>
Izan bedi <math display="inline">S = \{a - xb \; / \; x \in \Z \mbox{ eta } a - xb > 0\}</math> multzoa. Lehendabizi, <math display="inline">S \neq \emptyset</math> dela frogatuko dugu:
</p>

<ol>
<li><p>
<math display="inline">a > 0</math> bada, <math display="inline">a = a - 0 \cdot b > 0</math> beteko da, eta, hortaz, <math display="inline">a \in S</math> da.
</p></li>
<li><p>
<math display="inline">a \leq 0</math> bada, izan bedi <math display="inline">t = a-1</math>. Beraz, <math display="inline">t \in \Z</math> eta <math display="block">a - tb = a - (a-1)b = a - ab + b = (1-b)a + b.</math> beteko dira. Orduan, <math display="block">b > 0 \implies b \geq 1 \implies 1-b \leq 0 \implies (1-b)a \geq 0 \implies (1-b)a + b \geq b > 0 \implies</math> <math display="block"> \implies a - tb > 0 \implies a - tb \in S.</math>
</p></li>
</ol>

<p>
Hortaz, <math display="inline">S \neq \emptyset</math> da, eta ordena onaren printzipioaren arabera, <math display="inline">S</math> multzoak elementu minimoa du; izan bedi <math display="inline">r := \min S</math>.
<math display="block">r \in S \implies r = a - qb > 0, q \in \Z \mbox{ izanik} \implies a = qb + r, \, q, r \in \Z \mbox{ eta } r > 0 \mbox{ izanik}.</math>
</p>
<p>
<math display="inline">r < b</math> dela frogatzea baino ez da geratzen. Demagun <math display="inline">r \geq b</math> dela; kontraesan batera helduko garela ikusiko dugu:
</p>
<ol>
<li><p>
<math display="inline">r = b</math> bada, <math display="inline">a = qb + b = (q+1)b</math> da eta, hortaz, <math display="inline">b \mid a</math> beteko da, hartu dugun <math display="inline">b \not | \; a</math> baldintzaren kontrakoa dena.
</p></li>
<li><p>
<math display="inline">r > b</math> bada, <math display="inline">r = b + c</math> beteko da, <math display="inline">c := r - b > 0</math> izanik. Eta hortik <math display="block">a = qb + r = qb + b + c = (q+1)b + c \implies 0 < c = a - (q+1)b \implies c \in S \implies </math> <math display="block">\implies c \geq r = \min S \implies r - b \geq r \implies b \leq 0</math> lortuko dugu; eta hori ezinezkoa da <math display="inline">b > 0</math> delako.
</p></li>
</ol>
</li>
</ol>

<u><math display="inline">q</math> eta <math display="inline">r</math> bakarrak dira.</u>

Demagun <math display="block">\exists q_1, q_2, r_1, r_2 \in \Z, \, \mbox{ non } \; a = q_1b + r_1 = q_2b + r_2 \, \mbox{ den},</math> <math display="inline">0 \leq r_1 < b</math> eta <math display="inline">0 \leq r_2 < b</math> izanik. Orduan, <math display="block">(q_1 - q_2)b = r_2 - r_1</math> beteko da.

Lehendabizi, <math display="inline">r_1 = r_2</math> dela frogatuko dugu.

<math display="inline">r_1 \neq r_2</math> dela pentsatuko dugu eta kontraesan bat aurkituko dugu.

<ol>
<li>
<math display="inline">r_2 > r_1</math> bada, <math display="inline">0 < (q_1 - q_2)b \leq r_2 < b</math> izango dugu. <math display="inline">b > 0</math> denez, <math display="inline">0 < q_1 - q_2 < 1</math> aterako dugu; eta hori ezinezkoa da <math display="inline">q_1 - q_2 \in \Z</math> delako.
</li>
<li>
<math display="inline">r_2 < r_1</math> bada, arrazoibide bera da, kontuan izanik <math display="inline">(q_2 - q_1)b = r_1 - r_2</math> dela.
</li>
</ol>

Hortaz, <math display="inline">r_1 = r_2</math> dugu; hortik <math display="inline">q_1b = q_2b</math> aterako dugu. <math display="inline">b \neq 0</math> denez, <math display="inline">q_1 = q_2</math> lortuko dugu. <math display="inline">\Box</math>

<span>'''4.10 Adibidea.''' </span> <math display="block">\begin{array}{rrll}
        27 & \underline{\vline  6} & \\ 
    3 &   4 & \\
  \end{array} \quad \quad
  \begin{array}{rrll}
        -27 & \underline{\vline  6} & \\ 
    3 &   -5 & \\
  \end{array} \quad \quad
  \begin{array}{rrll}
        6 & \underline{\vline  27} & \\ 
    6 &   0 & \\
  \end{array} \quad \quad
  \begin{array}{rrll}
        -6 & \underline{\vline  27} & \\
    21 &   -1 & \\
  \end{array}</math>

===  4.1.4 Zatitzaile komun handiena ===

<span>'''4.11 Definizioa.''' </span> Izan bitez <math display="inline">a, b \in \Z</math> eta izan bedi <math display="inline">c \in \Z^{+}</math>. <math display="inline">c</math> zenbakia <math display="inline">a</math> eta <math display="inline">b</math> zenbakien <span>'''zatitzaile komun'''</span> bat dela esango dugu <math display="inline">c \mid a</math> eta <math display="inline">c \mid b</math> betetzen badira.

<span>'''4.12 Adibidea.''' </span><span id="zatikomu" label="zatikomu">[zatikomu]</span> <math display="inline">-24</math> zenbakiaren zatitzaile positiboak <math display="inline">1</math>, <math display="inline">2</math>, <math display="inline">3</math>, <math display="inline">4</math>, <math display="inline">6</math>, <math display="inline">8</math>, <math display="inline">12</math> eta <math display="inline">24</math> dira. <math display="inline">32</math> zenbakiaren zatitzaile positiboak <math display="inline">1</math>, <math display="inline">2</math>, <math display="inline">4</math>, <math display="inline">8</math>, <math display="inline">16</math> eta <math display="inline">32</math> dira. Bion zatitzaile positibo komunak <math display="inline">1</math>, <math display="inline">2</math>, <math display="inline">4</math> eta <math display="inline">8</math> dira.

<span>'''4.13 Definizioa.''' </span> Izan bitez <math display="inline">a, b \in \Z</math>, <math display="inline">a \neq 0</math> edo <math display="inline">b \neq 0</math>, eta izan bedi <math display="inline">d \in \Z^{+}</math>. <math display="inline">d</math> zenbakia <math display="inline">a</math> eta <math display="inline">b</math> zenbakien <span>'''zatitzaile komun handienetako'''</span> bat dela esango dugu baldin

<ol>
<li>
<math display="inline">d</math> bada <math display="inline">a</math> eta <math display="inline">b</math> zenbakien zatitzaile komun bat: <math display="block">d \mid a \, \mbox{ eta } \, d \mid b;</math>
</li>
<li>
<math display="inline">a</math> eta <math display="inline">b</math> zenbakien edozein zatitzaile komunek <math display="inline">d</math> zatitzen badu (<math display="inline">d</math> “handienetakoa” da zatigarritasunaren arabera): <math display="block">(\forall c\in \Z^{+}) \quad c \mid a, \quad c \mid b \, \Rightarrow \, c \mid d.</math>
</li>
</ol>

<span>'''4.14 Adibidea.''' </span> [[#zatikomu|[zatikomu]]] Adibidean ikus dezakegu <math display="inline">-24</math> eta <math display="inline">32</math> zenbakien zatitzaile komun handiena <math display="inline">8</math> 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.

<span>'''4.15 Teorema.''' </span> (Zatitzaile komun handienaren bakartasuna)

<math display="inline">a,b \in \Z</math> emanik, <math display="inline">a</math> eta <math display="inline">b</math> zenbakien zatitzaile komun handiena, existitzen bada, bakarra da.

<span>'''Froga.''' </span>

Demagun <math display="inline">a</math> eta <math display="inline">b</math> zenbakien bi zatitzaile komun handien daudela, <math display="inline">d_1</math> eta <math display="inline">d_2</math>. <math display="inline"> \, d_1 = d_2</math> dela frogatuko dugu.

<math display="inline">d_1</math> <math display="inline">a</math> eta <math display="inline">b</math> zenbakien zatitzaile <u>komuna</u> da; beraz, <math display="inline">d_1 \mid a</math> eta <math display="inline">d_1 \mid b</math>; hortaz, <math display="inline">d_1 \mid d_2</math>, <math display="inline">d_2</math> delako <math display="inline">a</math> eta <math display="inline">b</math> zenbakien zatitzaile komun <u>handienetako bat</u>.

Antzeko eran frogatuko genuke <math display="inline">d_2 \mid d_1</math> ere betetzen dela. Orduan, 
<math display="block">\left. \begin{array}{ll}
                                   d_1 \mid d_2 \\
                                   d_2 \mid d_1 \\
                             \end{array} \right\}
\implies d_1 = d_2 \, \mbox{ edo } \, d_1 = -d_2.</math> 
<math display="inline">d_1, d_2 \in \Z^{+}</math> denez, aukera bakarra <math display="inline">d_1 = d_2</math> izatea da. <math display="inline">\Box</math>

<span>'''Oharrak.''' </span>
<ol>
<li>
<math display="inline">a,b \in \Z</math> izanik, <math display="inline">a</math> eta <math display="inline">b</math> zenbakien zatitzaile komun handiena badago, <math display="inline">\mbox{zkh}(a,b)</math> adieraziko dugu.
</li>
<li>
<math display="inline">\mbox{zkh}(a,b)</math> badago, <math display="inline">\mbox{zkh}(b,a) = \mbox{zkh}(a,b)</math> beteko da.
</li>
<li>
<math display="inline">\mbox{zkh}(0, 0)</math> ez dago definiturik.
</li>
<li>
<math display="inline">a \in \Z^*</math> bada, erraz froga daiteke <math display="inline">\mbox{zkh}(a,0)</math> badagoela, eta <math display="inline">\mbox{zkh}(a,0) = \mid a \mid</math> betetzen dela.
*<math display="inline">\mid a \mid</math> zenbakia <math display="inline">a</math> eta <math display="inline">0</math> zenbakien zatitzaile <u>komuna</u> da: <math display="block">a = \mid a \mid \mbox{ edo } a = (-1)\cdot \mid a \mid \quad \implies \; \mid a\mid \big| \; a</math> 
<math display="block">\mid a \mid \; \big|\;0 \mbox{ (edozein zenbaki oso da 0 zenbakiaren zatitzailea).}</math>
* <math display="inline">\mid a \mid</math> zenbakia <math display="inline">a</math> eta <math display="inline">0</math> zenbakien zatitzaile komun <u>handiena</u> da: <math display="inline">c \in \Z^{+}</math> izanik, 
<math display="block">\left. \begin{array}{ll}
                                   c \mid a \\
                                   c \mid 0 \\
                             \end{array} \right\} 
\implies c \mid a \implies c \; \big | \; \mid a \mid \mbox{ (}\mid a \mid = a\mbox{ edo }\mid a \mid = -a\mbox{ delako).}</math>
</li>
</ol>

Laburbilduz, <math display="inline">a</math> edo <math display="inline">b</math> zenbakietako bat bakarrik <math display="inline">0</math> bada, badago <math display="inline">\mbox{zkh}(a,b)</math>. Beraz, <math display="inline">\mbox{zkh}(a,b)</math> existitzen dela frogatzeko, <math display="inline">a</math> eta <math display="inline">b</math> positiboak direla pentsatuko dugu.

<span>'''4.16 Teorema.''' </span> (Zatitzaile komun handienaren existentzia) <span id="zkhex" label="zkhex">[zkhex]</span>

<math display="inline">a,b \in \Z^{+}</math> zenbaki oso positibo guztietarako existitzen da zatitzaile komun handiena.

<span>'''Froga.''' </span>

Har dezagun <math display="inline">a</math> eta <math display="inline">b</math> zenbakien konbinazio lineal positibo guztien multzoa: <math display="block">S = \{ xa + yb \; / \; x, y \in \Z \quad \mbox{eta} \quad xa + yb > 0 \}.</math>

<math display="inline">S \subseteq \Z^{+}</math> da. <math display="inline">0 < a = 1 \cdot a + 0 \cdot b</math> betetzen denez, <math display="inline">a \in S</math> dugu eta, beraz, <math display="inline">S \neq \emptyset</math> da. Ordena onaren printzipioaren arabera, <math display="inline">S</math> multzoak elementu minimoa du; izan bedi <math display="inline">d = \min S</math>.

<math display="inline">d \in S</math> denez, <math display="inline">d</math> izango da <math display="inline">a</math> eta <math display="inline">b</math> zenbakien konbinazio lineal positibo bat; hau da, <math display="inline">d \in \Z^{+}</math> eta <math display="block">d = xa + yb, \quad x,y \in \Z \mbox{ izanik}.</math>

Ikus dezagun <math display="inline">d = \mbox{zkh}(a,b)</math> dela:

<ol>
<li><p>
<math display="inline">d</math> zenbakia <math display="inline">a</math> eta <math display="inline">b</math> zenbakien zatitzaile <u>komun bat</u> da:</p>
<ul>
<li><p>
Demagun <math display="inline">d \not | \, a</math> dela, eta kontraesan bat aurkituko dugu:</p>
<p><math display="inline">d \not | \, a</math> bada, <math display="inline">a</math> zati <math display="inline">d</math> zatiketa euklidearra egitean, <math display="inline">0</math> ez den hondar bat lortuko dugu: 
<math display="block">\begin{array}{rl}
                            a & \underline{\vline  d} \\ 
                            r &   q 
                      \end{array}, \quad \quad r > 0.</math> 
Hau da, <math display="inline">a = qd + r</math> da, <math display="inline">0 < r < d</math> izanik. Hortaz, <math display="inline">0 < r = a - qd = a - q(xa + yb) = (1 - qx)a + (-qy)b</math> ere izango dugu. Beraz, <math display="inline">r</math> hondarra <math display="inline">a</math> eta <math display="inline">b</math> zenbakien konbinazio lineal positibo bat da. Orduan, <math display="inline">r \in S</math> dugu eta, ondorioz, <math display="inline">r \geq d = \min S</math> beteko da; eta hori ezinezkoa da, <math display="inline">r < d</math> delako.</p></li>
<li><p><math display="inline">d \mid b</math> betetzen dela frogatzeko, antzeko arrazoibidea erabiliko genuke.</p></li></ul>
</li>
<li><p>
<math display="inline">d</math> zenbakia <math display="inline">a</math> eta <math display="inline">b</math> zenbakien zatitzaile komun <u>handiena</u> da: <math display="inline">c \in \Z^{+}</math> izanik, 
<math display="block">\left. \begin{array}{ll}
                                   c \mid a \\
                                   c \mid b \\
                             \end{array} \right\} \implies c \mid xa + yb = d</math> (zenbaki oso batek bi zenbaki zatitzen baditu, horien edozein konbinazio lineal zatituko duelako).</p></li></ol>
<math display="inline">\Box</math>

<span>'''Oharrak.''' </span>
<ol>
<li><p>
Orain, erraza da frogatzea, <math display="inline">a,b \in \Z</math> izanik, beti existitzen dela <math display="inline">\mbox{zkh}(a,b)</math> (<math display="inline">a = b = 0</math> denean izan ezik).</p>

<ol>
<li>
<p><math display="inline">\mbox{zkh} (\mid a \mid ,\mid b \mid)</math> existitzen dela jadanik frogatu dugu. Eta erraz froga dezakegu  
<math display="inline">\mbox{zkh}(a, b) = \mbox{zkh}(\mid a \mid ,\mid b \mid)</math> betetzen dela.</p>
<p>Horretarako, izan bedi <math display="inline">d = \mbox{zkh}(\mid a \mid ,\mid b \mid)</math> (badakigu existitzen dena); ikus dezagun <math display="inline">d = \mbox{zkh} (a,b)</math> dela:</p>
<ul>
<li><p>
<math display="inline">d</math> zenbakia <math display="inline">a</math> eta <math display="inline">b</math> zenbakien zatitzaile <u>komun bat</u> da: <math display="block">d = \mbox{zkh}(\mid a \mid ,\mid b \mid) \implies 
\left\{ \begin{array}{ll}
              d \big| \; \mid a \mid \implies d \mid a \\
              \\
              d \big| \; \mid b \mid \implies d \mid b \\
        \end{array} \right.</math>
</p></li>
<li><p>
<math display="inline">d</math> zenbakia <math display="inline">a</math> eta <math display="inline">b</math> zenbakien zatitzaile komun <u>handiena</u> da: <math display="inline">c \in \Z^{+}</math> izanik, 
<math display="block">\left. \begin{array}{ll}
                                   c \mid a \\
                                   c \mid b \\
                             \end{array} \right\} \implies 
\left\{ \begin{array}{ll}
              c \big| \; \mid a \mid \\
              \\
              c \big| \; \mid b \mid \\
        \end{array} \right\} \implies c \mid d,</math> 
<math display="inline">d</math> zenbakia <math display="inline">\mid a \mid</math> eta <math display="inline">\mid b \mid</math> zenbakien zatitzaile komun <u>handiena</u> delako.
</p></li>
</ul>
</li>

<li><p>
<math display="inline">a,b \in \Z</math> izanik, <math display="inline">a \neq 0</math> edo <math display="inline">b \neq 0</math>, <math display="inline"> \, a</math> eta <math display="inline">b</math> zenbakien konbinazio lineal bezala adieraz daitekeen zenbaki oso positiborik txikiena izango da <math display="inline">\mbox{zkh}(a,b)</math>: <math display="block">\mbox{zkh} (a,b) = \min \{ xa + yb \, / \, x,y \in \Z \, \mbox{ eta } \, xa + yb > 0 \}.</math></p>

<p>Emaitza hori [[#zkhex|[zkhex]]] Teoremaren frogatik atera dezakegu <math>a,b \in \Z^+</math> direnean. Emaitza hori <math display="inline">a \in \Z^-</math> edo <math display="inline">b \in \Z^-</math> direnean frogatzeko, nahikoa da kontuan hartzea <math display="inline">\mbox{zkh} (a,b) = \mbox{zkh} (\mid a \mid,\mid b \mid)</math> dela eta <math display="block">\{ xa + yb \, / \, x,y \in \Z \, \mbox{ eta } \, xa + yb > 0 \} =</math> <math display="block">= \{ x \mid a \mid + y \mid b \mid \, / \, x,y \in \Z \, \mbox{ eta } \, x \mid a \mid + y \mid b \mid >0 \} \, \mbox{dela}.</math> Demagun, esaterako, <math display="inline">a < 0</math> eta <math display="inline">b > 0</math> direla. Orduan, <math display="block">z \in \{ x \mid a \mid + y \mid b \mid \, / \, x,y \in \Z \, \mbox{ eta } \, x \mid a \mid + y \mid b \mid > 0 \} \implies </math> <math display="block">\implies z = x_1 \mid a \mid + y_1 \mid b \mid, \, x_1,y_1 \in \Z \, \mbox{ eta } \, x_1 \mid a \mid + y_1 \mid b \mid > 0 \, \mbox{ izanik} \implies</math> <math display="block">\implies z = x_1(-a) + y_1b = (-x_1)a + y_1b, \, (- x_1),y_1 \in \Z \, \mbox{ eta }\, (-x_1)a + y_1b > 0 \, \mbox{ izanik} \implies</math> <math display="block">\implies z \in \{ xa + yb \, / \, x,y \in \Z \, \mbox{ eta } \, xa + yb > 0\}.</math> Eta hortik hau aterako dugu: <math display="block">\{ x \mid a \mid + y \mid b \mid \, / \, x,y \in \Z \, \mbox{ eta } \, x \mid a \mid + y \mid b \mid > 0 \} \subseteq \{ xa + yb \, / \, x,y \in \Z \, \mbox{ eta } \, xa + yb > 0 \}.</math> Beste partekotasuna antzeko eran frogatuko genuke.
</p></li>
</ol>

<li><p>
<math display="inline">a,b \in \Z</math> izanik, <math display="inline">a \neq 0</math> edo <math display="inline">b \neq 0</math>, <math display="block">\mbox{zkh} (a,b) = xa + yb, \, x,y \in \Z \, \mbox{ izanik};</math> baina <math display="inline">x,y</math> ez dira bakarrak; izan ere, <math display="inline">\mbox{zkh} (a,b)= xa + yb</math> bada, <math display="inline"> \, p \in \Z</math> guztietarako hau beteko da: <math display="block">\mbox{zkh} (a,b) = (x + pb)a + (y - pa)b.</math>
</p></li>
</ol>

<span>'''4.17 Adibidea.''' </span> <math display="block">\mbox{zkh} (24,32) = \mbox{zkh} (-24,32) = 8.</math> 
<math display = "block">
\begin{array}{rl}
      8 = & (-1)24 + 1 \cdot 32 = (-1+32)24 + (1-24))32 = \\
        = & 31 \cdot 24 + (-23) \cdot 32 = (-1-64)24 + (1+48)32 = \\
        = & (-65)24 + 49 \cdot 32 = \cdots
\end{array}</math>

<span>'''Oharra.''' </span>
<math display="inline">a,b \in \Z</math> eta <math display="inline">d \in \Z^{+}</math> izanik, <math display="block">d = \mbox{zkh} (a,b) \implies d = xa + yb, \, x,y \in \Z \, \mbox{ izanik}.</math> Baina elkarrekikoa ez da orokorrean betetzen, <math display="inline">d = 1</math> denean izan ezik. <math display="block">d = xa + yb, \, x,y \in \Z \, \mbox{ izanik} \implies d \geq \mbox{zkh} (a,b).</math>

<span>'''4.18 Definizioa.''' </span> <math display="inline">a,b \in \Z</math> emanik, <math display="inline">a,b</math> zenbakiak <span>'''zenbaki lehen erlatiboak'''</span> direla esango dugu <math display="inline">\mbox{zkh} (a,b) = 1</math> denean.

<span>'''4.19 Ondorioa.''' <math display="inline">a,b \in \Z</math> emanik, <math display="block">a,b \, \mbox{ lehen erlatiboak dira} \iff \exists x,y \in \Z, \, \mbox{ non } \, xa + yb = 1 \, \mbox{den}.</math>

<span>'''4.20 Adibidea.''' </span> <math display="block">16 =(-2)24 + 2 \cdot 32. \, \, \mbox{ Hortaz,} \, \, \mbox{zkh}(24,32) \leq 16 \, \mbox{ da}.</math> 
<math display="block">1 = (-1)3 + 1 \cdot 4. \, \mbox{ Hortaz,} \, \, \mbox{zkh}(3,4) = 1 \, \mbox{ eta } \, 3, 4 \mbox{ zenbaki lehen erlatiboak dira}.</math>

=== 4.1.5 Euklidesen algoritmoa ===

<math display="inline">a,b \in \Z^{+}</math> izanik, <math display="inline">b \mid a</math> bada, <math display="inline">\mbox{zkh}(a,b) = b</math> izango da. Bestela, <math display="inline">\mbox{zkh}(a,b)</math> kalkulatzeko, algoritmo hau erabiliko dugu:

<span>'''Euklidesen algoritmoa.'''</span> Ondoko zatiketak egingo ditugu: 

<math display="block">\begin{array}{cllll}
      \begin{array}{rrll}
            a   & \underline{\vline  b } \\
            r_1 & q_1 & \\
      \end{array} & & a = q_1b + r_1, & & 0 < r_1 < b; \\
      \\
      \begin{array}{rrll}
            b   & \underline{\vline  r_1} \\
            r_2 & q_2 & \\
      \end{array} & & b = q_2r_1 + r_2, & & 0 < r_2 < r_1; \\
      \\
      \begin{array}{rrll}
            r_1 & \underline{\vline  r_2 } \\
            r_3 & q_3 & \\
      \end{array} & & r_1 = q_3r_2 + r_3, & & 0 < r_3 < r_2; \\
      \\
      \vdots & & \vdots & & \vdots \\
      \\
      \begin{array}{rrll}
            r_i     & \underline{\vline  r_{i+1} } \\
            r_{i+2} & q_{i+2} & \\
      \end{array} & & r_i = q_{i+2}r_{i+1} + r_{i+2}, & & 0 < r_{i+2} < r_{i+1}; \\
      \\
      \vdots & & \vdots & & \vdots \\
      \\
\end{array}</math>

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

<math display="block">\begin{array}{cllll}
      \begin{array}{rl}
            r_{k-1} & \underline{\vline  r_k } \\
            0       & q_{k+1} &\\
     \end{array} & & r_{k-1} = q_{k+1}r_{k}+0. & \quad &
\end{array}</math>

<math display="block">b > r_1 > r_2 > \cdots > r_{k-1} > r_k > 0 \; (= r_{k+1}).</math>

Orduan, <math display="inline">r_k</math>, <math display="inline">0</math> ez den azkeneko hondarra, <math display="inline">\mbox{zkh}(a,b)</math> da: 

<math display="block">\mbox{zkh}(a,b) = r_{k}.</math>

<span>'''Froga.'''</span>

Berdintza hauek dauzkagu:\label{hiru} 

<math display="block">
\left. \begin{array}{l}
             a = q_1b + r_1, \\
             b = q_2r_1 + r_2, \\
             r_i = q_{i+2}r_{i+1} + r_{i+2}, \quad i=1, \ldots, k-2. 
       \end{array} \right\} \mbox{ (hiru) }</math> 

<math display="inline">r_{0} = b</math> eta <math display="inline">r_{-1} = a</math> izendatzen baditugu, ([[#hiru|[hiru]]]) honela idatz ditzakegu: 

<math display="block">
r_i = q_{i+2}r_{i+1} + r_{i+2}, \quad i=-1, \ldots, k-2. \mbox{ (ri) }</math> 

Eta horrez gain, beste hau ere badugu: 

<math display="block">r_{k-1} = q_{k+1}r_{k}. \mbox{ (rk) }</math>

<math display="inline">\mbox{zkh}(a,b) = r_{k}</math> dela frogatzeko, ondokoa frogatu beharko dugu:

<ol>
<li><p>
<math display="inline">r_k</math> hondarra <math display="inline">a</math> eta <math display="inline">b</math> zenbakien <u>zatitzaile komun</u> bat da; hau da, <math display="inline">r_k \mid a</math> eta <math display="inline">r_k \mid b</math> betetzen dira.
</p>
<p>
Horretarako, ondoz ondo frogatuko dugu <math display="inline">r_k</math> hondarrak <math display="inline">r_k</math>, <math display="inline">r_{k-1}</math>, <math display="inline">r_{k-2}</math>, <math display="inline">r_{k-3}</math>, etab. zatitzen dituela, <math display="inline">r_{0} = b</math> eta <math display="inline">r_{-1} = a</math> ere zatitzen dituela frogatu arte.
</p>
<p>
([[#ri|[ri]]]) berdintzan ikus dezakegu <math display="inline">i=-1, \ldots, k-2</math> balioetarako <math display="inline">r_i</math> hondarra <math display="inline">r_{i+2}</math> eta <math display="inline">r_{i+1}</math> hondarren konbinazio lineala dela, eta hori erabiliko dugu.
</p>
<ul>
<li><p>
Argi dago <math display="inline">r_k \mid r_k</math> betetzen dela.
</p></li>
<li><p>
Bestalde, ([[#rk|[rk]]]) berdintzatik <math display="inline">r_k \mid r_{k-1}</math> ateratzen da.
</p></li>
<li><p>
<math display="inline">r_k \mid r_{k-2}</math> frogatzeko, ([[#ri|[ri]]]) berdintzetako <math display="inline">i=k-2</math> kasuan, <math display="inline">r_{k-2} = q_{k}r_{k-1} + r_{k}</math> berdintza dugu; hau da, <math display="inline">r_{k-2}</math> hondarra <math display="inline">r_{k}</math> eta <math display="inline">r_{k-1}</math> hondarren konbinazio lineala da. <math display="inline">\, r_k \mid r_{k}</math> eta <math display="inline">r_k \mid r_{k-1}</math> frogatu ditugunez, <math display="inline">r_k \mid r_{k-2}</math> daukagu.
</p></li>
<li><p>
<math display="inline">r_k\mid r_{k-3}</math> frogatzeko, antzeko arrazoibidea erabiliko dugu: ([[#ri|[ri]]]) berdintzetako <math display="inline">i=k-3</math> kasuan, <math display="inline">r_{k-3} = q_{k-1}r_{k-2} + r_{k-1}</math> berdintza dugu; hau da, <math display="inline">r_{k-3}</math> hondarra <math display="inline">r_{k-1}</math> eta <math display="inline">r_{k-2}</math> hondarren konbinazio lineala da. <math display="inline">r_k \mid r_{k-1}</math> eta <math display="inline">r_k \mid r_{k-2}</math> frogatuta daudenez, <math display="inline">r_k \mid r_{k-3}</math> ere beteko da.
</p></li>
<li><p>
Antzeko eran frogatuko ditugu <math display="inline">r_k \mid r_{k-4}</math>, <math display="inline">r_k \mid r_{k-5}</math>, etab. <math display="inline">r_k \mid r_{0} = b</math> eta <math display="inline">r_k \mid r_{-1} = a</math> kasuetara heldu arte.
</p></li>
</ul>

</li>
<li><p>
<math display="inline">r_{k}</math> hondarra <math display="inline">a</math> eta <math display="inline">b</math> zenbakien <u>zatitzaile komun handiena</u> da; hau da, <math display="inline">a</math> eta <math display="inline">b</math> zenbakien edozein zatitzaile komun <math display="inline">r_k</math> hondarraren zatitzailea da.
</p>
<p>
Izan bedi <math display="inline">c \in \Z^{+}</math> <math display="inline">a</math> eta <math display="inline">b</math> zenbakien zatitzaile komun bat, hots, <math display="inline">c \mid a</math> eta <math display="inline">c \mid b</math> betetzen dira. <math display="inline">c \mid r_k</math> ere betetzen dela frogatu behar dugu. Horretarako, ondoz ondo frogatuko dugu <math display="inline">c</math> zenbakiak <math display="inline">r_{-1}</math>, <math display="inline">r_{0}</math>, <math display="inline">r_{1}</math>, <math display="inline">r_{2}</math>, etab. zatitzen dituela, <math display="inline">r_{k}</math> hondarrera heldu arte.
</p>
<p>
([[#ri|[ri]]]) berdintzetatik <math display="inline">r_{i+2}</math> bakanduz gero, ekuazio hauek lortuko ditugu: 

<math display="block">r_{i+2} = r_i - q_{i+2}r_{i+1} \quad i=-1, \ldots, k-2. \; \mbox{ (alder) }</math> 
</p>
<p>
Ohar gaitezen, orduan, <math display="inline">i=-1, \ldots, k-2</math> balioetarako <math display="inline">r_{i+2}</math> hondarra <math display="inline">r_{i}</math> eta <math display="inline">r_{i+1}</math> hondarren konbinazio lineala dela; propietate hori erabiliko dugu.
</p>
<ul>
<li><p>
<math display="inline">c \mid a = r_{-1}</math>.
</p></li>
<li><p>
<math display="inline">c \mid b = r_{0}</math>.
</p></li>
<li><p>
<math display="inline">c \mid r_{1}</math> frogatzeko, ([[#alder|[alder]]]) ekuazioetako <math display="inline">i=-1</math> kasuan, <math display="inline">r_{1} = r_{-1} - q_{1}r_{0}</math> dugu; hau da, <math display="inline">r_{1}</math> hondarra <math display="inline">r_{-1}</math> eta <math display="inline">r_{0}</math> hondarren konbinazio lineala da. <math display="inline">c \mid r_{-1}</math> eta <math display="inline">c \mid r_{0}</math> betetzen direnez, <math display="inline">c \mid r_{1}</math> ere beteko da.</p></li>
<li><p><math display="inline">c\mid r_{2}</math> frogatzeko, arrazoibidea antzekoa da: ([[#alder|[alder]]]) ekuazioetako <math display="inline">i=0</math> kasuan, <math display="inline">r_{2} = r_{0} - q_{2}r_{1}</math> dugu; hau da, <math display="inline">r_{2}</math> hondarra <math display="inline">r_{0}</math> eta <math display="inline">r_{1}</math> hondarren konbinazio lineala da. <math display="inline">c \mid r_{0}</math> eta <math display="inline">c \mid r_{1}</math> betetzen direla frogatu dugunez, <math display="inline">c \mid r_{2}</math> ere beteko da.</p></li>
<li><p>Antzeko eran frogatuko dugu <math display="inline">c \mid r_{3}</math>, <math display="inline">c \mid r_{4}</math>, etab. betetzen direla <math display="inline">c \mid r_{k}</math> betetzen dela frogatu arte.</p></li></ul>
</li></ol>
<math display="inline">\Box</math>

<span>'''4.21 Adibidea.''' </span> <span id="zkh" label="zkh">[zkh]</span> <math display="inline">\mbox{zkh}(250,12)</math> kalkulatzeko: 
<math display="block">
\begin{array}{rrll}
      250 & \underline{\vline  12 } \\
       10 & 20 & \\
\end{array} \quad \quad
\begin{array}{rrll}
      12 & \underline{\vline  10 } \\
       2 &  1 & \\
\end{array} \quad \quad
\begin{array}{rrll}
      10 & \underline{\vline  2 } \\
       0 &  5 & \\
\end{array}.</math> 
Hortaz, 
<math display="block">\mbox{zkh}(250,12) = \mbox{zkh}(-250,12) = \mbox{zkh}(250,-12) = \mbox{zkh}(-250,-12) = 2.</math>

<span>'''Oharrak.''' </span>

# Euklidesen algoritmoa bai <math display="inline">a > b</math> denean bai <math display="inline">a < b</math> denean erabil daiteke; azken kasu horretan zatiketa bat gehiago egin beharko da.
# Euklidesek algoritmoak <math display="inline">\mbox{zkh}(a,b)</math> <math display="inline">a,b</math> zenbakien konbinazio lineal bezala adierazteko metodoa erakutsi digu.

<span>'''4.22 Adibideak.''' </span>
<ol>
<li><p>
[[#zkh|[zkh]]] adibidean, <math display="inline">\mbox{zkh} (250,12) = 2</math> kalkulatu dugu. <math display="inline">2</math> emaitza <math display="inline">250</math> eta <math display="inline">12</math> zenbakien konbinazio lineal bezala adierazteko, <math display="inline">2</math> azkeneko hondar ez-nulua <math display="inline">10</math> eta <math display="inline">12</math> zenbakien konbinazio lineal bezala adierazten hasiko gara:

<math display="block">\begin{array}{cllll}
\begin{array}{rrll}
      12 & \underline{\vline  10 } \\
       2 & 1 & \\
\end{array} & & 12 = 1 \cdot 10 + 2, & & 2 = 12 - 1 \cdot 10. \\
\end{array}</math> 

Orain, kontuan izanik <math display="inline">10</math> dela aurreko hondarra, <math display="inline">10</math> hori <math display="inline">250</math> eta <math display="inline">12</math> zenbakien konbinazio lineal bezala adieraz dezakegu: 

<math display="block">\begin{array}{cllll}
\begin{array}{rrll}
      250 & \underline{\vline  12 } \\
       10 & 20 & \\
\end{array} & & 250 = 20 \cdot 12 + 10, & & 10 = 250 - 20 \cdot 12. \\
\end{array}</math>

Orduan, hau lortuko dugu: <math display="block">2 = 12 - 1 \cdot {\bf 10} = 12 - 1 \cdot (250 - 20 \cdot 12) =(-1) \cdot 250 + 21 \cdot 12.</math>
</p>
</li>

<li>
<p>
<math>\mbox{zkh}(-250, 12) = 2 = 1 \cdot (-250) + 21 \cdot 12.</math>
<math>\mbox{zkh}(250, -12) = 2 = (-1) \cdot 250 + (-21) \cdot (-12).</math>
<math>\mbox{zkh}(-250, -12) = 2 = 1 \cdot (-250) + (-21) \cdot (-12).</math>
</p>
</li>

<li>
<p>
Euklidesen algoritmoa erabiliko dugu <math display="inline">\mbox{zkh} (250,111)</math> kalkulatzeko eta <math display="inline">250</math> eta <math display="inline">111</math> zenbakien konbinazio lineal bezala adierazteko:
</p>
<p>
<math display="block">\begin{array}{cllll}
\begin{array}{rrll}
      250 & \underline{\vline  111 } \\
       28 & 2 & \\
\end{array} & & 250 = 2 \cdot 111 + 28, & & 28 = 250 - 2 \cdot 111; \\
    \\
\begin{array}{rrll}
      111 & \underline{\vline  28} \\
       27 & 3 & \\
\end{array} & & 111 = 3 \cdot 28 + 27, & & 27 = 111 - 3 \cdot 28; \\
    \\
\begin{array}{rrll}
      28 & \underline{\vline  27 } \\
       1 & 1 & \\
\end{array} & & 28 = 1 \cdot 27 + 1, & & 1 = 28 - 1 \cdot 27; \\
    \\
\begin{array}{rrll}
      27 & \underline{\vline  1 } \\
       0 & 27 & \\
\end{array} & & 27 = 1 \cdot 27. & & \\
\end{array}</math>
</p>
<p>
<math display="inline">\mbox{zkh}(250, 111) = 1</math>; beraz, <math display="inline">250</math> eta <math display="inline">111</math> zenbaki lehen erlatiboak dira. 

<math display="block">
\begin{array}{rl}
      1 = & 28-1 \cdot 27 = 28 - 1 \cdot (111 - 3 \cdot 28) = \\
        = & (-1) \cdot 111 + 4 \cdot 28 = (-1) \cdot 111 + 4 \cdot (250 - 2 \cdot 111) = \\
        = & 4 \cdot 250 + (-9) \cdot 111.
\end{array}</math>
</p>
</li>
</ol>

=== 4.1.6 Multiplo komun txikiena ===

<span>'''4.23 Definizioa.'''</span> Izan bitez <math>a, b, c \in \Z^{+}</math>, <math>\, c</math> zenbakia <math>a</math> eta <math>b</math> zenbakien <span>'''multiplo komun'''</span> bat dela esango dugu baldin <math>a \mid c</math> eta <math>b \mid c</math> bada.

<span>'''4.24 Adibideak.'''</span>

# <math>40</math> zenbakia <math>2</math> eta <math>10</math> zenbakien multiplo komun bat da; izan ere, <math>2 \mid 40</math> eta <math>10 \mid 40</math> betetzen dira.
# <math>180</math> zenbakia <math>12</math> eta <math>18</math> zenbakien multiplo komun bat da; izan ere, <math>12 \mid 180</math> eta <math>18 \mid 180</math> betetzen dira.

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

# <math>m</math> zenbakia <math>a</math> eta <math>b</math> zenbakien multiplo komun bat da:
<math>a \mid m \, \mbox{ eta } \, b \mid m.</math>
# <math>a</math> eta <math>b</math> zenbakien edozein multiplo komun <math>m</math> baino handiago edo berdina da:

<math>(\forall c \in \Z^{+}) \quad  a \mid c, \quad b \mid c \implies m \leq c.</math>

<span>'''4.26 Adibideak.'''</span>

# <math>40</math> zenbakia <math>2</math> eta <math>10</math> zenbakien multiplo komuna da, baina ez da <math>\mbox{mkt}(2,10)</math>; izan ere, <math>20</math> ere <math>2</math> eta <math>10</math> zenbakien multiplo komuna da eta <math>20 \leq 40</math>. Gainera, <math>\mbox{mkt}(2,10) = 10</math> dela froga dezakegu:
#* <math>2 \mid 10</math> eta <math>10 \mid 10</math>.
#* <math>(\forall c\in \Z^{+}) \quad  2 \mid c, \quad 10 \mid c \implies 10 \mid c \implies 10 \leq c</math>.
# <math>180</math> zenbakia <math>12</math> eta <math>18</math> zenbakien multiplo komuna da, baina ez da <math>\mbox{mkt}(12,18)</math>; izan ere, <math>72</math> ere <math>12</math> eta <math>18</math> zenbakien multiplo komuna da eta <math>72 \leq 180</math>. Froga genezake <math>\mbox{mkt}(12,18) = 36</math> dela.

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

<span>'''4.27 Teorema.'''</span> <math>a, b, m \in \Z^{+}</math> izanik, <math>m = \mbox{mkt}(a,b)</math> bada, <math>a</math> eta <math>b</math> zenbakien edozein multiplo komun <math>m</math> zenbakiaren multiploa da: <math>(\forall c \in \Z^{+}) \quad a \mid c, \quad b \mid c \, \Rightarrow \, m \mid c.</math> 

<span>'''Froga.'''</span>

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

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

Demagun <math>m \not | \, c</math> betetzen dela; kontraesan bat bilatuko dugu.

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

Batetik <math>a \mid c</math>, bestetik <math>m = \mbox{mkt}(a,b) \implies a \mid m</math> ditugu; hortaz, <math>a \mid r</math> ere beteko da.

Horrez gain, <math>b \mid c</math> ere betetzen da, eta <math>m = \mbox{mkt}(a,b) \implies b \mid m</math>; hortaz, <math>b \mid r</math> ere beteko da.

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

Ondorioz, <math>m \mid c</math> dugu. <math>\Box</math>

<span>'''4.28 Adibidea.'''</span> <math>\mbox{mkt}(12, 18) = 36</math> denez, <math>12</math> eta <math>18</math> zenbakien edozein multiplo komun <math>36</math> zenbakiaren multiploa da. Esaterako, <math>36 \mid 72</math>.

Ondoko teoreman, zatitzaile komun handiena eta multiplo komun txikiena erlazionatuko ditugu.

<span>'''4.29 Teorema.'''</span> <math>a, b \in \Z^{+}</math> izanik, <math>ab = \mbox{mkt}(a,b) \, \mbox{zkh}(a,b)</math> betetzen da.

<span>'''Froga.'''</span>

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

<math>d = \mbox{zkh}(a,b)</math> denez, <math>a = k_1d</math> eta <math>b = k_2d</math> ditugu, <math>k_1, k_2 \in \Z</math> izanik. Gainera, <math>d = xa + yb</math> da, <math>x, y \in \Z</math> izanik.

Bestalde, <math>m = \mbox{mkt}(a,b)</math> denez, <math>m = k'_1a</math> eta <math>m = k'_2b</math> ditugu, <math>k'_1,k'_2 \in \Z</math> izanik.

<ol>
<li>
<p>
<math>md \mid ab</math>: 
</p>

<math>ab = ak_2d = bk_1d \implies \dfrac{ab}{d} = ak_2 = bk_1 \implies  \left\{ \begin{array}{ll}
              a \mid \dfrac{ab}{d} \\
              \\
              b \mid \dfrac{ab}{d}
       \end{array}\right\}
\implies m \mid \dfrac{ab}{d}</math>

(mkt Teoremaren arabera) <math>\implies md \mid ab.</math>
</li>

<li>
<p>
<math>ab \mid md</math>: 
</p>

<math>md = mxa + myb = k'_2bxa + k'_1ayb = (xk'_2 + yk'_1)ab \implies ab \mid md.</math>
</li>
</ol>

<math>\left. \begin{array}{ll}
                md \mid ab \\
                ab \mid md \\
          \end{array} \right\} \implies ab = md  \mbox{ edo } ab = -md \implies ab = md \quad (ab, md \in \Z^{+}\mbox{ direlako)}.</math> <math>\Box</math>

<span>'''Oharra.'''</span>
<math>a, b \in \Z^{+}</math> bi zenbakiak izanik, <math>\mbox{zkh}(a,b)</math> Euklidesen algoritmoa erabiliz kalkula dezakegu, eta <math>\mbox{mkt}(a,b)</math> kalkulatzeko, aurreko teorema erabili.

<span>'''4.30 Adibideak.'''</span>
<ol>
<li><p>
<math>\mbox{zkh}(250,12) = 2</math>; hortaz, <math>\mbox{mkt}(250,12) = \frac{250 \cdot 12}{2} = 1500</math> da.
</p></li>
<li><p>
<math>\mbox{zkh}(250,111) = 1</math>; hortaz, <math>\mbox{mkt}(250,111) = 250 \cdot 111</math> da.
</p></li>
<li><p>
<math>\mbox{zkh}(12,18) = 6</math>; hortaz, <math>\mbox{mkt}(12,18) = \frac{12 \cdot 18}{6} = 36</math> da.
</p></li>
</ol>

=== 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 <math>n \in \Z^{+}</math>, <math>n>1</math>, izanik, <math>n</math> lehena da edo <math>n</math> zenbaki lehenen biderketa bezala idatz daiteke era bakarrean, faktoreen ordena kontuan izan gabe.

Emaitza hori frogatu baino lehen bi lema hauek frogatuko ditugu.

<span>'''4.31 Lema.'''</span> [pab] <math>a,b,p \in \Z^{+}</math> izanik, <math>\, p</math> lehena izanik, 

<math>\, p \mid ab \implies (p \mid a) \, \mbox{ edo } \, (p \mid b).</math>

<span>'''Froga.'''</span>

Demagun <math>p \mid ab</math> betetzen dela; hau da, <math>\, ab = kp, \quad k \in \Z \, \mbox{ izanik}.</math> 

Bietako bat <math>p \mid a</math> edo <math>p \mid b</math> betetzen dela frogatu behar dugu.

Horretarako, <math>p \not | \, a</math> betetzen dela pentsatuko dugu eta, orduan, <math>p \mid b</math> betetzen dela ikusiko dugu.

Izan bedi <math>d = \mbox{zkh}(a,p)</math>.

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

Orduan, hau lortuko dugu: 

<math>\mbox{zkh}(a,p) = 1 \implies 1 = xa + yp, \quad x, y \in \Z \, \mbox{ izanik } \implies</math> 

<math>\implies b = xab + ypb = xkp + ypb = (xk + yb)p, \quad xk + yb \in \Z \, \mbox{ izanik } \implies p \mid b.</math> <math>\Box</math>

<span>'''4.32 Lema.''' </span> [pab2] <math>a_1, \ldots, a_n, p \in \Z^{+}</math> izanik, <math>\, p</math> lehena izanik, 

<math>p \mid a_1\cdots a_n \, \Longrightarrow \, p \mid a_j, \, \, j \in \{1, \cdots, n\}\mbox{ baterako}.</math>

<span>'''Froga.'''</span>

Demagun <math>p \mid a_1\cdots a_n</math> betetzen dela.

<math>n</math>-ren gaineko indukzioa erabiliz frogatuko dugu <math>j \in \{1, \cdots, n\}</math> baterako <math>p \mid a_j</math> beteko dela.

<math>n = 1</math> denean, ez dago zer frogatu, <math>p \mid a_1</math> betetzen da.

Demagun propietate hori betetzen dela <math>n = k</math> denean, eta izan bedi <math>n = k+1</math>.

Orduan, <math>p \mid a_1 \cdots a_n = a_1 \cdots a_ka_{k+1} = (a_1 \cdots a_k)a_{k+1}.</math>

[pab] Lema aplikatuz, <math>p \mid a_1 \cdots a_k</math> edo <math>p \mid a_{k+1}</math> lortuko dugu.

<math>p \mid a_1 \cdots a_k</math> betetzen bada, indukzio-hipotesiaren arabera, <math>p \mid a_j \, \mbox{ beteko da, } \, j \in \{ 1, \cdots, k \} \subset \{ 1, \cdots, k+1 \} = \{ 1, \cdots, n \} \, \mbox{ baterako}.</math>

<math>p \mid a_{k+1}</math> betetzen bada, <math>\, p \mid a_j</math> betetzen da, <math>j = k+1 \in \{ 1, \cdots, k+1 \} = \{ 1, \cdots, n \}</math> kasurako. <math>\Box</math>

<span>'''4.33 Adibidea.'''</span> Ikus dezagun <math>\sqrt{2}</math> zenbaki irrazionala dela.

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

<math>\sqrt{2} = \dfrac{a}{b}</math>, non <math>a,b \in \Z</math> eta <math>\mbox{zkh}(a,b) = 1</math> diren.

Hortik, 

<math>\sqrt{2} = \dfrac{a}{b} \implies 2 = \dfrac{a^2}{b^2} \implies 2b^2 = a^2 \implies 2 \mid a^2 = a \cdot a</math> 

atera dezakegu. [pab] Lema aplikatuz, <math>2 \mid a</math> ateratzen dugu. Eta hortik, 

<math>2 \mid a \implies a = 2k, \quad k \in \Z \, \mbox{ izanik } \implies 4k^2 = a^2 = 2b^2, \quad k \in \Z \, \mbox{ izanik } \implies b^2 = 2k^2, \quad k^2 \in \Z \mbox{ izanik } \implies 2 \mid b^2 = b \cdot b.</math>

[pab] Lema aplikatuz, <math>2 \mid b</math> ateratzen dugu.

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

<span>'''4.34 Teorema.''' </span> Aritmetikaren oinarrizko teorema

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

<span>'''Froga.''' </span>

Izan bedi <math>S</math> multzo hau: 

<math>S := \{ n \; : \; n \in \Z^{+}, n > 1, n \mbox{ ezin da adierazi zenbaki lehenen biderketa bezala} \}.</math>

Absurdora eramanez, <math>S = \emptyset</math> dela frogatuko dugu. Horretarako, <math>S \neq \emptyset</math> dela pentsatuko dugu.

Ordena onaren printzipioaren arabera, <math>S</math> multzoak elementu minimoa izango du; izan bedi <math>m = \min S</math>. <math>m \in S</math> denez, <math>m</math> ez da lehena eta, hortaz, <math>m = m_1m_2</math> izango da, <math>1 < m_1 < m</math> eta <math>1 < m_2 < m</math> izanik.

<math>m_1 < m = \min S</math> eta <math>m_2 < m = \min S</math> direnez, <math>m_1, m_2 \not \in S</math> beteko da; beraz, badago <math>m_1</math> eta <math>m_2</math> lehenen biderketa bezala adieraztea; eta hori <math>m \in S</math> hipotesiaren kontra doa.

Ondorioz, <math>S = \emptyset</math> da. Hortaz, edozein <math>n \in \Z^{+}</math>, <math>n > 1</math>, izanik, <math>n</math> zenbakiaren faktorizazioa lor dezakegu zenbaki lehenekin.

Faktorizazioa bakarra dela frogatzea baino ez da geratzen. <math>n</math>-ren gaineko indukzioz frogatuko dugu.

<ul>
<li><p>
<math>n=2</math> denean (lehenengo kasua), nabaria da faktorizazioa bakarra dela: <math>n=2</math> da.
</p></li>
<li><p>
Demagun faktorizazioa bakarra dela <math>n = 3, \ldots, k</math> kasuetarako (indukzio-hipotesia) eta froga dezagun <math>n = k+1</math> kasuan ere bakarra dela.
</p>
<p>
Horretarako <math>k+1</math> zenbakiak bi faktorizazio onartzen dituela pentsatuko dugu: 
</p>
<p>
<math>k+1 = p_{1}^{s_1} \cdots p_{r}^{s_r}</math>, <math>p_1 < \cdots < p_r</math> zenbaki lehenak eta <math>s_i > 0</math>, <math>i = 1, \ldots, r</math>, izanik;
</p>
<p>
<math>k+1 = q_{1}^{t_1} \cdots q_{u}^{t_u}</math>, <math>q_1 < \cdots < q_u</math> zenbaki lehenak eta <math>t_i > 0</math>, <math>i = 1, \ldots, u</math>, izanik.
</p>
<p>
Frogatu beharko dugu <math>r = u</math> eta <math>p_i = q_i</math>, <math>s_i = t_i</math> direla, <math>i = 1, \ldots, r</math> kasuetan.
</p>
<p>
<math>p_1 \mid k+1 = q_{1}^{t_1} \cdots q_{u}^{t_u}</math> betetzen denez eta <math>p_1</math> zenbaki lehena denez, [pab2] Lemaren arabera, <math>p_1 \mid q_j</math> beteko da <math>j \in \{1, \ldots, u\}</math> baterako. <math>p_1, q_j</math> zenbaki lehenak direnez eta <math>p_1 \mid q_j</math> betetzen denez, <math>p_1 = q_j</math> bete beharko da.
</p>
<p>
Ikus dezagun, absurdora eramanez, <math>j = 1</math> dela. Demagun <math>j \neq 1</math> dela, kontraesan batera helduko gara. <math>j > 1</math> denez, <math>q_1 < q_j</math> izango da. <math>q_1 \mid k+1 = p_{1}^{s_1} \cdots p_{r}^{s_r}</math> denez eta <math>q_1</math> zenbaki lehena denez, [pab2] Lemaren arabera, <math>q_1 \mid p_i</math> beteko da <math>i \in \{1, \ldots, r\}</math> baterako. <math>q_1, p_i</math> zenbaki lehenak direnez eta <math>q_1 \mid p_i</math> denez, <math>q_1 = p_i</math> bete beharko da. Orduan, <math>p_1 \leq p_i = q_1 < q_j = p_1</math> izango dugu, eta hor dago kontraesana.
</p>
<p>
Hortaz, <math>j = 1</math> eta <math>p_1 = q_1</math> beteko dira.
</p>
<p>
Izan bedi <math>n_1 := \frac{k+1}{p_1} = \frac{k+1}{q_1}</math>. <math>\, n_1</math> zenbakiaren bi faktorizazio dauzkagu: 

<math>\quad \left\{ \begin{array}{lll}
            n_1 = p_{1}^{s_1-1} \cdots p_{r}^{s_r}, \\
            \\
            n_1 = q_{1}^{t_1-1} \cdots q_{u}^{t_u}.
\end{array} \right.</math> 
</p>
<p>
Baina, <math>n_1 < k+1</math> denez, indukzio-hipotesiaren arabera, <math>\, n_1</math> zenbakiak faktorizazio bakarra dauka; beraz, hau dena beteko da: <math>\, r = u</math>, <math>\, p_i = q_i</math>, <math>i = 1, \ldots, r</math> guztietarako, eta <math>\, s_1-1 = t_1-1</math> (hots, <math>s_1 = t_1 \,</math>) eta <math>\, s_i = t_i</math>, <math>\, i = 2, \ldots, r</math> guztietarako.
</p>
</li></ul>
<math>\Box</math>

<span>'''4.35 Adibidea.'''</span> Kalkula dezagun <math>6552</math> zenbakiaren faktorizazioa zenbaki lehenekin:

* <math>2 \mid 6552</math>: <math>\quad 6552 = 2 \cdot 3276.</math>
* <math>2 \mid 3276</math>: <math>\quad 3276 = 2 \cdot 1638 \implies 6552 = 2^2 \cdot 1638.</math>
* <math>2 \mid 1638</math>: <math>\quad 1638 = 2 \cdot 819 \implies 6552 = 2^3 \cdot 819.</math>
* <math>2 \not | \,819</math>; <math>\, 3 \mid 819</math>: <math>\quad 819 = 3 \cdot 273 \implies 6552 = 2^3 \cdot 3 \cdot 273.</math>
* <math> 3 \mid 273</math>: <math>\quad 273 = 3 \cdot 91 \implies 6552 = 2^3 \cdot 3^2 \cdot 91.</math>
* <math>3 \not | \,91</math>; <math>\, 5 \not | \,91</math>; <math>\, 7 \mid 91</math>: <math>\quad 91 = 7 \cdot 13 \implies 6552 = 2^3 \cdot 3^2 \cdot 7 \cdot 13.</math>
* <math>13</math> lehena da; beraz, bukatu dugu.

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

== 4.2 Aritmetika modularra ==
Atal honetan, zenbaki osoak <math>n</math> zenbakiaz [[#zatiketa_euklidearra|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, <math>n</math> moduluko kongruentziaren definizioa eman genuen:

<math>a \equiv b \pmod n \iff n \mid a - b \iff \exists k \in \Z \, / \, a = b + kn.</math>

Kasu horretan, <math>a-b</math> zenbakia <math>n</math>-ren multiploa da.

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

<math>a,b \in \Z</math> izanik, <math>b > 0</math>, <math>\exists ! q \in \Z \; \; \exists ! \in \Z,</math> non <math>a = qb + r</math> den, <math>0 \leq r < b</math> izanik.

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

Horren arabera, hondar posible guztiak <math>0</math>, <math>1</math>, <math>\dots</math>, eta <math>b-1</math> dira.

<span>'''Oharrak.''' </span>
<ol>
<li>
Euklidesen teorema eta kongruentziaren definizioa kontutan izanik, <math>a  \equiv b \pmod n</math> bada, hau da, <math>a - b = kn</math> bada, <math>a</math> eta <math>b</math> zenbakiek hondar bera emango dute <math>n</math> zenbakiaz zatitzean; izan ere, <math>b</math> zenbakiak <math>r</math> hondarra ematen badu, <math>b = q n + r</math> izango da; bestalde <math>a - b = kn</math> denez, eta <math>a = b + (a - b)</math> denez, <math>a = q n + r + k n</math> izango da; ondorioz, <math>a = ( q + k ) n + r</math> dela esan dezakegu; beraz, <math>a</math> zenbakiak, <math>n</math> zenbakiaz zatitzean, <math>r</math> hondarra emango du, alegia, <math>b</math> zenbakiak ematen duen hondar bera:

<math>\begin{array}{rl}
            b & \underline{\vline  n}  \\
            r & q \\
\end{array} \quad b = qn + r, \quad 0 \leq r < n. \quad \quad  
\begin{array}{rl}
      a & \underline{\vline  n}  \\
      r & q+k \\
\end{array} \quad a = (q+k)n + r, \quad 0 \leq r < n.</math>
</li>

<li>
<p>
<math>n</math> moduluko kongruentzian, zatitzailea <math>n</math> denez, hondar posible guztiak  <math>0</math>, <math>1</math>, <math>\dots</math>, eta <math>n-1</math> dira eta, ondorioz, <math>n</math> moduluko hondarren multzoa <math>\Z_n = \{0,1, ..., n-1 \}</math> da.
</p>
<p>
Multzo horretan <math>n</math> elementu besterik ez dago, eta <math>\Z</math> multzoko elementu oro <math>\Z_n</math> multzoko elementu bakarrarekin erlazionatuta dago ([nmodbalerl] Teorema: <math>n</math> moduluko kongruentzia baliokidetasun-erlazioa da). Hau da, <math>\Z</math> multzoari <math>n</math> klase dituen partiketa eragiten dio erlazio honek.
</p>
</li>
</ol>

=== 4.2.2 Eragiketa modularrak ===

<span>'''4.36 Definizioa.'''</span> <math>\Z_n</math> multzoan, '''batuketa''' eta '''biderketa modularra''' honela definitzen dira:

<math>((a \pmod n) + (b \pmod n)) \pmod n = (a+b) \pmod n.</math>

<math>((a \pmod n) \cdot (b \pmod n)) \pmod n = (a\cdot b) \pmod n.</math>

<span>'''Zatiketa'''</span> ez dago <math>\Z_n</math> multzoko elementu guztietarako definituta, eta egin daitekeenean alderantzizko modularraz biderkatuz kalkulatu ohi da.

<span>'''4.37 Definizioa.'''</span> 
<math>\Z_n</math> multzoan, <math>a</math> elementua '''alderantzikagarria''' da <math>\exists b \in \Z_n</math>, non  <math>a \cdot b = 1</math> den. <math>b</math> elementuari '''alderantzizko modularra''' deituko diogu eta <math>a^{-1}</math> idatziko dugu.

<span>'''Oharra.'''</span>
<math>\Z</math> multzoko elementu guztiek ez dute alderantzizkorik, ez eta <math>\Z_n</math> multzoko guztiek alderantzizko modularrik ere.

<span>'''4.38 Teorema'''</span> (Alderantzizko modularraren existentzia) 

<math>a^{-1} \pmod n</math> existitzen da baldin eta soilik baldin zkh<math>(a, n)=1</math>. <math>\Z_n</math> multzoan alderantzikagarri diren elementuen multzoa <math>\Z^{*}_n</math> da.

<math>\Z_n</math> multzoan alderantzikagarri diren elementuen multzoari '''hondarren multzo murriztu''' deitzen zaio eta  <math>\Z^{*}_n</math> idatziko dugu: <math>\Z^{*}_n=\{a \in \Z_n \, / \, \mbox{zkh}(a, n) = 1\}</math>.

Alderantzizko modularra existitzen denean, <math>a^{-1} \pmod n</math> kalkulatzeko, Euklidesen algoritmoa erabiliko dugu.

<span>'''Alderantzizko modularraren kalkulua'''</span>
Euklidesen algoritmoa erabiliz

Izan bitez <math>a,n \in \Z</math> zenbaki lehen erlatiboak; hots, zkh<math>(a, n)=1</math> da.

Dakigunez, <math>\exists x,y \in \Z</math>, non <math>xa + yn = \mbox{zkh}(a, n) = 1</math> den.

Hortik ondoriozta daiteke <math>a</math>-ren alderantzizko modularra <math>x</math> dela:
  
<math>xa + yn = 1 \implies  ax=1+(-y)n \implies  xa \equiv 1 \pmod n \implies a^{-1}\equiv x \pmod n.</math>

Euklidesen algoritmoa erabiliz <math>x</math> kalkulatuko dugu, hau da, <math>a^{-1}</math>.

=== 4.2.4 Euler-en eta Fermat-en teoremak ===

<span>'''4.39 Definizioa.'''</span> '''Euler-en <math>\phi(n)</math> funtzioa''' <math>n</math> moduluko hondarren multzo murriztuak duen elementu kopurua da, hau da, <math>\Z^{*}_n</math> multzoaren kardinala da: <math>\phi(n) = \mbox{card}(\Z^{*}_n)</math>. 

<span>'''4.40 Teorema.'''</span>
Izan bitez <math>p,q,n \in \Z</math>.
<ol>
<li>
<math>n</math> zenbakia lehena bada, <math>\phi(n)=n-1</math> da.
</li>
<li>
<math>n = pq</math> bada, <math>p</math> eta <math>q</math> bi zenbaki lehen desberdinak izanik, <math>\phi(n) = (p-1)(q-1)</math> da.
</li>
<li>
<math>n = p_1^{e_1} \cdots p_r^{e_r}</math> moduan deskonposa daiteke, <math>p_1, \ldots, p_r</math> lehen desberdinak izanik, <math>\phi(n) = \dfrac{n}{p_1 \dots p_r}(p_1-1)\dots (p_r-1)</math> da.
</li>
</ol>

<span>'''4.41 Teorema.'''</span> Euler-en teorema 

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

<span>'''4.42 Teorema.'''</span> Fermat-en teorema txikia 

Izan bedi <math>n \in \Z^{+}</math> zenbaki lehena. <math>a \in \Z^{+}</math> izanik, <math>a^{n-1} \equiv 1 \pmod n</math> betetzen da. 

<span>'''4.43 Korolarioa.'''</span>
<math>a,n \in \Z^{+}</math> badira, zkh<math>(a,n)=1</math> izanik, <math>a^{-1}\equiv a^{\phi(n)-1} \pmod n</math> betetzen da.

<span>'''Froga.'''</span>

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


<span>'''Oharrak:'''</span>

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

=== 4.2.5 Berreketa modularra ===

<math>a, x\in \Z</math>, <math>x\geq 0</math> izanik, <math>a^x</math> berreketa biderketen bidez kalkulatzean, <math>x</math> berretzailea handia denean bi arazo mota sortzen dira:

* <math>a^x</math> handiegia da. Kalkulatu nahi izateak arazoak sor ditzake!
* <math>a</math> zenbakia bere buruarekin <math>x-1</math> aldiz biderkatu behar da. Biderketa kopuru handia!

Aritmetika modularrean, <math>a^x \mbox{ mod } n</math> kalkulatzean:

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

<span>'''Berreketa bitarraren metodoa'''</span>

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

Berreketaren honako hiru propietateetan oinarritzen da: 
# <math> a^1=a,</math> 
# <math> a^{x+y}=a^x a^y,</math> 
# <math> a^{xy}=(a^x)^y</math>

== 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 '''R'''ivest, Adi '''S'''hamir eta Leonard '''A'''dleman-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 <math>\phi(n)</math> 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.

<span>'''Teorema.'''</span> 
Izan bedi <math>n=p\ q,</math> non <math>p</math> eta <math>q</math> zenbaki lehenak diren, eta izan bitez <math>r \equiv s^{-1} \pmod {\phi(n)}</math> eta <math> a < \min\{p,q\} </math>, non <math>\phi(n)=(p-1)(q-1)</math> Eulerren funtzioa den. Orduan, <math>a \equiv a^{r s} \pmod n</math> beteko da. 

<span>'''Froga.'''</span>

Teoreman zehaztu da <math>n</math> zenbakia <math>p</math> eta <math>q</math> bi zenbaki lehenen biderketa dela; beraz, badakigu  <math>\phi(n) = (p-1)(q-1)</math> dela. Bestalde, <math>r=s^{-1} \pmod {\phi(n)}</math> denez, alderantzizko modularraren definizioaren arabera, <math>r s \pmod {\phi(n)} = 1</math> izango da eta, ondorioz, badakigu <math>k \in \Z </math> badagoela, non <math>r s = 1+ k\phi(n)</math> beteko den; hortaz, <math>a^{r s} = a^{1+k \phi(n)}</math> beteko da.

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

Teorema horretan oinarritzen da RSA algoritmoa: <math>a</math> mezua bidali beharrean <math>z = a^r \pmod n</math> mezu zifratua bidaltzea proposatzen du algoritmoak; eta mezu hori deszifratzeko, <math>z^s \pmod n</math> kalkulatzea nahikoa da, bai baitakigu <math>z^s \pmod n = a^{r s} \pmod n = a</math> dela.

=== 4.3.3 Gako publikoa eta gako pribatua ===

Demagun <math>a</math> kodeak zifratu nahi dugun mezua adierazten duela. RSA algoritmoaren oinarriak kontuan hartuz, berreketa modularra erabiliz,  mezua bidali nahi duenak
<math display="block">z \equiv a^r \pmod n</math>
kalkulatu beharko luke. Beraz, <math>n</math> eta <math>r</math> zenbakiek ezagunak izan behar dute. Hain zuzen ere, gako publikoak bi zenbaki horiek dira.

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

Gako publikoa ezagutzera ematen bada, alegia <math>n</math> eta <math>r</math> zenbakiak publikoak badira, <math>n</math> zenbakiaren deskonposaketa eginez <math>p</math> eta <math>q</math> zenbakiak ezagutu daitezke eta, ondorioz, <math>\phi(n) = (p-1)(q-1)</math> ere ezagutzea lortuko genuke. Hori guztia ezagutuz, deszifratzeko falta zaigun bakarra <math>s</math> zenbakia da; eta <math>r \equiv s^{-1} \pmod {\phi(n)}</math> 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 <math>s</math> zenbaki sekretua kalkulatzeko behar den denborak ematen dio: lehen esan bezala, <math>n</math> 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, 
<math>p,</math> <math>q</math> eta <math>\phi(n)</math> ezezagunak izango dira, eta ezin izango da <math>s</math> kalkulatu.

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

=== 4.3.4 Gako publikoak eta pribatuak sortzeko prozedura ===

Adierazi dugun bezala, <math>r \equiv s^{-1} \pmod {\phi(n)}</math> bete behar da, horrek ziurtatzen baitu <math>r\ s = 1 + k\ \phi(n)</math> dela, non <math>k \in \Z</math> baita.

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

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

Beraz, <math> n </math> zenbakia zehazteko, <math>p</math> eta <math>q</math> zenbaki lehenak aukeratu behar izan ditugu, eta bi zenbaki horiek zehazten dute  <math> \phi(n)</math> zenbakia, bai eta <math> \Z_{\phi(n)}</math> multzoa ere.

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

Laburbilduz, prozedurak urrats hauek ditu:
# Aukeratu <math>p</math> eta <math>q</math> zenbaki lehenak eta oso handiak
# Aukeratu <math> \phi(n) = (p-1)(q-1) </math> zenbakiarekiko lehena izango den <math> s </math> zenbakia.
# Kalkulatu  <math> r=s^{-1} \pmod {\phi(n)}</math> zenbakia.
# Publikatu <math>n</math> eta <math>r</math> gako publikoak eta ezkutuan ondo gorde <math>n</math> eta <math>s</math> 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 <math>(n,r)</math> 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 <math>a</math> baldin bada, 
<math display="block"> z = a^r \pmod n</math> 
kalkulatu behar dugu, eta Jasoneri <math> z</math> bidaliko diogu.

Jasonek, beraz, <math>z</math> mezu zifratua jasoko du, eta mezua deszifratzeko, <math display="block">z^s \pmod n</math> 
kalkulatu beharko du. Baina badakigu eragiketa horren emaitza <math>a</math> 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 <math>a</math> mezua bere gako pribatuarekin zifratuta 
<math display="block">z = a^s \pmod n</math> 
lortuko du <math>z</math> mezu ziurtatua; eta hori bidaliko baligu, guk 
<math display="block">a = z^r \pmod n</math> 
kalkulatu beharko genuke, eta horrela lortutako <math>a</math> mezuak zentzurik balu, esan ahal izango genuke Jasonek sortutako mezua dela.