276062000

1.5. Kongruencje i ich własności, twierdzenie chińskie o resztach 9

uznawany za pierwszy zapisany dowód przeprowadzony metodą niewprost i choćby z tego powodu jest tym dowodem, z którym warto się zapoznać.

Liczby pierwsze obecnie to punkt wyjścia do analizy całego bogactwa problemów nie tylko stricte teorioliczbowych, o których nie sposób opowiedzieć w kilku słowach. Wspomnieć jednak wypada o wciąż udoskonalanych testach pierwszości, których celem jest zbadanie pierw-szości zadanej liczby, (nie zaś jej rozkład na liczby pierwsze co jest zagadnieniem znacznie trudniejszym). Już w okolicach 200 p.n.e. grecki matematyk Eratosthenes ⁶wprowadził metodę wyznaczania liczb pierwszych nie mększych od ustalonej liczby n zwaną odtąd ”sitem Eratosthenesa”. Jej działanie jest niezwykle proste - wypisujemy wszystkie liczby od 2 do n następnie zakreślamy 2 jako liczbę pierwszą i wykreślamy jej wszystkie wielokrotności. Potem zakreślamy pierwszą pozostałą liczbę i wykreślamy wszystkie jej wielokrotności i tak kontynuujemy aż nie ma ”nietkniętych” liczb mniejszych lub równych od \fn. W ten sposób otrzymamy tablicę liczb pierwszych nie większych od liczby wyjściowej.

Obecne, o wiele bardziej zaawansowane metody testowania pierwszości dzielą się na dwa rodzaje: testy deterministyczne i probablistyczne. Do tych pierwszych zaliczyć można m.in. test Lucasa-Lehmera, ⁷ (przy użyciu tego testu znaleziono największe liczby pierwsze, test dotyczy badania pierwszości tzw. liczb Mer senne’a) ⁸, czy niektóre testy oparte na krzywych eliptycznych. Testy probablistyczne, choć nie pozwalają na zdecydowanie z pewnością, czy dana liczba jest pierwsza mają tę przewagę, że zwykle są dużo szybsze od testów deterministycznych. Liczby, którym udaje się przejść pozytywnie test probablistyczny, ale mimo to okazują się być jednak liczbami złożonymi znane są w kontekście liczb "pseudopierwszych”. Istnieje wiele różnych rodzajów takich liczb, z których bodaj najbardziej znane to liczby pseu-dopierwsze Fermata, które mimo iż pozostają liczbami złożonymi to spełniają założenia Małego Twierdzenia Fermata, o którym opowiemy dalej. Przy okazji testów probablistycznych wypada wspomnieć o dwóch testach: teście Rabina-Millera, który jest wyjątkowo efektywnym testem probablistycznym oraz o tzw. teście AKS (od nazwisk twórców: Manindra Agrawala, Neeraja Kayala i Nitina Saxena, 2002), który to test deterministyczny sprawdza pierwszość zadanej liczby w czasie wielomianowym, słowem jego czas działania jest ograniczony za pomocą zależności wielomianowej od rozmiaru danych wejściowych. Do czasu pojawienia się tego testu zasadniczo nie było dowodu na to, iż test pierwszości zadanej liczby jest problemem rozwiązywalnym w czasie wielomianowym mimo, iż uważano że taka możliwość istnieje.

1.5 Kongruencje i ich własności, twierdzenie chińskie o resztach

Na pierwszej stronie swego dzieła ”Disquisitiones Arithmeticae” Gauss wprowadza pojęcie ”kongruencji”, czyli jak to określać będziemy dalej ” przystawania”. Dzięki zastosowaniu tej notacji wiele własności i twierdzeń otrzymało prostszą postać, ale też znacznie ułatwiło to

(⁶) Eratosthenes: grecki matematyk, poeta, geograf, astronom i filozof (276-194 p.n.e.)

(⁷) Edouard Lucas, matematyk francuski 1842-1891, Derrick Henry Lehmer, matematyk amerykański, 1905-1991

(⁸) Liczby Mersenne’a: liczby postaci 2^P — 1, gdzie p jest liczbą pierwszą, nazwane tak na cześć matematyka francuskiego Marina Mersenne’a, autora pierwszej tablicy liczb pierwszych tego typu, (niestety zawierającą błędy) - Marin Mersenne: matematyk, filozof i teolog francuski, (1588-1648)