Basic HTML Version
közötti számmal sem.
Mivel az osztók párokba rendezhetők úgy, hogy a párok tagjainak szorzata a me
szám lesz (osztópárok), és
√
199
≈
14 12, elég a 15-nél kisebb számokról el
nünk, hogy van-e közöttük olyan, amely osztója a 199-nek, mivel egy 14-nél na
osztó párja biztosan nem nagyobb, mint 14 (14
·
15 = 210).
Ráadásul ha beláttuk, hogy a 199-nek nem osztója egy szám, akkor kizárhatjuk a
többszöröseit is, hiszen azokkal sem lehet osztható. Elég tehát a prímszámokka
oszthatóságot vizsgálnunk.
A fentiek alapján tehát csak a 2-vel, 3-mal, 5-tel, 7-tel, 11-gyel és 13-mal való
hatóságot kell megvizsgálnunk:
A 199 nem osztható 2-vel és 5-tel, mivel utolsó számjegye 9, amely nem os
2-vel és 5-tel sem.
A 199 nem osztható 3-mal, mivel számjegyeinek összege 19, amely nem os
3-mal.
A maradékos osztásokat elvégezve látható, hogy a 199 nem osztható 7-tel, 1
és 13-mal sem. (199 = 7
·
28 + 3 = 11
·
18 + 1 = 13
·
15 + 4)
Tehát a 199 prímszám.
A fentiekből láthatjuk, hogy annak ellenőrzése, hogy egy szám prímszám-e,
szonylag kicsi számok esetén sem egyszerű feladat. Nagy számok esetén a fel
szinte beláthatatlanul bonyolulttá válik, még a leggyorsabb számítógépek is
lassan birkóznak meg vele.
A 2013-ban ismert legnagyobb prímszám a 2
57885161
−
1.
Két prímszámot összeszorozni meglehetősen egyszerű feladat. Még ha a két s
százjegyű is, a szorzást egy modern számítógép alig 10 másodperc alatt végz
Azonban a két százjegyű prímszám meghatározása a szorzatuk ismeretébe
tudomány mai állása szerint, a legkorszerűbb számítógépek felhasználásáv
nagyon időigényes. Ha az egyik prímszámot valamilyen módon mégis megtud
a másik szorzótényező megtalálása ismét könnyű feladattá válik: egyetlen os
elvégzését igényli.
Ez a számítógépek által használt
titkosítási eljárások
alapja.
TEX 2013. június 30. –
(13. lap/47. old.)
∗
Matematika 9.
∗
(08SZ)
C
M
Y
K