ISSN 0351-6652 Letnik 22 (1994/1995) Številka 6 Strani 340-341
Primož Potočnik: SUNDARAMOVO REŠETO
Ključne besede: matematika, teorija števil, praštevila. Elektronska verzija: http://www.presek.si/22/1238-Potocnik.pdf
© 1995 Društvo matematikov, fizikov in astronomov Slovenije © 2010 DMFA - založništvo
SUNDARAMOVO REŠETO
Vsi poznamo Eratostenovo rešeto, ki nam omogoča hitro in enostavno določiti poljubno mnogo začetnih prastevil. Manj znana in resnici na ljubo ne tako hitra pa je metoda, ki jo je se kot študent odkril indijski matematik S.P. Sundarama. Kaj nam torej svetuje naš indijski kolega?
1.	Vzemi prazen list papirja in v zgornji levi kot napiši število 4. Nadaljuj stolpec tako, da prejšnjemu številu prišteješ 3.
2.	k-to vrstico nadaljuj tako, da prejšnjemu Številu v vrstici prišteješ 2 k + L
Na ta način dobimo naslednjo tabelo;
A	7	10	13	16	
7	12	17	22	27	
10	17	24	31	38	
13	22	31	40	49	
16	27	38	49	60	
					
Opazimo, da stoji na presečišču k-te vrstice in n-tega stolpca število k + (2k + l)a = k + 2kn + n.
Sledi malce presenetljiva trditev
Za vsako naravno število, ki ga ni v tabeli, je njegov dvakratnik, povečan za 1, praštevilo. Še več, vsako liho praštevilo se da na takšen način dobiti iz naravnega števila, ki ga v tabeli ni.
V prvi del trditve se prepričamo takole; Vzemimo naravno število x, ki ga ni v tabeli. To pomeni, da se števila x ne da zapisati v obliki n + 2kn + k za nobeni naravni števili n in k. Dokazati moramo, da je število 2x + 1 praštevilo. Pa denimo, da ni. Tedaj se da zapisati kot produkt dveh od 1 različnih naravnih števil:
2x + 1 = ab; a, b G IN a / 1, b f 1
Ker je 2x + 1 liho število, morata biti lihi tudi števili a in b, To pa pomeni, da sta števili
a-l	b—l
K —-n-I	" = —
2 2
naravni števili Izračunajmo izraz:
,	3-1 (3-l)(b-l) b- 1 afa-1
+ * = — + 2^—--¿+ =
Potemtakem se število x nahaja v naši tabeli, in sicer na presečišču k-te vrstice in n-tega stolpca. To pa je v nasprotju z začetno predpostavko, da Števila x ni v tabeli. Do protislovja smo prišli, ker smo dodatno privzeli, da Število 2x H- 1 ni praštevilo. S tem je prvi del trditve dokazan.
Lotimo se še drugega dela. Vzemimo liho praštevilo p. Vsako liho od 1 večje naravno Število - in zato tudi p - se da na en sam način zapisati v obliki 2x + 1, kjer je x naravno število. Za število p poiščimo takšen x. Dokazati želimo, da števila x ni v tabeli. Pa recimo, da kljub vsemu x je v tabeli. Potem morata obstajati naravni števili k in n taki, da vefja: x = k + 2kn-\- n. Tedaj za p velja:
p = 2x 4-1 = 2n + Akn + 2k + 1 = (2n + 1 )(2k + 1).
PrašteviTo p smo torej razcepili na produkt dveh naravnih števil, ki sta različni od L To pa je po definiciji praštevila nemogoče. Predpostavka, da število x najdemo v tabeli, nas je torej pripeljala do protislovja, Tedaj pa ni druge, kot da priznamo, da ga v tabeli ni. S tem je trditev v celoti dokazana.
Primož Potočnik