75
Izrek: Praštevil je neskončno mnogo.
Osnovni izrek aritmetike
Dokaz:
Vsako naravno število n lahko na en sam način (do vrstnega reda faktorjev natančno) zapišemo kot produkt potenc s praštevilskimi osnovami:
Izrek bomo dokazali tako kot ga je Evklid pred več kot 2300 leti. Recimo, da smo pri iskanju praštevil prišli do k-tega praštevila in se vprašamo, ali obstaja praštevilo, ki je večje od njega. Do odgovora pridemo tako, da sestavimo število, ki je produkt vseh znanih, po velikosti urejenih praštevil, povečan za 1:
n = p1n1 · p2n2 · … · pknk,
N = 2 · 3 · 5 ·…· pk + 1. Število N je očitno večje od vsakega od praštevil 2, 3, 5, …, pk, zato je ali praštevilo ali sestavljeno število. Če je N praštevilo, je izrek že dokazan, saj smo dobili novo, od pk večje praštevilo. Če pa je N sestavljeno število, mora biti deljivo z vsaj enim praštevilom – imenujmo ga p. Število N je za 1 povečan produkt vseh znanih praštevil, zato pri deljenju z vsakim od praštevil 2, 3, 5, …, pk ostane 1. Iz tega sledi, da je p od 2, 3, 5, …, pk večje praštevilo, kar potrjuje sklep, da je praštevil več kot k. Tako v vsakem primeru obstaja praštevilo, večje od pk, iz česar sklepamo, da je seznam praštevil neskončen.
pri čemer so p1, p2, …, pk praštevila. Zgled 4
CA
CA
11
12
13
14
5
6
7
8
9
10
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
IČI
Zgled 5
RA
Zapišimo in preštejmo vse delitelje števila 60.
NA
4
Delitelje najlaže preberemo iz števila, zapisanega kot produkt prafaktorjev: 60 = 22 · 3 · 5. Eratosten (280–196 pr. Kr.) je večino svojega življenja preživel v Aleksandriji v Egiptu, kjer je bil glavni knjižničar v tistem času največje knjižnice na svetu. Hranila je kar 700 000 knjig. Tako je imel pri roki vse opise tedanjih znanstvenih odkritij. Poleg geografije in matematike sta ga zanimali tudi fizika in astronomija, kot večina tedanjih učenjakov pa se je ukvarjal še s filozofijo in gramatiko ter pisal pesmi.
Delitelji števila 60 so: 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30 in 60.
LO V
3
1024 = 210
Vseh deliteljev števila 60 je 12. Zgled 6
Ali izraz n3 + 7n2 – 8n za vsako naravno število n predstavlja sestavljeno število? Izraz razcepimo: n3 + 7n2 – 8n = n(n2 + 7n – 8) = n(n – 1)(n + 8). Število ni sestavljeno, če je n enak 0, 1 ali –8. Ker 0 in –8 nista naravni števili, ju ne potrebujemo upoštevati.
DE
2
LO V
1
NA
RA
ZL
IČI
Praštevila do nekega ne prevelikega naravnega števila je znal poiskati že starogrški učenjak Eratosten iz Cirene (sicer bolj znan po tem, da je za tisti čas izredno natančno izmeril polmer Zemlje). Po njegovem receptu moramo za iskanje praštevil do naravnega števila n2 poznati vsa praštevila do n. Najprej napišemo vsa števila do n2 in potem med njimi prečrtamo vse mnogokratnike števila 2, ki so večji od 2. Prvo število, ki ostane neprečrtano, je praštevilo 3. Nato prečrtamo vse mnogokratnike števila 3, ki so večji od 3 (4 je prečrtana že od prej), in je prvo neprečrtano število praštevilo 5. Tako nadaljujemo in vedno je prvo neprečrtano število praštevilo. Postopek, ki mu rečemo tudi Eratostenovo sito, je enostaven, vendar zelo zamuden, če želimo poiskati malo večja praštevila. Poglejmo si primer za n = 10.
ZL
Zgled 3
Števila 1024, 7150 in 22 491 zapišimo kot produkt praštevil. 1024 2 7150 2 22491 3 512 2 3575 5 7497 3 256 2 715 5 2499 3 128 2 143 11 833 7 64 2 13 13 119 7 32 2 1 17 17 16 2 1 7150 = 2 · 52 · 11 · 13 8 2 22 491 = 33 · 72 · 17 4 2 2 2 1
Video razlaga dokaza
DE
74
Izraz je sestavljeno število za vsako naravno število n > 1. Pri n = 1 pa je izraz enak 0. Zgled 7
Zapišimo število, če vemo, da zanj veljajo naslednje trditve: T1: Število ni liho. T2: Ima 4 delitelje.
Ko želimo število zapisati kot produkt potenc, ga zaporedoma delimo s praštevili, s katerimi je dano število deljivo: najprej z 2, potem s 3, s 5, s 7 …, dokler ne pridemo do količnika 1. Ta postopek ima vedno končno mnogo korakov, saj se z vsakim deljenjem število manjša, ker pa delimo naravna števila, kvocient ne more biti manjši od 1. Zapis naravnega števila kot produkt potenc s praštevilskimi osnovami imenujemo tudi praštevilski razcep.
T3: Brano od desne proti levi je praštevilo. T4: Vsota njegovih števk je dvomestno praštevilo. T5: Je manjše od 100. T6: Ena od njegovih števk je popolni kvadrat.