ZT Hiztegi Berria

zenbaki-teoria

1. Mat.

Zenbakiak, oro har, eta batez ere zenbaki osoak eta haien arteko erlazioak aztertzen dituen matematikaren atala. Garai batean, 'aritmetika' eta 'goi-aritmetika' erabili zen matematika puruaren atal hau izendatzeko. Hainbat azpiatal ditu: zenbakien oinarrizko teoria, zenbaki-teoria analitikoa, zenbaki-teoria aljebraikoa, zenbaki-teoria geometrikoa, zenbaki-teoria konbinatorioa eta zenbaki-teoria konputazionala. Arazo teorikoak aztertzen ditu, baina baditu aplikazio praktiko garrantzitsuak ere; adibidez, kriptografian.

en number theory
es teoría de números
fr théorie des nombres

1. Mat.: Zenbakiak, oro har, eta batez ere zenbaki osoak eta haien arteko erlazioak aztertzen dituen matematikaren atala. Garai batean, 'aritmetika' eta 'goi-aritmetika' erabili zen matematika puruaren atal hau izendatzeko. Hainbat azpiatal ditu: zenbakien oinarrizko teoria, zenbaki-teoria analitikoa, zenbaki-teoria aljebraikoa, zenbaki-teoria geometrikoa, zenbaki-teoria konbinatorioa eta zenbaki-teoria konputazionala. Arazo teorikoak aztertzen ditu, baina baditu aplikazio praktiko garrantzitsuak ere; adibidez, kriptografian.

Zenbaki-teoria Edit

Egilea: Patxi Angulo Martin

ZENBAKI-TEORIA

Zenbaki-teoriak zenbaki osoen arteko zatigarritasuna aztertzen du bereziki. Zenbaki osoen $ℤ$ multzoan $(+)$ batuketa, $(\cdot)$ biderketa eta $(-)$ kenketa eragiketak definiturik daude; hau da, bi zenbaki oso batzen, bidertzen edo kentzen baditugu, emaitza zenbaki oso bat da. Aitzitik, $/$ zatiketa ezin da $ℤ$ multzoan egin beti: $2,3 \in ℤ$ , baina $2,3 \notin ℤ$ . Hala ere, kasu batzuetan, zenbaki oso batek beste zenbaki oso bat zehazki zatitzen du.

Zatigarritasuna. Zenbaki lehenak

Definizioa $a, b \in ℤ$ zenbakiak emanik eta $a \neq 0$ izanik, esango dugu $a$ zenbakiak $b$ zenbakia zatitzen duela, eta $a | b$ adieraziko dugu, baldin

$\exists k \in ℤ$ , non $b = k a$ den.

Hori gertatzen denean, esango dugu $a$ zenbakia $b$ zenbakiaren zatitzaile bat dela, edo $b$ zenbakia $a$ zenbakiaren multiplo bat dela.

Teorema $a, b, c \in ℤ$ emanik,

$1 | a, a | a, a | 0 (a \neq 0);$
$(a | b) \land (b | a) \Rightarrow a = b \lor a = - b (a \neq 0, b \neq 0);$
$(a | b) \land (b | c) \Rightarrow a | c (a \neq 0, b \neq 0);$
$a | b \Rightarrow (\forall x \in ℤ)$ $a | x b (a \neq 0);$

$(a | b) \land (a | c) \Rightarrow (\forall x, y \in ℤ)$ $a | x b + y c (a \neq 0).$

Definizioa Izan bedi $n \in ℤ^{+}$ , $n > 1$ .

Esango dugu $n$ zenbaki lehena dela bere zatitzaile positibo bakarrak $n$ eta 1 badira:

$m | n$ , $m \in ℤ^{+} \Rightarrow m = 1$ edo $m = n$ ;

eta esango dugu $n$ zenbaki konposatua dela lehena ez bada:

$\exists m_{1}, m_{2} \in ℤ^{+}$ , non $n = m_{1} m_{2}$ den, $1 < m_{1} < n$ , $1 < m_{2} < n$ izanik.

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.

Teorema Zenbaki konposatu orok zatitzaile lehenen bat dauka, hau da, $n \in ℤ^{+}$ , $n > 1$ emanik,

$n$ konposatua $\Rightarrow \exists p \in ℤ^{+}$ , $p$ lehena da eta $p | n$ .

Teorema Infinitu zenbaki lehen daude.

Froga

Absurdora eramanez frogatuko dugu.

Suposa dezagun zenbaki lehenen kopurua finitua dela: $p_{1}, \dots, p_{k}$ .

Izan bitez $a = p_{1} \cdot \dots \cdot p_{k}$ eta $A = a + 1$ .

Orduan, $p_{i} | a, i = 1, \dots, k,$ dugu eta, hortaz, $a \geq p_{i}, i = 1, \dots, k;$ hortik $A \neq p_{i}, i = 1, \dots, k,$ aterako dugu. Beraz, $A$ konposatua da. Aurreko teoremaren arabera, badago $p_{j} \in {p_{1}, \dots, p_{k}}$ zenbaki lehenen bat, non $p_{j} | A$ betetzen den.

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

Beraz, ezin da egon zenbaki lehenen kopuru finitu bat bakarrik, hau da, infinitu zenbaki lehen daude.

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 frogatu zuen zenbaki horiek bakarrak direla baldintza batzuk betez gero.

Teorema $a, b \in ℤ$ emanik eta $b > 0$ izanik,

$\exists | q \in ℤ$ $\exists | r \in ℤ$ , non $a = q b + r$ den, $0 \leq r < b$ izanik.

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

Adibidea

27	6		-27	6		6	27		-6	27
3	4		3	-5		6	0		21	-1

Zatitzaile komun handiena

Definizioa Izan bitez $a, b \in ℤ$ eta izan bedi $c \in ℤ^{+}$ . Esango dugu $c$ zenbakia $a$ eta $b$ zenbakien zatitzaile komun bat dela $c | a$ eta $c | b$ betetzen badira.

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. Bion zatitzaile positibo komunak 1, 2, 4 eta 8 dira.

Definizioa Izan bitez $a, b \in ℤ$ , $a \neq 0$ edo $b \neq 0$ , eta izan bedi $d \in ℤ^{+}$ . Esango dugu $d$ zenbakia $a$ eta $b$ zenbakien zatitzaile komun handienetako bat dela baldin

$d$ bada $a$ eta $b$ zenbakien zatitzaile komun bat:

$d | a$ eta $d | b;$
$a$ eta $b$ zenbakien edozein zatitzaile komunek $d$ zatitzen badu:

$(\forall c \in ℤ^{+})$ $c | a$ , $c | b \Rightarrow c | d.$

Adibidea Aurreko adibidean ikus dezakegu −24 eta 32 zenbakien zatitzaile komun handiena 8 dela.

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

Teorema $a, b \in ℤ$ emanik, $a$ eta $b$ zenbakien zatitzaile komun handiena existitzen bada, bakarra da.

Oharrak

$a, b \in ℤ$ emanik, $a$ eta $b$ zenbakien zatitzaile komun handiena badago, $zkh (a, b)$ adierazten dugu.
$zkh (a, b)$ badago, $zkh (b, a) = zkh (a, b)$ beteko da.
$zkh (0,0)$ ez dago definiturik.
$a \in ℤ^{*}$ bada, frogatu daiteke $zkh (a,0)$ badagoela eta $zkh (a,0) = | a |$ dela.

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

Teorema $a, b \in ℤ$ zenbaki oso positibo guztietarako existitzen da zatitzaile komun handiena.

Oharrak

Emaitza horretan oinarriturik, beste hau frogatu daiteke: $a, b \in ℤ^{+}$ emanik, beti existitzen da $zkh (a, b)$ $(a = b = 0$ denean izan ezik).
Aurreko teoremaren frogan agertzen da emaitza hau: $a, b \in ℤ$ emanik, $a \neq 0$ edo $b \neq 0,$ $zkh (a, b)$ izango da $a$ eta $b$ zenbakien konbinazio lineal gisa adieraz daitekeen zenbaki oso positiborik txikiena:

$zkh (a, b) = \min {x a + y b : x, y \in ℤ eta x a + y b > 0}.$
Aurreko oharrak esaten digu bi zenbakiren zatitzaile komun handiena bi zenbakien konbinazio lineala dela; baina konbinazio lineal hori ez da bakarra. $a, b \in ℤ$ emanik, $a \neq 0$ edo $b \neq 0,$ $zkh (a, b) = x a + y b$ da, $x, y \in ℤ$ izanik; baina $x, y$ ez dira bakarrak; izan ere, $zkh (a, b) = x a + y b$ bada, $p \in ℤ$ guztietarako hau beteko da:

$zkh (a, b) = (x + p b) a + (y - p a) b$ .

Adibidea $zkh (24,32) = zkh (- 24,32) = 8$ dugu; hortik,

$8 = (- 1) \cdot 24 + 1 \cdot 32 =$

$= 31 \cdot 24 + (- 23) \cdot 32 =$

$= (- 65) \cdot 24 + 49 \cdot 32 = \dots$

Definizioa $a, b \in ℤ$ emanik, esango dugu $a, b$ zenbaki lehen erlatiboak direla $zkh (a, b) = 1$ denean.

Ondorioa $a, b \in ℤ$ emanik,

$a, b$ lehen erlatiboak $\Leftrightarrow \exists x, y \in ℤ$ , non $x a + y b = 1$ den.

Adibidea $1 = (- 1) \cdot 3 + 1 \cdot 4$ denez, $zkh (3,4) = 1$ da eta $3,4$ zenbaki lehen erlatiboak dira.

Euklidesen algoritmoa

$a, b \in ℤ^{+}$ emanik, $b | a$ bada, $zkh (a, b) = b$ izango da. Bestela, $zkh (a, b)$ kalkulatzeko, algoritmo hau erabiliko dugu:

Euklidesen algoritmoa Zatiketa hauek egingo ditugu:

$a$	$b$	$a = q_{1} b + r_{1}$ ,	$0 < r_{1} < b;$
$r_{1}$	$q_{1}$	$a = q_{1} b + r_{1}$ ,	$0 < r_{1} < b;$
$b$	$r_{1}$	$b = q_{2} r_{1} + r_{2}$ ,	$0 < r_{2} < r_{1}$ ;
$r_{2}$	$q_{2}$	$b = q_{2} r_{1} + r_{2}$ ,	$0 < r_{2} < r_{1}$ ;
$r_{1}$	$r_{2}$	$r_{1} = q_{3} r_{2} + r_{3}$ ,	$0 < r_{3} < r_{2}$ ;
$r_{3}$	$q_{3}$	$r_{1} = q_{3} r_{2} + r_{3}$ ,	$0 < r_{3} < r_{2}$ ;
...		...	...
$r_{i}$	$r_{i + 1}$	$r_{i} = q_{i + 2} + r_{i + 1} + r_{i + 2}$ ,	$0 < r_{i + 2} < r_{i + 1}$ ;
$r_{i + 2}$	$q_{i + 2}$	$r_{i} = q_{i + 2} + r_{i + 1} + r_{i + 2}$ ,	$0 < r_{i + 2} < r_{i + 1}$ ;
...		...	...

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

$r_{k - 1}$	$r_{k}$		$r_{k - 1} = q_{k + 1} r_{k} + 0$ ;
$0$	$q_{k + 1}$		$r_{k - 1} = q_{k + 1} r_{k} + 0$ ;

$b > r_{1} > r_{2} > \dots > r_{k - 1} > r_{k} > 0 (= r_{k + 1})$ .

Orduan, 0 ez den azkeneko hondarra $zkh (a, b)$ da, hots,

$r_{k} = zkh (a, b).$

Adibidea $zkh (250,12)$ kalkulatzeko:

250	12		12	10		10	2
10	20		2	1		0	5

Hortaz,

$zkh (250,12) = zkh (- 250,12) = zkh (250, - 12) = zkh (- 250, - 12) = 2.$

Oharrak

Euklidesen algoritmoa bai $a > b$ denean bai $a < b$ denean erabil daiteke; azken kasu horretan, zatiketa bat gehiago egin beharko da.
Euklidesen algoritmoak $zkh (a, b)$ balioa $a, b$ zenbakien konbinazio lineal gisa adierazteko metodoa erakusten du.

Adibidea Aurreko adibidean, $zkh (250,12) = 2$ kalkulatu dugu. 2 emaitza 250 eta 12 zenbakien konbinazio lineal gisa adierazteko, 2 azkeneko hondar ez-nulua 10 eta 12 zenbakien konbinazio lineal gisa adierazten hasiko gara:

12	10		12 = 1 · 10 + 2,		2 = 12 $-$ 1 · 10.
2	1		12 = 1 · 10 + 2,		2 = 12 $-$ 1 · 10.

Orain, kontuan izanik 10 dela aurreko hondarra, 10 hori 250 eta 12 zenbakien konbinazio lineal gisa adieraz dezakegu:

250	12		250 = 20 · 12 + 10,		10 = 250 $-$ 20 · 12.
10	20		250 = 20 · 12 + 10,		10 = 250 $-$ 20 · 12.

Orduan, hau lortuko dugu:

2 = 12 − 1 · 10 = 12 − 1 · (250 − 20 · 12) = (−1) · 250 + 21 · 12.

Multiplo komun txikiena

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

Adibidea 40 zenbakia 2 eta 10 zenbakien multiplo komun bat da; izan ere, $2 | 40$ eta $10 | 40$ betetzen dira.

Definizioa Izan bitez $a, b, m \in ℤ^{+}$ , esango dugu $m$ zenbakia $a$ eta $b$ zenbakien multiplo komun txikiena dela $(m = mkt (a, b))$ $a$ eta $b$ zenbakien multiplo komunen artean zenbaki oso txikiena bada; hau da,

$m$ zenbakia $a$ eta $b$ zenbakien multiplo komun bat da:

$a | m$ eta $b | m;$
$a$ eta $b$ zenbakien edozein multiplo komun m baino handiago edo berdina da:

$(\forall c \in ℤ^{+})$ $a | c$ , $b | c \Rightarrow m \leq c.$

Adibidea 40 zenbakia 2 eta 10 zenbakien multiplo komuna da, baina ez da $mkt (2,10);$ izan ere, 20 ere 2 eta 10 zenbakien multiplo komuna da eta 20 ≤ 40 . Frogatu dezakegu $mkt (2,10) = 10$ dela:

$2 | 10$ eta $10 | 10$ .

$(\forall c \in ℤ^{+})$ $2 | c$ eta $10 | c$ betetzen badira, $10 | c$ da; beraz, $10 \leq c$ da.

Teorema $a, b, m \in ℤ^{+}$ emanik, $m = mkt (a, b)$ bada, $a$ eta $b$ zenbakien edozein multiplo komun $m$ zenbakiaren multiploa da:

$(\forall c \in ℤ^{+})$ $a | c,$ $b | c \Rightarrow m | c.$

Adibidea $mkt (12,18) = 36$ denez, 12 eta 18 zenbakien edozein multiplo komun 36 zenbakiaren multiploa da. (Esaterako, $36 | 72).$

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

Teorema $a, b \in ℤ^{+}$ emanik,

$a b = mkt (a, b) zkh (a, b).$

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

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

Aritmetikaren oinarrizko teorema

Aurreko teorema batean ikusi dugu edozein zenbaki konposatuk gutxienez zatitzaile lehen bat duela. Emaitza hura zabalduko dugu atal honetan, eta beste hau frogatuko dugu: $\forall n \in ℤ^{+}$ , $n > 1$ izanik, $n$ lehena da edo $n$ zenbaki lehenen biderketa gisa idatz daiteke era bakarrean, faktoreen ordena kontuan izan gabe.

Lema $a, b, p \in ℤ^{+}$ emanik eta $p$ lehena izanik,

$p | a b \Rightarrow (p | a)$ edo $(p | b).$

Lema $a_{1}, \dots, a_{n}, p \in ℤ^{+}$ emanik eta $p$ lehena izanik,

$p | a_{1}, \cdot \dots \cdot, a_{n} \Rightarrow p | a_{j}, j \in {1, \dots, n}$ baterako.

Teorema Aritmetikaren oinarrizko teorema

Edozein $n \in ℤ^{+}$ , $n > 1$ , emanik, $n$ lehena da edo $n$ zenbaki lehenen biderketa gisa idatz daiteke era bakarrean, faktoreen ordena kontuan izan gabe.

$n$ lehena bada, bera da faktore lehen bakarra.

Adibidea Kalkula dezagun 6.552 zenbakiaren faktorizazioa zenbaki lehenekin:

$2 | 6 .552 : 6.552 = 2 \cdot 3.276.$
$2 | 3 .276 : 3.276 = 2 \cdot 1.638$ $\Rightarrow$ $6.552 = 2^{2} \cdot 1 . 638.$
2 $∤$ 1 . 638: 1.638 = 2 ·819 $\Rightarrow$ $6.552 = 2^{3} \cdot 819.$
$2 | 8 19;$ $3 | 8 19 = 3 \cdot 273$ $\Rightarrow$ $6.552 = 2^{3} \cdot 3 \cdot 273.$
$3 | 2 73 : 273 = 3 \cdot 91$ $\Rightarrow$ $6.552 = 2^{3} \cdot 3^{2} \cdot 91.$
3 $∤$ 91; 5 $∤$ 91; 7 $∣$ 91: 91 = 7 · 13 $\Rightarrow$ $6.552 = 2^{3} \cdot 3^{2} \cdot 7 \cdot 13.$
$13$ lehena da; beraz, bukatu dugu.

6.552	2
3.276	2
1.638	2
819	3
273	3
91	7
13

$6.552 = 2^{3} \cdot 3^{2} \cdot 7 \cdot 13$ .

n moduluko kongruentzia

Definizioa Izan bedi $n \in ℤ$ , $n > 1$ . $a, b \in ℤ$ emanik, $a b$ -rekin kongruentea da $n$ moduluz , eta $a \equiv b (\mod n)$ idatziko dugu, $n | a - b$ bada, hau da, $\exists k \in ℤ$ , non $a = b + k n$ den.

Adibideak

$17 \equiv 2$ $(mod 5)$ da, $5 | 15$ betetzen delako.
$- 23 \equiv 5$ $(mod 6)$ da, $6 | - 18$ betetzen delako.

Teorema Izan bedi $n \in ℤ,$ $n > 1.$ $n$ moduluko kongruentzia baliokidetasun-erlazioa da $ℤ$ multzoan.

Baliokidetasun-erlazio honetarako zatidura-multzoa bi eratan adierazi ohi da, $ℤ / ℤ n$ edo $ℤ_{n}$ :

$ℤ / ℤ n = ℤ_{n} = {[x] : x \in ℤ}.$

Frogatu daiteke zatidura-multzoaren klaseak “zati $n$ " zatiketaren hondar posibleen bidez defini daitezkeela, eta guztira $n$ direla. $x \in ℤ$ emanik eta $x = q n + r$ bada, $q$ , $r \in ℤ$ eta $0 \leq r < n$ izanik, $[x] = [r]$ dela ondoriozta dezakegu. Bestalde, $r$ “zati $n$ " zatiketaren hondarra denez, $n$ hondar desberdin bakarrik egon daitezke:

$ℤ / ℤ n = ℤ_{n} = {[0], [1], \dots, [n - 1]}.$

Adibidea

$ℤ / ℤ 5 = ℤ_{5} = {[0], [1], [2], [3], [4]}.$

$22 \in [2]$ da, $22 = 4 \cdot 5 + 2$ delako.

$- 22 \in [3]$ da, $- 22 = (- 5) \cdot 5 + 3$ delako.

Egitura aljebraikoak

Orain, $ℤ$ eta $ℤ_{n}$ multzoetan defini daitezkeen egitura aljebraikoak aipatuko ditugu. Horretarako, $(+)$ batuketa eta $(\cdot)$ biderketa erabiliko ditugu.

$ℤ$ multzoari dagozkion egiturak:
- $(ℤ, +)$ egitura aljebraikoa talde abeldarra edo trukakorra da.
- $(ℤ, \cdot)$ ez da taldea; adibidez, $\exists 2^{- 1}$ .
- $(ℤ^{*}, \cdot)$ egitura ere ez da taldea; adibidez, $\exists 5^{- 1}$ .
- $(ℤ, +, \cdot)$ eraztun trukakor unitateduna da.
- $(ℤ, +, \cdot)$ egitura osotasun-eremua da, ez baitu zeroren zatitzailerik.
- $(ℤ, +, \cdot)$ ez da gorputza $ℤ$ multzoan ez baitaude bere elementu ez-nulu guztien alderantzizkoak.
$ℤ_{n}$ multzoari dagozkion egiturak:
- $(ℤ_{n}, +)$ egitura $n$ ordenako talde abeldar finitua da, $\forall n \in ℤ$ .
- Teorema $(ℤ_{n}^{*}, \cdot)$ egitura taldea da, baldin eta soilik baldin n zenbaki lehena bada.
  
  Adibidez, $(ℤ_{3}^{*}, \cdot)$ talde abeldarra da eta $(ℤ_{4}^{*}, \cdot)$ ez da taldea.
- $(ℤ_{n}, +, \cdot)$ eraztun trukakor unitateduna da, $\forall n \in ℤ$ .
- Teorema $(ℤ_{n}, +, \cdot)$ osotasun-eremua da baldin eta soilik baldin $(ℤ_{n}, +, \cdot)$ gorputza bada.
- Teorema $(ℤ, +, \cdot)$ gorputza da baldin eta soilik baldin $n$ lehena bada.
  
  Adibidez, $(ℤ_{2}, +, \cdot), (ℤ_{3}, +, \cdot), (ℤ_{5}, +, \cdot) \dots$ gorputzak dira.
  
  Bestalde, $(ℤ_{4}, +, \cdot), (ℤ_{6}, +, \cdot), (ℤ_{8}, +, \cdot) \dots$ ez dira gorputzak.