Chyba każdy zna algorytm uzyskiwania liczb pierwszych, zwany „sitem Eratostenesa”. Wypisujemy wszystkie liczby naturalne po kolei (oczywiście, w praktyce skończymy na jakiejś liczbie N), następnie zaś szukamy pierwszej liczby pierwszej; jest nią, oczywiście, dwa. Zostawiamy ją w spokoju, z naszego ciągu wykreślamy zaś wszystkie liczby podzielne przez 2. Następnie szukamy kolejnej liczby pierwszej; znajdujemy 3. Znów ją zostawiamy, wykreślamy natomiast wszystkie liczby podzielne przez 3. Teraz kolejną liczbą w naszym ciągu jest 5 (bo 4 zostało już wykreślone, jako podzielna przez 2); to znów jest liczba pierwsza, więc ją zostawiamy, wykreślając liczby podzielne przez 5. I tak dalej. W ten sposób liczby pierwsze zostaną „odsiane”.

A oto inne sito na liczby pierwsze, bardzo podobne w działaniu. Skonstruowane zostało mniej więcej w połowie ubiegłego wieku przez hinduskiego matematyka Sundarma.

Weźmy najpierw pod uwagę taki oto ciąg liczb naturalnych:


Nietrudno zauważyć, że jest to zwykły postęp arytmetyczny o pierwszym wyrazie 4 i różnicy 3 (tzn. każda następna liczba jest o 3 większa od poprzedniej, a pierwsza to 4).

Ułóżmy teraz nieskończoną tablicę następująco:


Pierwszy wiersz tej tabeli, to nasz ciąg wyjściowy. Ten sam ciąg powtarza się jako pierwsza kolumna. Drugi wiersz jest znów postępem arytmetycznym, tylko teraz o różnicy 5; następny także jest postępem, ale o różnicy 7; kolejny również, tyle że teraz różnica między kolejnymi wyrazami wynosi 9, w następnym – 11…
Inaczej mówiąc: naszą nieskończoną tabelę wypełniamy wierszami postępów arytmetycznych, których różnicami są kolejne liczby nieparzyste poczynając od 3.

No i teraz prawdziwe jest następujące

Twierdzenie:
Jeśli pewna liczba N występuje w tej tablicy, to 2N+1 jest zawsze liczbą złożoną. Jeśli natomiast liczba N w tej tablicy nie występuje, to 2N+1 jest liczbą pierwszą.

Weźmy przykład: w naszej tablicy nie ma liczby 3. W myśl twierdzenia zatem 2×3+1 = 7 jest liczbą pierwszą. Liczby 6 również nie ma; wobec tego 2×6+1 = 13 jest liczbą pierwszą. Liczba 7 jest w tablicy – stąd na mocy naszego twierdzenia 2×7+1 = 15 jest liczbą złożoną.

Dowód naszego twierdzenia nie jest przesadnie skomplikowany, choć wymaga trochę prostych rachunków. Nieznający teorii postępów arytmetycznych mogą go pominąć.

Pierwszy wiersz naszej tabeli zawiera liczby postaci


Drugi – liczby postaci


Ogólnie, wiersz o numerze k zawiera liczby postaci


Jeśli więc jakaś liczba N wystąpi w rozważanej tablicy, to na pewno musi być ona właśnie powyższej postaci. Istnieją zatem takie liczby naturalne k i n, że
N =

Ale wówczas

2N +1 =


i tym samym liczba N jest iloczynem dwóch czynników, z których żaden nie jest równy 1; oznacza to, że 2N + 1 jest rzeczywiście złożone.

W drugą stronę. Jeśli 2N + 1 jest dowolną liczbą nieparzystą złożoną, to da się ją napisać w postaci

2N + 1 =


gdzie k i n są pewnymi liczbami naturalnymi. Rozwiązując to równanie względem N otrzymamy

N =

co oznacza, że N należy do naszej tablicy.

Zauważmy teraz, że wszystkie liczby pierwsze (z wyjątkiem 2) są nieparzyste, a każda liczba nieparzysta (z wyjątkiem liczby 1) jest albo złożona, albo pierwsza. Stąd wniosek, że dla żadnej liczby pierwszej nieparzystej postaci 2N + 1 nie może w naszej tablicy występować liczba N. Twierdzenie jest dowiedzione w całej rozciągłości.