i
i
“Lavric-prastevila” — 2010/6/14 — 9:09 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 16 (1988/1989)
Številka 2
Strani 82–89, 117
Boris Lavrǐc:
O PRAŠTEVILIH
Ključne besede: matematika, teorija števil, praštevila.
Elektronska verzija: http://www.presek.si/16/928-Lavric.pdf
c© 1988 Društvo matematikov, fizikov in astronomov Slovenije
c© 2010 DMFA – založništvo
Vse pravice pridržane. Razmnoževanje ali reproduciranje celote ali
posameznih delov brez poprejšnjega dovoljenja založnika ni dovo-
ljeno.
o PRASTEV ILlH
Dogovorimo se. da bomo tu z besedo število razumeli naravno število. torej
element množice N = { 1.2,3•... } . Ukvarjali se bomo namreč le z naravni-
mi števili. Brž ko želimo bolje spoznati njihove lastnosti. se srečamo s po-
membno družino števil. ki jim rečemo praštevila. Zanje je značilno. da .imajo
v množici N natanko po dva delitelja. Število n je torej praštevilo, če je večje
od 1 in ni produkt dveh od 1 različnih števil. Druga števila, razen 1, tedaj lahko
razstavimo v produkt z manjšima faktorjema in jih zato imenujemo sestavljena
števila. Z zapored nim razstavljanjem faktorjev v produkt, če je to potrebno, I
pridemo do naslednje znane in pomembne ugotovitve:
Vsako naravno število razen števila 1 je produkt samih praštevil.
Dognali bi lahko celo to. da je takšna razstavitev le ena, če ne gledamo na vrstni
red faktorjev v njej.
Praštevila so potemtakem osnovni sestavni deli vsakega naravnega števila,
zato jim namenimo nekaj več pozornosti.
Zapišimo po velikosti nekaj najmanjših zaporednih praštevil:
2,3,5,7,11 ,13,17,19,23,29,31 ,37,41 , ...
in se za hip pomudimo ob vprašanju. ali je vseh praštevil končno mnogo
ali ne. Že znameniti grški matematik Evklid se je ubadal s tem problemom in
ga tudi rešil. Dokazal je. da je praštevil brez konca, in to tako mojstrsko ute-
meljil. da bomo ponovili njegov dokaz. Takole teče:
Denimo. da so 2, 3. 5, ...• p zaporedna praštevila, in postavimo
n = 2·3·5··· p + 1. Potem n očitno ni deljiv z nobenim od praštevil 2.3,5•...• p.
Zato je n bodisi praštevilo ali pa je deljiv s praštevilom, ki je večje od p. V obeh
primerih obstaja praštevilo. večje od p, torej praštevil ni končno mnogo.
Veliko težje je zvedeti kaj več o gostoti porazdelitve praštevil v zaporedju
vseh naravnih števil. Kljub temu poznamo nekaj pomembnih rezultatov v tej
smeri, med katerimi je zelo lep naslednji.
IZREK: Naj bo naravno število n večje od 1. Potem med nin 2n obstaja
vsaj eno praštevilo.
Dokaz je prezahteven za naš list, iznašel pa ga je ruski matematik P.L. Čebi­
šev leta 1850. to je pet let po tem. ko je francoski matematik J. Bertrand
postavil domnevo. da navedeni izrek velja. Danes vemo. da za n > 5 med n in
2n obstajata vsaj dve praštevili .
82
Za svoja dela je Čebišev žel priznanja doma in v tujini, bil je član več aka- .
dem ij, v Franciji pa tudi vitez Legije časti. Med obiski v Parizu je večkrat preda-
val v Association Francaise pour I'avancement des sciences. Eno njegovih preda-
vanj, O krojenju oblek, je privabilo res številno in, lahko si mislimo, izbrano
poslušalstvo, snovalce in nosilce modnihkrikov. Po prvem stavku so se kot en
mož dvignili in zapustili dvorano. Čebišev je predavanje začel takole: Zaradi
enostavnosti privzemimo, da ima človeško telo obliko krogle. V resnici je šlo za
nalogo iz diferencialne geometrije, kako iz kosa ravnine (blaga) napraviti lupi-
no, ki se bo najbolje prilegala danemu telesu.
Anekdoto smo prepisali iz Križaničeve knjige Nihalo, prostor in delci,
Slovenska Matica (1982).
Ozrimo se spet na zaporedje vseh praštevil. Hitro opazimo, da si praštevila
ne slede enakomerno. Z izjemo para 2, 3 je razlika med sosednjima praštevilo-
ma tega zaporedja vedno sodo število, saj so vsa od 2 različna praštevila tiha. Že
na kratkem odseku zaporedja vseh praštevil najdemo sosednji praštevili, ki se
razlikujeta za 2, 4 , 6 ali 8 , te razlike pa so neenakomerno posejane. Ponujata
se nasledn ji vprašanji :
1. Kako na preprost način najti vsa praštevila, manjša od danega števila n?
2. Ali so razlike med sosednjimi praštevili lahko poljubno velike?
Zanimivo je odgovoril na prvo vprašanje grški astronom Eratosten(es) že
pred približno dva tisoč leti. Stopimo po njegovi poti.
Naravna števila od 2 do n razvrstimo po velikosti v naraščajoče zaporedje
in najprej obkrožimo praštevilo 2 ter prečrtamovse druge večkratnike števila 2.
Najmanjše neoznačeno število je zdaj praštevilo 3. Zato obkrožimo 3 in pre -
črtamo vse tiste njegove večkratnike, ki še niso prečrtani ali obkroženi. Naj-
manjše neoznačeno število je zdaj praštevilo 5, ki ga obkrožimo in nato pre -
črtamo vse njegove večje večkratnike. Če nadaljujemo na enak način, bomo
obkrožil i natanko vsa praštevila do n ,
Pravkar opisani postopek imenujemo Eratostenovo rešeto. Ni težko videti ,
da seje precej hitro - brž ko smo obkrožili prvo praštevilo, ki presega yn, nam
ostanejo neoznačenav zaporedju le še praštevila.
Enostavno konstrukcijo Eratostenovega rešeta, posebno pripravno za pra-
števila do 120, najdemo veni od Gardnerjevih knjig iz rekreacijske matematike.
Števila od 1 do 120 zapišemo v pravokotno tabelo 20 x 6, kot kaže slika .
Nato pri sejanju upoštevamo, da soda števila ležijo v drugem, četrtem in šestem
sto lpcu, večkratniku števila tri v tretjem (in šestem), petkratniki na vsaki peti
"naraščajoči" diagonali , večkratniki števila 7 pa na vsaki sedmi "padajoči"
83
2 3 4 56
61 64 66
67 68 69 0~1 72
/
73 74 75 76 n 78
/
79 80 81 82 83 84
/
85 86 87 88 89 90
/
91 92 93 94 95 96
/
97 98 99 100 101 102
103 104 10 106 107 108
/
109 1 O 111 11'2 113 114
115 116 117 118 119 12('
diagonali, začenši z drugo. V nekaj potezah nam tako na rešetu ostanejo na-
tančno vsa praštevila, manjša od 127.
Matematik S. Ulam si je na nekem dolgem sestanku preganjal dolgčas s
tem, da je na list narisal kvadratna mrežo in vanjo razvrščal po sp irali zapo -
redna naravna števila podobno kot na sliki 1. Nato se je pozabaval z obkroža-
vanjem vseh vpisanih praštevil in presenečen opazil, da se večinoma nahajajo
vzdolž nekaterih diagonalnih premic . Blizu središča ta lastnost še ni tako izrazi-
ta kot dlje od njega , kjer se tudi ohranja. Ulam je s pomočjo računalnika in
znane tabele praštevil uspel v laboratoriju izdelati sliko spirale, na kateri je
84
prvih 65 000 naravnih števi l. Izsek tega vzorca, ki ga imenujemo U/amov prt,
je na slik i 2 .
65 64 63 62 61 60 59 58 57
66 37 36 35 34 33 32 31 56
67 38 17 16 15 14 13 30 55
68 39 18 5 4 3 12 29 54
69 40 19 6 2 11 28 53
70 41 20 7 8 9 10 27 52
71 42 21 22 23 24 25 26 51
72 43 44 45 46 47 48 49 50
73 74 75 76 77 78 79 80 81
Slika 1 Slika 2
Števila na diagonali prta lahko izrazimo s preprosto formulo, ki jo dobimo
takole. Krenimo po spirain i poti iz sredine. Prvo število, ki ga srečamo na "na-
rašč aj oč i " glavni diagona li, zaznamujmo z al, naslednje z a2 in tako nadaljuj-
mo (to rej je a l = 3, a2 = 7, a3 = 13, ...). Od središča do al smo napravili en
ovinek in prešli dve po lji, od al do a2 smo spet enkrat zavili in prešl i štiri pol ja,
nato pa smo od a2 do a 3 potrebovali šest po lj. od an-1 do an pa je tedaj pot
do lga 2n kvadratov. Torej velja zveza an = an_ 1 + 2n. Če jo zaporedoma upo-
rabimo za n, n-l, n-2 , ... .• dobimo:
an=an_ 1 +2n=an _ 2 +2(n-l)+2n= ...
... =al + 2(2 + 3 + ... + n) = n2 + n + 1
in formula je tu : an = n2 + n + 1.
Če namesto z 1 v sredini začnemo z m, za števila na diagonali dobimo
formulo an = n2 + n + m . Pri m = 17 in pr i m = 41 dobimo dve izmed mnog ih
" f ormul za pra števlla" , ki j ih je že v 18. stoletju odkril veliki švicarski matema-
tik Leonhard Eu/er . Prva da praštevila za vsak n E { O. 1,2•. .., 15 }, druga (ki
je najbolj znana) pa celo za vsak n E { O. 1• ....• 39 } . To pomeni. da je diaqo-
nala kvadrata velikosti 40 x 40 na Ulamovem prtu . ki se začne v sredini z 41,
v celoti zapolnjena s praštevili.
85
''2""'",,91 n-1
11"8'
°3,\, ~
~- °1~
l ,1~
°2 ~
°4
On
293 283 281
233 229 227 223
181 179 173
239 139 137 131
103 101 97 277
241 73 71
107 53
79 43 127
191 109 59 41 167
47 67
307 193 61 271
149 83 89
113 163 269
151 157 211
311 197 199
251 257 263
313 317
86
Poslovimo se zdaj od prvega vprašanja in odgovorimo na drugo. V ta na-
men vzemimo poljubno število n > 2. zapišimo m = 2·3···n in si oglejmo za-
poredje m + 2. m + 3..... m + n. Število m + 2 je deljivo z 2. m + 3 s 3, ....
m + n pa z n. torej so vsa sestavljena. Razlika med sosednjima prašteviloma
(pred in po navedenem zaporedju) je vsaj n , nasploh pa poljubno velika.
Zanimiva je tudi druga skrajnost. Le praštevili 2 in 3 sta sosedni naravni
števili, parov praštevil, ki se razlikujeta za dve, pa je več. Rečemo jim pari
praštevil dvojčkov. Naštejmo nekaj najmanjših:
3.5; 5.7 ; 11.13; 17.19; 29.31 ; 41,43; 59,61; 71.73; ...
in povejmo, da je eden največjih znanih dvojčkov par 9.2 2 11 - 1.9.22 11 + 1
(števili imata v desetiškem zapisu po 65 cifer).
Je tudi teh parov brez konca. tako kot vseh praštevil? Vprašanje zveni
preprosto in je znano pod imenom problem praštevil dvojčkov. odgovora nanj
pa do danes še ne poznamo. Uvrščamo ga med najslavnejše nerešene matema-
tične probleme.
Kljub tem težavam o parih praštevil dvojčkov vendarle lahko nekaj pove-
mo. Poglejmo spet zaporedje praštevil in označimo pare dvojčkov:
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61 ,67 ..
Opazil i ste, da edino 5 nastopa v dveh parih dvojčkov . Dokažimo, da ima res
samo praštevilo 5 to lastnost.
Števila p, p + 2 in p + 4 pri deljenju s 3 dajo različne ostanke, zato je eno
od njih deljivo s 3. Če hočemo, da so vsa tri praštevila, mora biti p = 3, odko-
der sledi našatrditev.
Podobno doženemo naslednjo lastnost . Če sta prvo in zadnje število tro-
jice p, p + 1. p + 2 praštevili (dvojčka) in velja p > 3. potem je vmesno število
p + 1 deljivo s 6. Dokaz prepustimo bralcu. Razen v primeru (3. 5) je par
dvojčkov torej vedno oblike (6k - 1, 6k + 1), k E IN.
O tem, kako gosto so posejani pari dvojčkov v zaporedju vseh praštevil,
vemo bolj malo. Na začetku zaporedja jih srečamo mnogo, obsežnejša pre-
geldnica praštevil pa pokaže. da kasneje pari dvojčkov nastopajo vedno redke-
je. Pokažimo, da je med pari zaporednih praštevil neskončno takšnih , ki niso
pari dvojčkov .
Res, če je parov praštevil dvojčkov končno mnogo, potem to očitno drži.
V nasprotnem primeru pa poglejmo tiste pare zaporednih praštevil (P, qlo pri
katerih so (p - 2. p) pari dvojčkov. Takšnih parov je (po predpostavki)
neskončno in očitno, razen pri p = 5. nobeden ni par dvojčkov.
S tem smo trditev dokazali, toda žal nam pove bore malo . Vsaj to bi še
radi vedeli , če je praštevil, ki niso vključena v pare dvojčkov. tudi neskončno
mnogo. Če bi jih bilo le končno število. potem bi moralo biti parov praštevil
87
dvojčkov brez konca (vseh praštevil je neskončno), s tem pa " rešen " problem
praštevil dvojčkov. Toda ta je še nerešen, zato jih je končno mnogo. Je to res
dokaz? Seveda ne.
Za tehten odgovor na vprašanje, ki smo si ga postavili, bomo potrebovali
kanček znamenitega Dirichletovega izreka .
IZREK: Naj bosta a in b tuji naravni števili. Potem je v množici {ak + b:
k E IN} neskončnopraštevil.
Dokaz tega izreka, ki ga je nemški matematik P.G. Lejeune-Dirichlet
objavil leta 1837 , je težak in ni elementaren. Kasneje so ga drug i poenostavili,
toda tud i najpreprostejši znani dokaz je še vedno zelo zapleten in krepko pre-
sega Presekov okvir. Za nekatere posebne primere , npr. a = 4, b = 3 ali a = 6,
b = 5, je izrek vendarle mogoče preprosto dokazati . Ob tem se ne bomo za-
drževali, pač pa se lotimo zadane naloge.
Preverimo, da nobeno število oblike 21 k + 5, k E IN, ne more biti udele-
ženo v paru praštevi l dvojčkov. Res, za dve manjše število 21 k + 3 je deljivo
s 3, za dve večje število 21 k + 7 pa je delj ivo s 7. Obe sta večj i od 7 in zato ne
moreta biti praštevili. Po Dirichletovem izreku (za a = 21 in b = 5) je med šte-
vili 21 k + 5, k E IN, neskončno praštevil, ki po prejšnjem ne pripadajo parom
dvojčkov. Z enako lastnostjo se odlikujejo še mnoga druga zaporedja.
Naloga je rešena, naš izlet v svet praštevil pa sklenimo spreglednico prašte-
vii (z označenimi pari dvojčkov) in s kopico vprašanj.
2 31 73 127 179 233 283 353 419 467 547 607 661 739 811 877
3 37 79 131 181 239 293 359 421 479 557 613 673 743 821 881
5 41 83 137 191 241 307 367 431 487 563 617 677 751 823883
7 43 89 139 193 251 311 373 433 491 569 619 683 757 827887
11 47 97 149 197 257 313 379 439 499 571 631 691 761 829907
13 53 101 151 199263317 383443503577 641 701 769 839911
17 59 103 157 211 269 331 389449 509 587 643 709 773853919
19 61 107 163 223 271 337 397 457 521 593 647 719 787 857 929
23 67 109 167 ~27 277 347 401 461 523 599 653 727 797 859937
29 71 113 173229 281 349409 463 541 601 659 733 809 863941
1. Katera od števil 101, 1001, 10001 in 100001 so praštevila?
2. A li obstaja tak n E N, da so n, 2n + 1 in 5n - 1 hkrati praštevila?
3. H.E. Dudeney je leta 1907 ugotovil, da ima od (tedaj) znanih praštevil le
11 v desetiškem zapisu samo enke. Dokazal je, da so števila ak = 11...1
'--"...--J '
k
88
Mer je 3 lg k < 18, vsa swmuljma, In obi8vB vprdanje, Ee je kmm od 
litrwil ak, k > 18, pmbvilo. Eden od bralcw ja h a l u  ugowil, da ja &I 
a19 prabuilo. Tudi 8 2 3  je pr&milo, ni pa mano, Ee je med 3teviU ak 
neskcni5no pr&Wil, In na-adnje Se naloga, DOMI, de velja s k b :  Ce 
je a,, pdtwib,  je adi n pdbvilo. 
4. Dokdi, da sta mkwredni trdki: 
a) Pam praStRvil dvojdkov je kanEno mnap 
b) Le km&m rnnago h i  b rnndim C n2 - f : n E N 3 ima na- 
tanko air! delitelje v N. 
6. DokaZi, dr pmdukt prabwil dvojEkw pri &lje#lju s 36 da manek 36, Ee 
le ni to par (3,5). 
8, Poiei r n d  moredji C ak + b : k E N 1 , kjer sta na roljo tujl naravnl 
Hterili a in b, neskodino takih, kt ne vsnbujefo nobnega p r h i l a  h: pefav 
dvo&kw. 
Odgavore in r J i e  naiderte na stran! 1 17. 
I 1. Le 101 je prah~ilo. 2. ~enni&~Evs3,jevlaJenoodA~~ll2n+1In6n-1de~ivor3inzato 
Ilerunrljeno. Tord mom Mti n = 3, vendar mdl; v tern primeru wa tri gtovtla 
RFSO pr&e~ila. 
3. Denlmo, dm je k reot$vueno Stmilo. Tsrdaj velja: k = m-n (m > 1, n > 1) in 
ram 
11 ... 1-11 ...lolO,.O1O...O...lQ...O1 - -  
k n D n n 
4. h i l o  n2 - 1 = (R - l ) (n  f 11 Ima Wnrr Wri detitelje le, Wje 
(n - 1, R * 1) par pr&tmtl draj&kosou. 
. Vmk par rdvoj&kav, razllbn od 43, 61, je oblib (8k - 1,Gk + 1 ), k E N, 
tomi ja paoduk && prltgtwil en& 3 6 p  - 1. 
6. Naj bo b > 3 poljubno llho M l o  in a = (b - 2)(6 + 21. Potem sta Saevili 
sinbtoji,gtevilfsk+b-2inek+b+2parer~nrljenlza~kEN. 
Boris LevriC